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):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

from decimal import *

H, W = MAP()
A = [input() for _ in range(H)]
cnt = [[-1]*W for _ in range(H)]
q = deque()

for y in range(H):
    for x in range(W):
        if A[y][x] == "
            cnt[y][x] = 0
            q.append((y, x))

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

while q:
    y, x = q.popleft()
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < H and 0 <= nx < W and cnt[ny][nx] == -1:
            cnt[ny][nx] = cnt[y][x] + 1
            q.append((ny, nx))

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

from decimal import *

H, W = MAP()
A = [input() for _ in range(H)]
cnt = [[0]*W for _ in range(H)]
q = deque()

for y in range(H):
    for x in range(W):
        if A[y][x] == "
            q.append((y, x))

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

while q:
    y, x = q.popleft()
    for Dy, Dx in zip(dy, dx):
        ny = y + Dy
        nx = x + Dx
        if 0 <= ny < H and 0 <= nx < W and cnt[ny][nx] == 0 and A[ny][nx] == ".":
            cnt[ny][nx] = cnt[y][x] + 1
            q.append((ny, nx))

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

from decimal import *

H, W = MAP()
A = [input() for _ in range(H)]
cnt = [[-1]*W for _ in range(H)]
q = deque()

for y in range(H):
    for x in range(W):
        if A[y][x] == "
            cnt[y][x] = 0
            q.append((y, x))

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

while q:
    y, x = q.popleft()
    for Dy, Dx in zip(dy, dx):
        ny = y + Dy
        nx = x + Dx
        if 0 <= ny < H and 0 <= nx < W and cnt[ny][nx] == -1 and A[ny][nx] == ".":
            cnt[ny][nx] = cnt[y][x] + 1
            q.append((ny, nx))

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

from decimal import *

H, W = MAP()
A = [input() for _ in range(H)]
cnt = [[-1]*W for _ in range(H)]
q = deque()

for y in range(H):
    for x in range(W):
        if A[y][x] == "
            cnt[y][x] = 0
            q.append((y, x))

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

while q:
    y, x = q.popleft()
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < H and 0 <= nx < W and cnt[ny][nx] == -1:
            cnt[ny][nx] = cnt[y][x] + 1
            q.append((ny, nx))

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

from decimal import *

H, W = MAP()
A = [input() for _ in range(H)]
check = [[-1]*W for _ in range(H)]
q = deque()

for y in range(H):
    for x in range(W):
        if A[y][x] == "
            check[y][x] = 0
            q.append((y, x, 0))

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

while q:
    y, x, cnt = q.popleft()
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < H and 0 <= nx < W:
            if check[ny][nx] == -1 or cnt+1 < check[ny][nx]:
                check[ny][nx] = cnt + 1
                q.append((ny, nx, cnt+1))


print(max([max(c) for c in check]))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

from decimal import *

H, W = MAP()
A = [input() for _ in range(H)]
check = [[-1]*W for _ in range(H)]
q = deque()

for y in range(H):
    for x in range(W):
        if A[y][x] == "
            check[y][x] = 0
            q.append((y, x, 0))

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

while q:
    y, x, cnt = q.popleft()
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < H and 0 <= nx < W:
            if check[ny][nx] == -1 or cnt+1 < check[ny][nx]:
                check[ny][nx] = cnt + 1
                q.append((ny, nx, cnt+1))


print(max([max(c) for c in check]))

Solution (Python):
import collections

h,w = map(int,input().split())
field = [list(input()) for i in range(h)]

black = collections.deque()
for i in range(h):
    for j in range(w):
        if field[i][j] == "
            black.append((i,j))
            
ans = 0
dx = [1,0,-1,0]
dy = [0,1,0,-1]

def bfs(y,x):
    for k in range(4):
        newy = y + dy[k]
        newx = x + dx[k]
        if 0<= newy < h and 0<= newx < w:
            if field[newy][newx] == ".":
                black.append((newy,newx))
                field[newy][newx] = "

