Problem:
 Score : 300 points    Problem Statement You are given a grid of squares with H horizontal rows and W vertical columns, where each square is painted white or black. HW characters from A_{11} to A_{HW} represent the colors of the squares. A_{ij} is # if the square at the i -th row from the top and the j -th column from the left is black, and A_{ij} is . if that square is white.  We will repeatedly perform the following operation until all the squares are black:   Every white square that shares a side with a black square, becomes black.   Find the number of operations that will be performed.
The initial grid has at least one black square.      Constraints  1 \leq H,W \leq 1000  A_{ij} is # or . .  The given grid has at least one black square.         Input Input is given from Standard Input in the following format:  H  W  A_{11} A_{12} ... A_{1W}  :  A_{H1} A_{H2} ... A_{HW}       Output Print the number of operations that will be performed.        Sample Input 1 3 3
...
.#.
...      Sample Output 1 2  After one operation, all but the corners of the grid will be black. After one more operation, all the squares will be black.       Sample Input 2 6 6
..#..#
......
#..#..
......
.#....
....#.      Sample Output 2 3

Solution (Python):
MAX_INT = int(10e10)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def cnt(c,d):
    if (0 <= c < H) and (0 <= d < W):
        return grid[c][d]
    else:
        return MAX_INT
def tami(a,b):
    num = min(cnt(a+1,b),cnt(a,b+1),cnt(a-1,b),cnt(a,b-1))
    return num+1

H,W = IL()
A = [[i for i in S()] for i in range(H)]

grid = [[MAX_INT]*W for i in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j] == "
            grid[i][j] = 0

for i in range(H):
    for j in range(W):
        if grid[i][j] != 0:
            grid[i][j] = tami(i,j)

for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if grid[i][j] != 0:
            grid[i][j] = tami(i,j)

ans = 0
for i in range(H):
    ans = max(ans,max(grid[i][:]))

print(ans)

Solution (Python):

def parse(A):
    R=len(A)
    C=len(A[0])
    grid=[[1 for j in xrange(C)]  for i in xrange(R)]
    for i in xrange(R):
        for j in xrange(C):
            if A[i][j]=='.':
                grid[i][j]=0
                
    return grid

def find(grid):
    black={}
    R=len(grid)
    C=len(grid[0])
    new=[]
    for i in xrange(R):
        for j in xrange(C):
            if grid[i][j]==1:
                black[(i,j)]=0
                new+=[(i,j)]
    time=0        
    
    while len(black)<R*C:
        
        time+=1
        new_black=set([])
        
        for X in new:
            x,y=X
            check=[(x-1,y),(x+1,y),(x,y-1),(x,y+1)]
            for Y in check:
                y1,y2=Y[0],Y[1]
                if y1>R-1 or y1<0 or y2>C-1 or y2<0:
                    continue
                if grid[y1][y2]==0:
                    new_black.add((y1,y2))
                    
                    black[(y1,y2)]=1
                else:
                    continue
        for X in new_black:
            grid[X[0]][X[1]]=1
        new=[]
        new=new_black
        
    return time    

H,W=list(map(int,raw_input().strip().split(' ')))
A=[]
for _ in xrange(H):
    A+=[raw_input()]
grid=parse(A)
print(find(grid))

Solution (Python):
import numpy as np

H, W = map(int, input().split())
A = tuple(input() for _ in range(H))

INF = H * W

dp = np.full((H, W), INF, dtype=np.int)

for i in range(H):
	for j in range(W):
		dp[i, j] = 0 if A[i][j] == '

for i in range(1, H):
	dp[i, :] = np.minimum(dp[i, :], dp[i-1, :] + 1)
for i in range(0, H-1)[::-1]:
	dp[i, :] = np.minimum(dp[i, :], dp[i+1, :] + 1)
for j in range(1, W):
	dp[:, j] = np.minimum(dp[:, j], dp[:, j-1] + 1)