while black:
    l = len(black)
    for i in range(l):
        s = black.popleft()
        y,x = s[0],s[1]
        bfs(y,x)
    ans += 1

print(ans-1)

Solution (Python):

from collections import deque
H, W = map(int, input().split())
D = [list(input()) for i in range(H)]

visited = [[False for i in range(W)] for j in range(H)]
dis = [[0 for i in range(W)] for j in range(H)]

black = deque()
dif = [(-1, 0), (1, 0), (0, 1), (0, -1)]
for i in range(H):
    for j in range(W):
        if D[i][j] == "
            visited[i][j] = True
            black.append((i, j))

while black:
    x, y = black.popleft()
    for dx, dy in dif:
        if 0 <= dx+x < H and 0 <= dy+y < W and visited[dx+x][dy+y] == False:
            visited[dx+x][dy+y] = True
            dis[dx+x][dy+y] = dis[x][y]+1
            black.append((dx+x, dy+y))
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, dis[i][j])
print(ans)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W = map(int, input().split())
    grid = list(list(input()) for _ in range(H))

    que = deque([])
    maze = [[f_inf] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if grid[h][w] == "
                que.append([h, w])
                maze[h][w] = 0

    while que:
        h, w = que.popleft()
        for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            next_h, next_w = h + dh, w + dw
            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                continue
            if maze[next_h][next_w] > maze[h][w] + 1:
                maze[next_h][next_w] = maze[h][w] + 1
                que.append([next_h, next_w])

    res = 0
    for h in range(H):
        for w in range(W):
            res = max(res, maze[h][w])
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):


from collections import deque

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

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

A = []
black_deque = deque()

for i in range(H):
    A.append(list(input()))
    black_deque.extend([(i,j) for j in range(W) if A[i][j] == '

if len(black_deque) == H*W:
    print(0)
    exit(0)

for x,y in black_deque:
    A[x][y] = 0

while len(black_deque) != 0:
    x,y = black_deque.popleft()
    depth = A[x][y]
    for k in range(4):
        new_x = x+dx[k]
        new_y = y+dy[k]
        if 0 <= new_x < H and \
           0 <= new_y < W and \
           A[new_x][new_y] == '.':
            black_deque.append((new_x, new_y))
            A[new_x][new_y] = depth+1

print(depth)

Solution (Python):
h, w = map(int, input().split())
A = [["
                     for _ in range(h)] + [["


def main():
    step = 0
    Q = set([])
    for hh in range(1, h + 1):
        for ww in range(1, w + 1):
            if A[hh][ww] == "
                if A[hh - 1][ww] == ".":
                    Q.add((hh - 1, ww))
                if A[hh][ww - 1] == ".":
                    Q.add((hh, ww - 1))
                if A[hh + 1][ww] == ".":
                    Q.add((hh + 1, ww))
                if A[hh][ww + 1] == ".":
                    Q.add((hh, ww + 1))
    while len(Q) > 0:
        step += 1
        new = set([])
        for hh, ww in Q:
            A[hh][ww] = "
        while len(Q) > 0:
            hh, ww = Q.pop()
            if A[hh - 1][ww] == ".":
                A[hh-1][ww] = "
                new.add((hh - 1, ww))
            if A[hh][ww - 1] == ".":
                A[hh][ww-1] = "
                new.add((hh, ww - 1))
            if A[hh + 1][ww] == ".":
                A[hh+1][ww] = "
                new.add((hh + 1, ww))
            if A[hh][ww + 1] == ".":
                A[hh][ww + 1] = "
                new.add((hh, ww + 1))
        Q = new.copy()
    print(step)
    return


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque


def bfs(q):
    ans = 0
    while q:
        i, j = q.popleft()
        for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W and dist[ni][nj] < 0:
                q.append((ni, nj))
                dist[ni][nj] = dist[i][j] + 1
                ans = max(ans, dist[ni][nj])
    return ans


H, W = map(int, input().split())
field = [input() for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        if field[i][j] == "
            dist[i][j] = 0
            q.append((i, j))
print(bfs(q))

Solution (Python):


from collections import deque
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     


def debug(start, goal, p, t):
    player = p
    debug_grid = list(list(grid[h]) for h in range(H))
    if start != (None, None):
        debug_grid[start[0]][start[1]] = "S"
    if goal != (None, None):
        debug_grid[goal[0]][goal[1]] = "G"
    debug_grid[player[0]][player[1]] = "P"
    print("~~~~~~~~~ t = " + str(t+1) + "  ~~~~~~~~")
    for debug_h in range(H):
        print("".join(str(debug_grid[debug_h][debug_w]) for debug_w in range(W)))


def bfs(grid, next_set, goal, visit):
    visit[start[0]][start[1]] = 1               
    while next_set:                             
        p, t = next_set.popleft()               
        h, w = p
        for dh, dw in move:                     
            q = (h + dh, w + dw)
            if q[0] < 0 or q[0] >= H or q[1] < 0 or q[1] >= W:
                continue
            if grid[q[0]][q[1]] == wall:         
                continue
            if visit[q[0]][q[1]] == 1:           
                continue
            
            
            
            if q == goal:                       
                return t + 1                    
            visit[q[0]][q[1]] = 1               
            next_set.append((q, t + 1))         
    return t


road, wall = ".", "

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

grid = []
next_set = deque()
visit = [[0]*W for _ in range(H)]
for h in range(H):
    grid.append(input())
    for w, a in enumerate(grid[-1]):
        if a == "
            start = (h, w)
            next_set.append((start,0))
            visit[start[0]][start[1]] = 1

print(bfs(grid, next_set, (None,None), visit))

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
q = deque()
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
x = ((-1, 0), (1, 0), (0, -1), (0, 1))
for i in range(h):
    for j in range(w):
        if a[i][j] == "
            for k in x:
                if 0 <= i + k[0] < h and 0 <= j + k[1] < w and a[i + k[0]][j + k[1]] == ".":
                    a[i + k[0]][j + k[1]] = "0"
                    q.append([i + k[0], j + k[1], 1])
ans = 0
while q:
    u, v, res = q.popleft()
    for k in x:
        if 0 <= u + k[0] < h and 0 <= v + k[1] < w and a[u + k[0]][v + k[1]] == ".":
            a[u + k[0]][v + k[1]] = "0"
            q.append((u + k[0], v + k[1], res + 1))
            ans = res + 1
print(ans)

Solution (Python):
from collections import deque 
import sys
input = sys.stdin.readline
q = deque([])
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
x=[[-1,0],[1,0],[0,-1],[0,1]]
for i in range(h):
    for j in range(w):
        if a[i][j]=="
            for k in x:
                if 0<=i+k[0]<h and 0<=j+k[1]<w and a[i+k[0]][j+k[1]]==".":
                    a[i+k[0]][j+k[1]]="0"
                    q.append([i+k[0],j+k[1],1])
ans=0
while q:
    v=q.popleft()
    for k in x:
        if 0<=v[0]+k[0]<h and 0<=v[1]+k[1]<w and a[v[0]+k[0]][v[1]+k[1]]==".":
            a[v[0]+k[0]][v[1]+k[1]]="0"
            q.append((v[0]+k[0],v[1]+k[1],v[2]+1))
            ans=v[2]+1
print(ans)

Solution (Python):
from collections import deque 
import sys
input = sys.stdin.readline
q = deque([])
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
x=[[-1,0],[1,0],[0,-1],[0,1]]
for i in range(h):
    for j in range(w):
        if a[i][j]=="
            for k in x:
                if 0<=i+k[0]<h and 0<=j+k[1]<w and a[i+k[0]][j+k[1]]==".":
                    a[i+k[0]][j+k[1]]="0"
                    q.append([i+k[0],j+k[1],1])
ans=0
while q:
    v=q.popleft()
    for k in x:
        if 0<=v[0]+k[0]<h and 0<=v[1]+k[1]<w and a[v[0]+k[0]][v[1]+k[1]]==".":
            a[v[0]+k[0]][v[1]+k[1]]="0"
            q.append([v[0]+k[0],v[1]+k[1],v[2]+1])
            ans=v[2]+1
print(ans)

Solution (Python):
from collections import deque

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

q = deque([])
for i in range(h):
    for j in range(w):
        if a[i][j] == '
            q.append([i, j])
            q.append(0)

while q:
    y, x = q.popleft()
    ans = q.popleft() + 1
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        ny, nx = dy + y, dx + x
        if ny < 0 or nx < 0 or ny >= h or nx >= w:
            continue
        if a[ny][nx] == '.':
            a[ny][nx] = '
            q.append([ny, nx])
            q.append(ans)

print(ans-1)

Solution (Python):
from collections import deque
def main():
    H, W = map(int,input().split())
    s = [list(map(str,input())) for _ in range(H)]
    dist = [[-1]*W for _ in range(H)]
    
    q = deque([])
    for i in range(H):
        for j in range(W):
            if s[i][j] == "
                dist[i][j] = 0
                q.append((i, j))
    
    ans = 0
    while q:
        x, y = q.popleft()
        dx = [1, -1, 0, 0]
        dy = [0, 0, 1, -1]
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if (0 <= nx < H and 0 <= ny < W and dist[nx][ny] == -1 and s[nx][ny] == '.'):
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))
                ans = max(ans, dist[nx][ny])
                
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
H,W=map(int, input().split())

A=[]
que=[]
done=[[-1]*W for _ in range(H)]
for h in range(H):
    a=list(input())
    A.append(a)
    for w in range(W):
        if a[w]=="
            que.append((h,w))
            done[h][w]=0

d=[(1,0),(-1,0),(0,1),(0,-1)]
que=deque(que)
ans=0
while que:
    h,w=que.popleft()
    now=done[h][w]
    for t in d:
        dh,dw=t
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if done[nh][nw]==-1:
                done[nh][nw]=now+1
                que.append((nh,nw))
                ans=max(ans, now+1)



print(ans)

Solution (Python):
from collections import deque
INF = -1
H, W = map(int,input().split())
d = [[INF for i in range(W)] for j in range(H)]
tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]

q = deque()
for i in range(H):
    line = list(input())
    for j in range(W):
        if line[j] == '
            d[i][j] = 0
            q.append([i, j, 0])

ans = 0

while len(q) > 0:
    p = q.popleft()
    ans = max(ans, p[2])
    for i in range(4):
        nx = p[0] + tx[i]
        ny = p[1] + ty[i]
        if 0 <= nx <= H-1 and 0 <= ny <= W-1 and d[nx][ny] == INF:
            d[nx][ny] = p[2] + 1
            q.append([nx, ny, p[2]+1])

print(ans)

Solution (Python):


from collections import deque
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     


def debug(start, goal, p, t):
    player = p
    debug_grid = list(list(grid[h]) for h in range(H))
    if start != (None, None):
        debug_grid[start[0]][start[1]] = "S"
    if goal != (None, None):
        debug_grid[goal[0]][goal[1]] = "G"
    debug_grid[player[0]][player[1]] = "P"
    print("~~~~~~~~~ t = " + str(t+1) + "  ~~~~~~~~")
    for debug_h in range(H):
        print("".join(str(debug_grid[debug_h][debug_w]) for debug_w in range(W)))


def search(grid, next_set, goal=(None,None), visit=set()):
    visit.add(start)                            
    while next_set:                             
        p, t = next_set.popleft()               
        h, w = p
        for dh, dw in move:                     
            q = (h + dh, w + dw)
            if q[0] < 0 or q[0] >= H or q[1] < 0 or q[1] >= W:
                continue
            if grid[q[0]][q[1]] == wall:         
                continue
            if q in visit:                      
                continue
            
            
            
            if q == goal:                       
                return t + 1                    
            visit.add(q)                        
            next_set.append((q, t + 1))         
    return t



road, wall = ".", "

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

grid = []
next_set = deque()
visit = set()
for h in range(H):
    grid.append(input())
    for w, a in enumerate(grid[-1]):
        if a == "
            start = (h, w)
            next_set.append((start,0))
            visit.add(start)

print(search(grid, next_set, goal=(None,None), visit=visit))

Solution (Python):


import copy
import random
import bisect 
import fractions 
import math
import sys
import collections
from decimal import Decimal 

mod = 10**9+7
sys.setrecursionlimit(mod) 

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

H, W = LI()
A = [[] for i in range(H)]
for i in range(H):
    a = list(str(input()))
    A[i] = a

visited = [[-1 for i in range(W)] for j in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j] == "
            d.append((i,j))
            visited[i][j] = 0

moves = [[0,1],[1,0],[-1,0],[0,-1]]
cnt = 0
while len(d) > 0:
    X, Y = d.popleft()
    cnt = visited[X][Y]
    for x, y in moves:
        n_X = X + x
        n_Y = Y + y
        if 0 <= n_X < H and 0 <= n_Y< W:
            if visited[n_X][n_Y] == -1:
                visited[n_X][n_Y] = cnt + 1
                d.append((n_X, n_Y))
print(cnt)

Solution (Python):
from collections import deque

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

S = [None]*W
S = [list(input()) for i in range(H)]
light = []
for i in range(H):
    for j in range(W):
        if S[i][j] == "
            light.append((i,j))

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

not_visited = [[-1]*W for i in range(H)]
stack = deque()
for k in range(len(light)):
    stack.append(light[k])
    i,j = light[k]
    not_visited[i][j] = 0

while stack != deque([]):
    y,x = stack.popleft()
    for i in range(4):
        if 0<= x+dx[i] <W and 0<= y+dy[i] <H and not_visited[y+dy[i]][x+dx[i]] == -1:
            not_visited[y+dy[i]][x+dx[i]] =  not_visited[y][x] + 1
            stack.append((y+dy[i],x+dx[i]))

ans = -1
for i in range(H):
    ans = max(ans,max(not_visited[i]))

print(ans)

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

INF = 1 << 21


def main():
  H, W = list(map(int, input().split()))
  M = [input()[:-1] for _ in range(H)]

  blacks = deque()
  whites = []
  d = [[INF]*W for _ in range(H)]
  for i in range(H):
    for j in range(W):
      if M[i][j] == '
        blacks.append((i, j))
        d[i][j] = 0
      elif M[i][j] == '.':
        whites.append((i, j))

  def bfs(q, d):
    is_visited = [[0]*W for _ in range(H)]
    while len(q):
      ur, uc = q.popleft()
      d_ur = d[ur]
      for vr, vc in [(ur+1, uc), (ur-1, uc), (ur, uc-1), (ur, uc+1)]:
        if 0 <= vr < H and \
           0 <= vc < W:

          d_vr = d[vr]
          is_visited_vr = is_visited[vr]
          if not(is_visited_vr[vc]) and not(M[vr][vc] == '
             (d_vr[vc] > d_ur[uc] + 1):

            d_vr[vc] = d_ur[uc] + 1
            is_visited_vr[vc] = True
            q.append((vr, vc))
    return d_ur[uc]

  print(bfs(blacks, d))


if(__name__ == '__main__'):
  main()

Solution (Python):
from collections import deque
h,w=map(int,input().split())
l=[]
l.append('@'*(w+2))
for i in range(h):
    l.append('@'+input()+'@')
l.append('@'*(w+2))
q=deque()
p=[[-1 for i in j] for j in l]
for i in range(1,h+1):
    for j in range(1,w+1):
        if l[i][j]=='
            q.append([i,j])
            p[i][j]=0
while len(q)>0:
    x,y=q.popleft()
    for i,j in [[1,0],[-1,0],[0,-1],[0,1]]:
        if l[x+i][y+j]=='.' and p[x+i][y+j]==-1:
            q.append([x+i,y+j])
            p[x+i][y+j]=p[x][y]+1
a=0
for i in p:
    for j in i:
        a=max(a,j)
print(a)