for j in range(0, W-1)[::-1]:
	dp[:, j] = np.minimum(dp[:, j], dp[:, j+1] + 1)

print(np.max(dp))

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

H, W = map(int, input().split())
grid = [[v for v in input()[:-1]] for _ in range(H)]

Q = []
cnt = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] == "
            Q.append([i, j])
            cnt += 1

DX = [-1, 1, 0, 0]
DY = [0, 0, -1, 1]
d = 0

while cnt < H*W:
    d += 1
    tmp = []
    
    
    
    
    
    for x, y in Q:
        for dx, dy in zip(DX, DY):
            nx = x+dx
            ny = y+dy
            if 0 <= nx < H and 0 <= ny < W:
                if grid[nx][ny] == ".":
                    grid[nx][ny] = "
                    tmp.append([nx, ny])
                    cnt += 1
            else:
                continue
    Q = tmp

print(d)

Solution (Python):
import sys
H, W = map(int, sys.stdin.readline().split())
INF = float('inf')
S = [[INF] * W for i in range(H)]
for i in range(H):
    a = list(sys.stdin.readline())
    for j in range(W):
        if a[j] == '
            S[i][j] = 0

ma = 0
for i in range(1, H):
    for j in range(W):
        S[i][j] = min(S[i][j], S[i - 1][j] + 1)

for i in range(H - 2, -1, -1):
    for j in range(W):
        S[i][j] = min(S[i][j], S[i + 1][j] + 1)

for i in range(H):
    for j in range(1, W):
        S[i][j] = min(S[i][j], S[i][j - 1] + 1)

for i in range(H):
    for j in range(W - 2, -1, -1):
        S[i][j] = min(S[i][j], S[i][j + 1] + 1)

for i in range(H):
    for j in range(W):
        ma = max(ma, S[i][j])

print(ma)

Solution (Python):


from bisect import bisect_left as binl
from copy import copy

def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * sy) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x





def safe_ref(listlist, x, y):
    if x < 0 or y < 0 or x >= len(listlist) or y >= len(listlist[0]):
        return None
    try:
        return listlist[x][y]
    except:
        return None

def main():
    h, w = intin()
    alistlist = []
    for i in range(h):
        alistlist.append([s for s in input()])

    count = 0
    check_list = []

    for i, alist in enumerate(alistlist):
        for j, a in enumerate(alist):
            if a == '
                count += 1
                check_list.append((i, j))

    for repeated in range(h * w * 3):
        if count == h * w:
            print(repeated)
            return

        new_alistlist = copy(alistlist)
        next_list = []

        for i, j in check_list:
            if safe_ref(alistlist, i+1, j) == '.':
                new_alistlist[i+1][j] = '
                next_list.append((i+1, j))
                count += 1
            if safe_ref(alistlist, i-1, j) == '.':
                new_alistlist[i-1][j] = '
                next_list.append((i-1, j))
                count += 1
            if safe_ref(alistlist, i, j+1) == '.':
                new_alistlist[i][j+1] = '
                next_list.append((i, j+1))
                count += 1
            if safe_ref(alistlist, i, j-1) == '.':
                new_alistlist[i][j-1] = '
                next_list.append((i, j-1))
                count += 1

        check_list = next_list
        alistlist = new_alistlist


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
h,w = map(int, input().split())
a = [list(input()) for _ in range(h)]
d = [(0,1),(1,0),(0,-1),(-1,0)]
q = deque()
cnt = h*w
t = 0
for i in range(h):
  for j in range(w):
    if a[i][j] == "
      q.append((i,j))
      a[i][j] = 0
      cnt -= 1
while cnt:
  y,x = q.popleft()
  for dx,dy in d:
    if 0 <= x+dx < w and 0 <= y+dy < h and a[y+dy][x+dx] == ".":
      a[y+dy][x+dx] = a[y][x] + 1
      cnt -= 1
      q.append((y+dy,x+dx)) 
for i in range(h):
  m = max(a[i])
  t = max(t,m)
print(t)

Solution (Python):
def main():
    h, w = map(int, raw_input().split())
    aa = []
    for _ in xrange(h):
        aa.append(raw_input())
    q = []
    dist = [[False] * w for _ in xrange(h)]
    for y in xrange(h):
        row = aa[y]
        for x in xrange(w):
            if row[x] == '
                dist[y][x] = True
                q.append([x, y])
    m = 0
    nexts = []
    while True:
        for x, y in q:
            for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                xx = x + dx
                yy = y + dy
                if 0 <= xx < w and 0 <= yy < h:
                    if aa[yy][xx] == '.' and not dist[yy][xx]:
                        dist[yy][xx] = True
                        nexts.append([xx, yy])
        if nexts:
            m += 1
            q = nexts
            nexts = []
        else:
            break
    print m


if __name__ == '__main__':
    main()

Solution (Python):
H, W = map(int, input().split())
masu = []
for i in range(H):
    masu.append(list(input()))
black = []
for i in range(H):
    for j in range(W):
        if masu[i][j] == "
            black.append([i,j])
ans = -1
while len(black) != 0:
    ans += 1
    blacktemp = black[:]
    black = []
    for k in blacktemp:
        for i, j in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
            if 0 <= k[0] + i <= H-1 and 0 <= k[1] + j <= W-1:
                if masu[k[0]+i][k[1]+j] == ".":
                    masu[k[0]+i][k[1]+j] = "
                    black.append([k[0]+i, k[1]+j])
print(ans)

Solution (Python):
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.head = None
        self.last = None
        self._size = 0

    def enqueue(self, data):
        if self.last is None:
            self.head = Node(data)
            self.last = self.head
        else:
            self.last.next = Node(data)
            self.last = self.last.next
            
        self._size += 1

    def dequeue(self):
        if self.head is None:
            return None
        else:
            to_return = self.head.data
            self.head = self.head.next
            self._size -= 1
            
            if self._size == 0:
                self.head = None
                self.last = None
            return to_return
        
    def size(self):
        return self._size
    
def inside(y,x,H,W):
    if 0<=y<H and 0<=x<W:
        return True
    else:
        return False
    
def addQueueIfPossible(new_y, new_x, new_val, data, queue):
    if inside(new_y, new_x, H, W) and data[new_y][new_x]==-1:
        data[new_y][new_x] = new_val
        queue.enqueue((new_y, new_x, new_val))
        return True
    else:
        return False

H, W = map(int,input().split())

data = []
for _ in range(H):
    data.append([0 if it=='



queue = Queue()
for y in range(H):
    for x in range(W):
        if data[y][x] == 0:
            queue.enqueue((y,x,0))

while queue.size() > 0:
    y, x, val = queue.dequeue()
    
    addQueueIfPossible(y-1, x, val+1, data, queue)
    
    addQueueIfPossible(y+1, x, val+1, data, queue)
    
    addQueueIfPossible(y, x+1, val+1, data, queue)
    
    addQueueIfPossible(y, x-1, val+1, data, queue)

print(val)

Solution (Python):
BLACK = '
WHITE = '.'
sizeI, sizeJ = map(int, input().split())
a = [list(input()) for _ in range(sizeI)]

nBlack = 0
curStep = []
for i in range(sizeI):
    for j in range(sizeJ):
        if a[i][j] == BLACK:
            nBlack += 1
            curStep.append((i, j))
need = sizeI * sizeJ
ret = 0
while nBlack != need:
    nextStep = []
    for i, j in curStep:
        for di, dj in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            ni, nj = i + di, j + dj
            if 0 <= ni < sizeI and 0 <= nj < sizeJ and a[ni][nj] == WHITE:
                a[ni][nj] = BLACK
                nBlack += 1
                nextStep.append((ni, nj))
    ret += 1
    curStep = nextStep
print(ret)

Solution (Python):

from collections import defaultdict, deque
def inpl(): return list(map(int, input().split()))

H, W = inpl()
searched = [[10**9]*(W+2) for _ in range(H+2)]

for h in range(H+2):
    searched[h][0] = 0
    searched[h][-1] = 0
for w in range(W+2):
    searched[0][w] = 0
    searched[-1][w] = 0

Q = deque()
for h in range(H):
    for w, c in enumerate(input()):
        if c == "
            searched[h+1][w+1] = 0
            Q.append((h+1, w+1, 0))

while Q:
    h, w, c = Q.popleft()
    if searched[h][w] < c:
        continue
    for dh, dw in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
        nh, nw = h+dh, w+dw
        if searched[nh][nw] > c+1:
            searched[nh][nw] = c+1
            Q.append((nh, nw, c+1))

print(max(map(max, searched)))

Solution (Python):
from collections import deque

H,W = map(int,input().split())
A = [input() for i in range(H)]

L = [[float("inf") for x in range(W)] for y in range(H)]



dxy = [(-1,0), (1,0), (0,-1), (0,1)]

Q = deque()

for y in range(H) :
    for x in range(W) :
        if A[y][x] != "
            continue
        
        L[y][x] = 0
        
        Q.append((y,x))

while Q :
    y,x = Q.popleft()

    for dy,dx in dxy :
        ny = y+dy
        nx = x+dx

        if (ny < 0) or (ny >= H) or (nx < 0) or (nx >= W) :
            continue

        if L[ny][nx] <= (L[y][x] + 1) :
            continue
        
        L[ny][nx] = L[y][x] + 1
        
        Q.append((ny,nx))

ans = 0

for y in range(H) :
    ans = max(ans, max(L[y]))
print(ans)

Solution (Python):
h,w=map(int, input().split())
a=[[i for i in input()] for j in range(h)]
q=[]
ans=-1
for i in range(h):
    for j in range(w):
        if(a[i][j]=="
            q.append([i,j])
while len(q)>0:
    tl=q
    q=[]
    for i in tl:
        y=i[0]
        x=i[1]
        if(y>0):
            if(a[y-1][x]=="."):
                a[y-1][x]="
                q.append([y-1,x])
        if(x>0):
            if(a[y][x-1]=="."):
                a[y][x-1]="
                q.append([y,x-1])
        if(y<h-1):
            if(a[y+1][x]=="."):
                a[y+1][x]="
                q.append([y+1,x])
        if(x<w-1):
            if(a[y][x+1]=="."):
                a[y][x+1]="
                q.append([y,x+1])
    ans+=1
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
from collections import deque
h,w=map(int,input().split())
MAP=[list(input().strip()) for _ in range(h)]
q=deque()
for i,M in enumerate(MAP):
    for j,m in enumerate(M):
        if m=='
            q.append((i,j,0))
delta=[(1,0),(-1,0),(0,1),(0,-1)]
ans=0
while q:
    x,y,d=q.popleft()
    ans=max(ans,d)
    for dx,dy in delta:
        if 0<=x+dx<h and 0<=y+dy<w:
            if MAP[x+dx][y+dy]=='.':
                MAP[x+dx][y+dy]='
                q.append((x+dx,y+dy,d+1))
print(ans)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
G = [input() for _ in range(H)]
dist = [0]*(H*W)
bn = 0
B = deque()
geta = W
for i, g in enumerate(G):
    for j, f in enumerate(g):
        if f == '
            bn += 1
            B.append(i*geta + j)
visited = set(B)
while bn < H*W:
    if not B:
        break
    dh, dw = divmod(B.pop(), geta)
    dhw = dh * geta + dw
    for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        ni, nj = dh + di, dw + dj
        if not (0 <= ni <= H - 1) or not (0 <= nj <= W - 1):
            continue
        nij = ni * geta + nj
        if nij in visited or G[ni][nj] == '
            continue
        visited.add(nij)
        dist[nij] = 1 + dist[dhw]
        B.appendleft(nij)
print(max(dist))

Solution (Python):
H, W = map(int, input().split())
B = [input() for _ in range(H)]
BB = [[1<<30]*W for _ in range(H)]
for y in range(H):
    p=1<<30
    for x in range(W):
        p+=1
        if B[y][x]=="
            p=0
        BB[y][x] = p

    p = 1 << 30
    for x in range(W-1,-1,-1):
        p += 1
        if B[y][x] == "
            p = 0
        p = min(p, BB[y][x])
        BB[y][x] = p

ans = 0
for x in range(W):
    p = 1 << 30
    for y in range(H):
        p = min(p+1, BB[y][x])
        BB[y][x] = p

    p = 1 << 30
    for y in range(H - 1, -1, -1):
        p = min(p+1, BB[y][x])
        ans = max(ans, p)
        BB[y][x] = p

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

H,W=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

ANS=[[-1]*W for i in range(H)]

from collections import deque
QUE=deque()

for i in range(H):
    for j in range(W):

        if MAP[i][j]=="
            QUE.append([i,j,0])
            ANS[i][j]=0

while QUE:
    NQUE=deque()
    while QUE:
        x,y,z=QUE.pop()

        for nx,ny in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:
            if nx<0 or ny<0 or nx>=H or ny>=W:
                continue

            if ANS[nx][ny]!=-1:
                continue

            NQUE.append([nx,ny,z+1])
            ANS[nx][ny]=z+1

    QUE=NQUE

            
print(max([max(ANS[i]) for i in range(H)]))

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    h,w = map(int,input().split())
    a = []
    for i in range(h):
        inp = list(input())
        a.append(inp)
    
    dp = [[10**9]*w for i in range(h)]
    
    for i in range(h):
        for j in range(w):
            if a[i][j] == '.' and [i,j] != [0,0]:
                if i >= 1:
                    dp[i][j] = dp[i-1][j]+1
                    if j >= 1:
                        dp[i][j] = min(dp[i][j],dp[i][j-1]+1)
                else:
                    dp[i][j] = dp[i][j-1]+1
            elif a[i][j] == '
                dp[i][j] = 0
    for i in range(h):
        for j in range(w-1,-1,-1):
            if a[i][j] == '.' and [i,j] != [0,w-1]:
                if i >= 1:
                    dp[i][j] = min(dp[i-1][j]+1,dp[i][j])
                    if j+1 <= w-1:
                        dp[i][j] = min(dp[i][j],dp[i][j+1]+1)
                else:
                    dp[i][j] = min(dp[i][j+1]+1,dp[i][j])
    for i in range(h-1,-1,-1):
        for j in range(w):
            if a[i][j] == '.' and [i,j] != [h-1,0]:
                if i+1 <= h-1:
                    dp[i][j] = min(dp[i+1][j]+1,dp[i][j])
                    if j >= 1:
                        dp[i][j] = min(dp[i][j],dp[i][j-1]+1)
                else:
                    dp[i][j] = min(dp[i][j-1]+1,dp[i][j])
    for i in range(h-1,-1,-1):
        for j in range(w-1,-1,-1):
            if a[i][j] == '.' and [i,j] != [h-1,w-1]:
                if i+1 <= h-1:
                    dp[i][j] = min(dp[i+1][j]+1,dp[i][j])
                    if j+1 <= w-1:
                        dp[i][j] = min(dp[i][j],dp[i][j+1]+1)
                else:
                    dp[i][j] = min(dp[i][j+1]+1 ,dp[i][j])
        
    res = -1
    for i in range(h):
        for j in range(w):
            res = max(res,dp[i][j])

    print(res)



if __name__ == '__main__':
    main()

Solution (Python):
H,W = list(map(int,input().split()))
A = [list(input()) for _ in range(H)]

q = []
for i in range(H):
    for j in range(W):
        if A[i][j] == "
            q.append((i,j))
            A[i][j] = 0
ans = 0
k = 0
while k < len(q):
    i,j = q[k]
    v = A[i][j]
    if i>0 and A[i-1][j]==".":
        A[i-1][j] = v + 1
        q.append((i-1,j))
        ans = max(ans,v+1)
    if i<H-1 and A[i+1][j]==".":
        A[i+1][j] = v + 1
        q.append((i+1,j))
        ans = max(ans,v+1)
    if j>0 and A[i][j-1]==".":
        A[i][j-1] = v + 1
        q.append((i,j-1))
        ans = max(ans,v+1)
    if j<W-1 and A[i][j+1]==".":
        A[i][j+1] = v + 1
        q.append((i,j+1))
        ans = max(ans,v+1)
    k += 1
print(ans)

Solution (Python):
h, w = map(int, input().split())

from collections import deque

q = deque([])

field = [input() for _ in range(h)]
black = [[0 for j in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
        if field[i][j] == "
            black[i][j] = 1
            q.append((i, j, 0))

dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]
ans = 0
while q:
    i, j, dist = q.popleft()
    for di, dj in dir:
        ni = i + di
        nj = j + dj
        if (0 <= ni and ni <= h-1) and (0 <= nj and nj <= w-1) and black[ni][nj] == 0:
            black[ni][nj] = 1
            ans = dist + 1
            q.append((ni, nj, dist + 1))

print(ans)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
A = [input() for i in range(H)]

dx = [1,-1,0,0]

dy = [0,0,1,-1]
B = [[-1 for i in range(W)] for j in range(H)]
qu = deque([])
for i in range(H):
  for j in range(W):
    if A[i][j] == '
      B[i][j] = 0
      qu.append((i,j))
      
      
while qu:
  base = qu.popleft()
  for i in range(4):
    if base[0]+dx[i] < 0 or base[0]+dx[i] >=H or base[1]+dy[i] < 0 or base[1]+dy[i] >=W:
      continue
    if B[base[0]+dx[i]][base[1]+dy[i]] == -1:
      qu.append((base[0]+dx[i],base[1]+dy[i]))
      B[base[0]+dx[i]][base[1]+dy[i]] = B[base[0]][base[1]] + 1
      
ans = 0
for i in range(H):
  ans = max(ans,max(B[i]))
print(ans)

Solution (Python):
from collections import deque

H, W = [int(i) for i in input().split()]
A = [[i for i in input()] for j in range(H)]

q = deque()
for h in range(H):
    for w in range(W):
        if A[h][w] == '
            q.append((h, w))

dh = [1, -1, 0, 0]
dw = [0, 0, 1, -1]
ans = 0

while len(q):
    ans += 1
    n = len(q)
    for i in range(n):
        h, w = q.popleft()
        for j in range(4):
            nh = h + dh[j]
            nw = w + dw[j]
            if nh >= H or nh < 0 or nw >= W or nw < 0:
                continue
            if A[nh][nw] == '.':
                A[nh][nw] = '
                q.append((nh, nw))

print(ans - 1)

Solution (Python):

import sys

inf = 10 ** 18

H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]

from collections import deque

field = [[None] * W for _ in range(H)]
q = deque([])
cnt = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == "
            field[i][j] = 0
            q.append((i, j, 0))
            cnt += 1

tblr = ((-1, 0), (1, 0), (0, -1), (0, 1))
while cnt < H * W:
    y, x, d = q.popleft()
    for dy, dx in tblr:
        if y + dy < 0: continue
        if x + dx < 0: continue
        if y + dy >= H: continue
        if x + dx >= W: continue
        if field[y + dy][x + dx] != None: continue
        
        field[y + dy][x + dx] = d + 1
        q.append((y + dy, x + dx, d + 1))
        cnt += 1

print(max([max(field[i]) for i in range(H)]))

Solution (Python):
from collections import deque

h, w = list(map(int, input().split()))
f = []
q = deque()
for i in range(h):
    l = input()
    for j, c in enumerate(l):
        if c == '
            q.append((0, i, j))
    f.append(l)

visited = [[False] * w for _ in [0] * h]
for d, i, j in q:
    visited[i][j] = True

ans = 0
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]

while q:
    d, i, j = q.popleft()
    ans = d
    for di, dj in move:
        ni, nj = i + di, j + dj
        if ni < 0 or h <= ni or nj < 0 or w <= nj:
            continue
        if visited[ni][nj]:
            continue
        visited[ni][nj] = True
        q.append((d + 1, ni, nj))

print(ans)

Solution (Python):
from collections import deque
def main():
    h, w = map(int, raw_input().split())
    s = [raw_input().strip() for _ in xrange(h)]
    q = deque()
    po = q.popleft
    pu = q.append
    a = [100000] * (h * w)
    for i, r in enumerate(s):
        for j, c in enumerate(r):
            if c == '
                pu((i, j))
                a[i*w+j] = 0
    dd = ((0, -1), (0, 1), (1, 0), (-1, 0))
    while q:
        x, y = po()
        z = a[x*w+y] + 1
        for dx, dy in dd:
            nx, ny = x + dx, y + dy
            if 0 <= nx < h and 0 <= ny < w and a[nx*w+ny] > z:
                a[nx*w+ny] = z
                pu((nx, ny))
    print z - 1
main()

Solution (Python):
from collections import deque
import sys
def input():
	return sys.stdin.readline()[:-1]

H, W = map(int, input().split())
m = [["
q = deque()
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

step = [[float("inf") for _ in range(W+2)] for _ in range(H+2)]

for h in range(1, H+1):
	for w in range(1, W+1):
		if m[h][w] == "
			q.appendleft([h, w])
			step[h][w] = 0

while q:
	label = q.pop()

	for i in range(4):
		h, w = label[0] + dx[i], label[1] + dy[i]
		if m[h][w] != "
			q.appendleft([h, w])
			step[h][w] = step[label[0]][label[1]] + 1

ans = 0
for h in range(1, H+1):
	for w in range(1, W+1):
		ans = max(ans, step[h][w])
print(ans)

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque

h,w = li()
a = [list(lc()) for _ in range(h)]

que = deque()

dist = [[-1]*w for _ in range(h)]

for i, ai in enumerate(a):
    for j, aij in enumerate(ai):
        if aij == "
            que.append((0, (i, j)))
            dist[i][j] = 0
        
drs = [0,1,0,-1]
dcs = [1,0,-1,0]

while que:
    cur, (r,c) = que.popleft()
    dist[r][c] = cur
    
    for dr, dc in zip(drs, dcs):
        if 0 <= r+dr < h and 0 <= c+dc < w:
            if dist[r+dr][c+dc] == -1:
                dist[r+dr][c+dc] = cur + 1
                que.append((cur+1, (r+dr, c+dc)))
                
ans = 0
for di in dist:
    for dij in di:
        ans = max(ans, dij)
print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)

def main():
    h,w = LI()
    a = [S() for _ in range(h)]
    t = set()
    for i in range(h):
        ai = a[i]
        for j in range(w):
            if ai[j] == '
                t.add(i*w+j)


    r = 0
    u = t | set()
    while 1:
        k = set()
        for ij in t:
            i = ij // w
            j = ij % w
            for di,dj in dd:
                ni = i + di
                nj = j + dj
                if ni < 0 or ni >= h or nj < 0 or nj >= w:
                    continue
                nk = ni*w + nj
                if nk in u:
                    continue
                k.add(nk)
        if not k:
            break
        r += 1
        t = k
        u |= k

    return r


print(main())

Solution (Python):


import sys
from collections import deque

INF = float('inf')
MOD = 10 ** 9 + 7
dy, dx = (0, -1, 0, 1), (1, 0, -1, 0)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    h, w = LI()
    B = [list(SI()) for _ in range(h)]

    D = deque()
    for i, row in enumerate(B):
        for j, c in enumerate(row):
            if c == '
                D.append((i, j, 0))

    while D:
        y, x, cnt = D.popleft()
        for i in range(4):
            yy = y + dy[i]
            xx = x + dx[i]

            if 0 <= yy < h and 0 <= xx < w:
                if B[yy][xx] == '
                    continue
                B[yy][xx] = '
                D.append((yy, xx, cnt + 1))

    print(cnt)




if __name__ == '__main__':
    main()

Solution (Python):
import sys
range = xrange
input = lambda: sys.stdin.readline().rstrip()

h,w = [int(x) for x in input().split()]
A = [list(input()) for _ in range(h)]

found = [False]*(w*h)

cur = []
for y in range(h):
    for x in range(w):
        if A[y][x]=='
            cur.append(y*w+x)
            found[y*w+x]=True


counter = 0
while cur:
    counter += 1
    tmp = []
    
    while cur:
        ind = cur.pop()
        y,x = divmod(ind,w)

        if 0<=x-1 and not found[ind-1]:
            tmp.append(ind-1)
            found[ind-1] = True
        if x+1<w and not found[ind+1]:
            tmp.append(ind+1)
            found[ind+1] = True

        if 0<=y-1 and not found[ind - w]:
            tmp.append(ind - w)
            found[ind-w] = True
    
        if y+1<h and not found[ind + w]:
            tmp.append(ind + w)
            found[ind+w] = True
    cur = tmp

print counter-1

Solution (Python):
import collections

h,w = map(int, input().split())
cells = []
for i in range(h):
    row = input()
    cells.append([c == '

blacks = collections.deque()

for i in range(h):
    for j in range(w):
        if cells[i][j]:
            blacks.append((i,j,0))
res = 0
while blacks:
    y,x,c = blacks.popleft()
    for dy,dx in ((-1, 0), (1, 0), (0, -1), (0,1)):
        if 0<=y+dy<h and 0<=x+dx<w and not cells[y+dy][x+dx]:
            cells[y+dy][x+dx] = True
            blacks.append((y+dy, x+dx, c+1))
            res = c+1
print(c)

Solution (Python):



from collections import deque
import heapq
import math
import bisect

H, W = map(int, input().split())
grid = [input() for i in range(H)]
dist = [[-1]*W for i in range(H)]
q = deque()
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]


def bfs():
    res = 0
    while(len(q)):
        ci, cj = q.popleft()
        for i in range(4):
            ni, nj = ci + dx[i], cj + dy[i]
            if 0<=ni<H and 0<=nj<W and dist[ni][nj]==-1:
                dist[ni][nj] = dist[ci][cj] + 1
                res = max(res, dist[ni][nj])
                q.append((ni, nj))

    return res


def main():
    for i in range(H):
        for j in range(W):
            if grid[i][j] == "
                dist[i][j] = 0
                q.append((i, j))

    print(bfs())


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
H,W = map(int,input().split())
A = [input() for i in range(H)]
dxy = [(0,1),(1,0),(0,-1),(-1,0)]

INF = 99999
dp = [[INF]*W for i in range(H)]
q = deque()
for y,row in enumerate(A):
    for x,c in enumerate(row):
        if c=='
            dp[y][x] = 0
            q.append((x,y))

while q:
    x,y = q.popleft()
    d = dp[y][x]
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if dp[ny][nx] <= d+1: continue
        dp[ny][nx] = d+1
        q.append((nx,ny))
print(max(max(row) for row in dp))

Solution (Python):
from collections import*
h,w=map(int,input().split())
c=eval('list(input()),'*h)
q=deque()
for i in range(h):
    for j in range(w):
        if c[i][j]=='
            q.append((i,j,0))
ans=0
while q:
    y,x,v=q.popleft()
    ans=max(ans,v)
    for i,j in((y,x-1),(y,x+1),(y-1,x),(y+1,x)):
        if h>i>=0 and w>j>=0 and c[i][j]=='.':
            c[i][j]='
            q.append((i,j,v+1))
print(ans)