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):
from collections import deque
h, w = map(int, input().split())

a = [[False]*(w+2)]
for y in range(h):
    a.append([False] + [x!='
a.append([False]*(w+2))

s = deque()
for i in range(1, h+1):
    for j in range(1, w+1):
        if not a[i][j]:
            s.append((i,j))

ans = -1
while s:
    ns = deque()
    for i, j in s:
        if a[i-1][j]:
            a[i-1][j] = False
            ns.append((i-1, j))
        if a[i+1][j]:
            a[i+1][j] = False
            ns.append((i+1, j))
        if a[i][j-1]:
            a[i][j-1] = False
            ns.append((i, j-1))
        if a[i][j+1]:
            a[i][j+1] = False
            ns.append((i, j+1))
        
    s = ns
    ans += 1
    
print(ans)

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

a = [[False]*(w+2)]
for y in range(h):
    a.append([False] + [x!='
a.append([False]*(w+2))

s = deque()
for i in range(1, h+1):
    for j in range(1, w+1):
        if not a[i][j]:
            s.append((i,j))

ans = -1
while s:
    ns = deque()
    for i, j in s:
        if a[i-1][j]:
            a[i-1][j] = False
            ns.append((i-1, j))
        if a[i+1][j]:
            a[i+1][j] = False
            ns.append((i+1, j))
        if a[i][j-1]:
            a[i][j-1] = False
            ns.append((i, j-1))
        if a[i][j+1]:
            a[i][j+1] = False
            ns.append((i, j+1))
        
    s = ns
    ans += 1
    
print(ans)

Solution (Python):
def main():
    H, W = map(int, input().split())
    m = []
    m.append([True] * (W + 2))
    for _ in range(H):
        m.append([True] + [c == '
    m.append([True] * (W + 2))
    queue = []
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if m[i][j]:
                queue.append((i, j))
    ans = -1
    while queue:
        ans += 1
        tmp = []
        for x, y in queue:
            if not m[x - 1][y]:
                m[x - 1][y] = True
                tmp.append((x - 1, y))
            if not m[x + 1][y]:
                m[x + 1][y] = True
                tmp.append((x + 1, y))
            if not m[x][y - 1]:
                m[x][y - 1] = True
                tmp.append((x, y - 1))
            if not m[x][y + 1]:
                m[x][y + 1] = True
                tmp.append((x, y + 1))
        queue = tmp
    print(ans)

if __name__ == '__main__':
    main()

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

from collections import deque
q = deque()
for i, r in enumerate(l):
    for j, c in enumerate(r):
        if c == '
            l[i][j] = 0
            q.append((i, j))
d = [(0, 1), (0, -1), (1, 0), (-1, 0)]

while q:
    y, x = q.popleft()
    for dy, dx in d:
        if (0 <= y+dy < H) and (0 <= x+dx < W) and l[y+dy][x+dx] == '.':
            l[y+dy][x+dx] = l[y][x] + 1
            q.append((y+dy, x+dx))

m = 0
for r in l:
    for c in r:
        if m < c:
            m = c
print(m)

Solution (Python):
from collections import deque
import copy
 
def main():
    h, w = map(int, input().split())
    a = [[j == "
 
 
    
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])
 
    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))
 
        if nque:
            que = copy.copy(nque)
        else:
            break
 
    print(count - 1)
 
if __name__ == "__main__":
    main()

Solution (Python):

def bfs() -> None:
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    cur, q = 0, []
    
    q = [(x, y) for x in range(H) for y in range(W) if B[x][y] == 0]
    while q:  
        next_q = []
        for x, y in q:
            for dx, dy in dxy:
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and B[nx][ny] == -1:
                    B[nx][ny] = cur + 1
                    next_q.append((nx, ny))
        q = next_q
        cur += 1
    return cur - 1


def main():
    global H, W, B
    H, W, *A = open(0).read().split()
    H, W = int(H), int(W)
    
    B = [[0 if i == "
    ans = bfs()
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

def bfs() -> None:
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    cur, q = 0, []
    for x, b in enumerate(B):
        for y, i in enumerate(b):
            if i != cur:
                continue
            for dx, dy in dxy:
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and B[nx][ny] == -1:
                    B[nx][ny] = cur + 1
                    q.append((nx, ny))
    while q:
        cur += 1
        next_q = []
        for x, y in q:
            for dx, dy in dxy:
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and B[nx][ny] == -1:
                    B[nx][ny] = cur + 1
                    next_q.append((nx, ny))
        q = next_q
    return cur


def main():
    global H, W, B
    H, W, *A = open(0).read().split()
    H, W = int(H), int(W)
    B = [[0 if i == "
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    ans = bfs()
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):


from scipy.ndimage import distance_transform_cdt as dist


def main():
    H, W, *A = open(0).read().split()
    B = [[1 if i == "." else 0 for i in a] for a in A]
    D = dist(B, metric="taxicab")
    ans = D.max()
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):


from scipy.ndimage import distance_transform_cdt as dist


def main():
    """
    distance_transform_cdt:
        orig     taxicab / chessboard
        1 1 1     2 1 2      1 1 1
        1 0 1 ->  1 0 1      1 0 1
        1 1 1     2 1 2      1 1 1
    """
    H, W, *A = open(0).read().split()
    B = [[1 if i == "." else 0 for i in a] for a in A]
    D = dist(B, metric="taxicab")
    ans = D.max()
    print(ans)


if __name__ == "__main__":
    main()

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

def main():
    H, W = map(int, input().split())

    INF = int(1e7)
    a = np.array([list(map(lambda x: 0 if x=="

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

    print(np.max(a))

if __name__ == "__main__":
    main()

Solution (Python):

h, w = map(int, input().split())
a = []
a = [[True] * (w + 2)]
for i in range(h):
    a.append([True] + [x == '
a.append([True] * (w + 2))
q = []

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if a[i][j]:
            q.append((i, j))

count = 0
while True:
    qq = []
    for i, j in q:
        if not a[i-1][j]:
            a[i-1][j] = True
            qq.append((i - 1, j))
        if not a[i+1][j]:
            a[i+1][j] = True
            qq.append((i + 1, j))
        if not a[i][j-1]:
            a[i][j-1] = True
            qq.append((i, j - 1))
        if not a[i][j+1]:
            a[i][j+1] = True
            qq.append((i, j + 1))
    q = qq
    if len(q) <= 0:
        break
    count += 1

print(count)

Solution (Python):
import numpy as np
from scipy.ndimage import distance_transform_cdt as d
h,w=map(int,input().split())
s=[[1 if i=="." else 0 for i in input()]for i in range(h)]
a=d(s,metric='taxicab')
print(a.max())

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

H,W = map(int, input().split())
check = []
b = [[True]*(W+2)]

for i in range(H):
    s = input().strip()
    b.append([True] + [False]*W + [True])
    for j,c in enumerate(s):
        if c == '
            check.append((i+1,j+1))
            b[i+1][j+1] = True
b.append([True]*(W+2))

t = 0
while check:
    tmp = []
    for i,j in check:
        if not b[i-1][j]:
            b[i-1][j] = True
            tmp.append((i-1,j))
        if not b[i][j-1]:
            b[i][j-1] = True
            tmp.append((i,j-1))
        if not b[i][j+1]:
            b[i][j+1] = True
            tmp.append((i,j+1))
        if not b[i+1][j]:
            b[i+1][j] = True
            tmp.append((i+1,j))
    check = tmp
    t += 1

print(t-1)

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


INF = 10000
S = [[INF for _ in range(W)] for _ in range(H)]
for i in range(H):
  flag = False
  for j in range(W):
    if A[i][j] == '
      flag  = True
      d = 0
      S[i][j] = 0
    if flag and A[i][j] == '.':
      d += 1
      S[i][j] = min(d,S[i][j])
  flag = False
  for j in range(W-1,-1,-1):
    if A[i][j] == '
      flag  = True
      d = 0
      S[i][j] = 0
    if flag and A[i][j] == '.':
      d += 1
      S[i][j] = min(d,S[i][j])
for j in range(W):
  flag = False
  for i in range(H):
    if S[i][j] < INF:
      flag = True
    if flag and i > 0 and A[i][j] == '.':
      S[i][j] = min(S[i][j],S[i-1][j]+1)
  flag = False
  for i in range(H-1,-1,-1):
    if S[i][j] < INF:
      flag = True
    if flag and i < H-1 and A[i][j] == '.':
      S[i][j] = min(S[i][j],S[i+1][j]+1)


ans = 0
for s in S:
  ans = max(ans,max(s))
print(ans)

Solution (Python):
def gen():
    print("1000 1000")
    print("
    for i in range(1000-1):
        print("."*1000)

def main():
    from collections import deque
    import sys
    from heapq import heappush, heappop
    input = sys.stdin.readline
    H, W = map(int, input().split())
    D = [None]*H
    Q = deque()
    for h in range(H):
        D[h] = [10e10]*W
        l = input()
        for w in range(W):
            if l[w] == "
                D[h][w] = 0
                Q.append((h, w))
    m = 0
    while Q:
        h, w = Q.popleft()
        alt = D[h][w] + 1
        for dx, dy in [(-1,0), (1,0), (0,-1), (0, +1)]:
            h1, w1 = h+dx, w+dy
            if 0 <= h1 < H and 0 <= w1 < W:
                if D[h1][w1] > alt:
                    D[h1][w1] = alt
                    m = max(m, alt)
                    Q.append((h1, w1))

    print(m)
main()

Solution (Python):

from collections import deque
def solve():
  h,w = (int(i) for i in input().split())
  maze = ["0"*(w+2)]
  for i in range(h):
    maze.append("0"+input()+"0")
  maze.append("0"*(w+2))
  black = deque([])
  count = 0
  visit = [[False]*(w+2) for _ in range(h+2)]
  
  for i in range(h+2):
    for j in range(w+2):
      if maze[i][j] == "
        black.append((0,i,j)) 

  d = [(0,1),(1,0),(-1,0),(0,-1)]
  ans = 0
  
  while count != h*w:
    move,y,x = black.popleft()
    
    if visit[y][x]:
      continue
    else:
      visit[y][x] = True
      count += 1
      for dy,dx in d:
        ny,nx = y+dy,x+dx
        if visit[ny][nx]:
          continue
        elif maze[ny][nx] ==".":
          black.append((move+1,ny,nx))
  print(move)
          

    
solve()

Solution (Python):
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    H,W = map(int, input().split())
    grid = [list(input().rstrip()) for _ in range(H)]
    q = []
    visited = [[False]*W for _ in range(H)]
    for y in range(H):
        for x in range(W):
            if grid[y][x] == '
                q.append((y,x))
                visited[y][x] = True
    ans = -1
    while q:
        ans += 1
        nq = []
        for y,x in q:
            if 0 < x and not visited[y][x-1]:
                visited[y][x-1] = True
                nq.append((y,x-1))
            if x < W-1 and not visited[y][x+1]:
                visited[y][x+1] = True
                nq.append((y,x+1))
            if 0 < y and not visited[y-1][x]:
                visited[y-1][x] = True
                nq.append((y-1, x))
            if y < H-1 and not visited[y+1][x]:
                visited[y+1][x] = True
                nq.append((y+1,x))
        if nq:
            q = nq[:]
        else:
            break
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys









sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    H,W = map(int, input().split())
    grid = [list(input().rstrip()) for _ in range(H)]
    q = []
    visited = [[False]*W for _ in range(H)]
    for y in range(H):
        for x in range(W):
            if grid[y][x] == '
                q.append((y,x))
                visited[y][x] = True
    ans = -1
    while q:
        ans += 1
        nq = []
        for y,x in q:
            if 0 < x and not visited[y][x-1]:
                visited[y][x-1] = True
                nq.append((y,x-1))
            if x < W-1 and not visited[y][x+1]:
                visited[y][x+1] = True
                nq.append((y,x+1))
            if 0 < y and not visited[y-1][x]:
                visited[y-1][x] = True
                nq.append((y-1, x))
            if y < H-1 and not visited[y+1][x]:
                visited[y+1][x] = True
                nq.append((y+1,x))
        if nq:
            q = nq[:]
        else:
            break
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    H, W = map(int,input().split())
    visited = [[False]*W for _ in range(H)]
    q = []
    for y in range(H):
        S = input().rstrip()
        for x, s in enumerate(S):
            if s == "
                q.append((y, x))
                visited[y][x] = True

    ans = -1
    while q:
        ans += 1
        nq = []
        for y, x in q:
            if 0 < x and not visited[y][x-1]:
                visited[y][x-1] = True
                nq.append((y,x-1))
            if x < W-1 and not visited[y][x+1]:
                visited[y][x+1] = True
                nq.append((y,x+1))
            if 0 < y and not visited[y-1][x]:
                visited[y-1][x] = True
                nq.append((y-1, x))
            if y < H-1 and not visited[y+1][x]:
                visited[y+1][x] = True
                nq.append((y+1,x))
        if nq:
            q = nq
        else:
            break

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    H, W = map(int,input().split())
    visited = [[False]*W for _ in range(H)]
    q = []
    for y in range(H):
        S = input()
        for x, s in enumerate(S):
            if s == "
                q.append((y, x))
                visited[y][x] = True

    ans = -1
    while q:
        ans += 1
        nq = []
        for y, x in q:
            if 0 < x and not visited[y][x-1]:
                visited[y][x-1] = True
                nq.append((y,x-1))
            if x < W-1 and not visited[y][x+1]:
                visited[y][x+1] = True
                nq.append((y,x+1))
            if 0 < y and not visited[y-1][x]:
                visited[y-1][x] = True
                nq.append((y-1, x))
            if y < H-1 and not visited[y+1][x]:
                visited[y+1][x] = True
                nq.append((y+1,x))
        if nq:
            q = nq
        else:
            break

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import copy

H, W = map(int, input().split())
a = [list(input()) for _ in range(H)]
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
que = deque([(i, j) for i in range(H) for j in range(W) if a[i][j] == '
count = 0

flag_all = False

while True:
	count += 1

	que_next = deque()
	while que:
		i, j = que.popleft()
		for k in range(4):
			dx, dy = d[k][0], d[k][1]
			x = i + dx
			y = j + dy
			if x >= 0 and x < H and y >= 0 and y < W and a[x][y] != '
				a[x][y] = '
				que_next.append((x, y))

	que = copy.copy(que_next)

	if que:
		que = copy.copy(que_next)
	else:
		break
print(count-1)

Solution (Python):
import sys
from pprint import pprint

from collections import deque

h, w = map(int, sys.stdin.readline().strip().split(" "))
field = []
for _ in range(h):
    field.append(list(sys.stdin.readline().strip()))



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

while q:
    count, y, x = q.popleft()
    for dy, dx in ((-1, 0), (1, 0), (0, 1), (0, -1)):
        if 0 <= y+dy < h and 0 <= x+dx < w:
            
            if field[y+dy][x+dx] == "
                continue
            else:
                field[y+dy][x+dx] = "
                q.append((count+1, y+dy, x+dx))


print(count)

Solution (Python):
from collections import deque

def main():
    H,W = map(int, input().split())

    A = [[a for a in input()] for _ in range(H)]
    
    stack = [(i, j) for i in range(H) for j in range(W) if A[i][j]=="
    ans = 0
    flag = False
    if stack:
        flag = True
    while flag:
        ans += 1
        flag = False
        
        new_stack = []
        for a,b in stack:
        
            
            
             
            if a != 0 and A[a-1][b] == ".": 
                    A[a-1][b] = "
                    new_stack.append((a-1,b))
             
            if a != H-1 and A[a+1][b] == ".": 
                    A[a+1][b] = "
                    new_stack.append((a+1,b))
            
            if b != 0 and A[a][b-1] == ".": 
                    A[a][b-1] = "
                    new_stack.append((a,b-1))
            
            if b != W-1 and A[a][b+1] == ".": 
                    A[a][b+1] = "
                    new_stack.append((a,b+1))
        stack = new_stack
        if stack:
            flag = True
        else:
            ans -= 1 

    print(ans)
            


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    H, W = map(int,input().split())

    A = [[False for _ in range(W)] for _ in range(H)]

    Q = []
    for y in range(H):
        S = input()
        for x, s in enumerate(S):
            if s == "
                Q.append((y, x))
                A[y][x] = True

    ans = 0
    while Q:
        ans += 1
        NQ = []
        for y, x in Q:
            if x > 0 and A[y][x-1] == False:
                A[y][x-1] = True
                NQ.append((y,x-1))
            if x < W-1 and A[y][x+1] == False:
                A[y][x+1] = True
                NQ.append((y,x+1))
            if y > 0 and A[y-1][x] == False:
                A[y-1][x] = True
                NQ.append((y-1, x))
            if y < H-1 and A[y+1][x] == False:
                A[y+1][x] = True
                NQ.append((y+1,x))
        if NQ:
            Q = NQ
        else:
            break

    print(ans-1)

if __name__ == '__main__':
    main()

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

B = int(1E8)

def main():

    H, W = map(int, input().split())
    
    l = 0
    q = []
    checked = []
    for h in range(H):
        S = input()
        L = []
        for w in range(W):
            if S[w] == '
                l += 1
                L.append(True)
                q.append(B*h+w)
            else:
                L.append(False)
        checked.append(L)

    Next = [[[] for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if h != 0:
                Next[h][w].append(B*(h-1) + w)
            if h != H-1:
                Next[h][w].append(B*(h+1) + w)
            if w != 0:
                Next[h][w].append(B*h + w-1)
            if w != W-1:
                Next[h][w].append(B*h + w+1)

    c = -1
    for _ in range(H+W+2):
        qq = []
        if len(q) == 0:
            break
        for hw in q:
            h, w = hw//B, hw%B
            for nhw in Next[h][w]:
                nh, nw = nhw//B, nhw%B
                if not checked[nh][nw]:
                    qq.append(B*nh + nw)
                    checked[nh][nw] = True
        q = qq
        c += 1

    print(c)


if __name__ == "__main__":
    main()

Solution (Python):
h,w = map(int,input().split())
b = [[i == "
check = []
for i in range(h):
  for j in range(w):
    if b[i][j]:
      check.append((i,j))
ans = 0
while check:
  new = []
  k = 0
  for i,j in check:
    if not b[i-1][j]:
      new.append((i-1,j))
      b[i-1][j] = True
      k = 1
    if not b[i+1][j]:
      new.append((i+1,j))
      b[i+1][j] = True
      k = 1
    if not b[i][j-1]:
      new.append((i,j-1))
      b[i][j-1] = True
      k = 1
    if not b[i][j+1]:
      new.append((i,j+1))
      b[i][j+1] = True
      k = 1
  check = new
  if k:
    ans += 1
print(ans)

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


D = [[-1] * W for i in range(H)]
queue = deque([])
for h in range(H):
    for w in range(W):
        if A[h][w] == '
            queue.append([h, w])
            D[h][w] = 0


while queue:
    nh, nw = queue.pop()
    for dh, dw in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        if not ((0 <= nh + dh < H) and (0 <= nw + dw < W)):
            continue

        if D[nh + dh][nw + dw] >= 0:
            continue

        D[nh + dh][nw + dw] = D[nh][nw] + 1
        queue.appendleft([nh + dh, nw + dw])


ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, D[h][w])

print(ans)

Solution (Python):
from collections import deque


H, W = map(int, input().split())
A = [list('
q = deque()
A_append = A.append
q_append = q.append
for _ in range(H):
    a = input()
    A_append(list('
A.append(list('
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

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

ans = 0

while len(q) != 0:
    p = q.popleft()
    for k in range(4):
        y = p[0] + dy[k]
        x = p[1] + dx[k]
        c = p[2]
        ans = max(ans, c)
        if A[y][x] == '.':
            A[y][x] = '
            q_append([y, x, c + 1])

print(ans)

Solution (Python):
r,c=map(int,input().split())
grid=[input() for _ in [0]*r]
ans=sum([grid[i].count(".") for i in range(r)])
q=[]
[[q.append([i,j]) for j in range(c) if grid[i][j]=="
visit=[[grid[i][j]=="
d=[(1,0),(-1,0),(0,1),(0,-1)]
cnt=0

while q:
    qq=[]
    while q:
        i,j=q.pop()
        for dx,dy in d:
            if 0<=i+dx<r and 0<=j+dy<c:
                if i+dx==r-1 and j+dy==c-1:
                    flag=True
                if visit[i+dx][j+dy]==False:
                    visit[i+dx][j+dy]=True
                    qq.append([i+dx,j+dy])
    q=qq
    cnt+=1
    
print(cnt-1)

Solution (Python):
import sys
import copy
import  math
import bisect
from collections import *
from operator import itemgetter
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

h, w = na()
maze = [list(input()) for _ in range(h)]
que = deque()
d = [[-1] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        if maze[i][j] == "
            d[i][j] = 0
            que.append((i, j))
l = 0

while que:
    x, y = que.popleft()
    l = d[x][y]
    for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        nx = x + dx
        ny = y + dy
        if not 0 <= nx < h or not 0 <= ny < w or d[nx][ny] != -1:
            continue
        d[nx][ny] = l + 1
        que.append((nx, ny))
print(l)

Solution (Python):
h,w=map(int,input().split())
s=set()
a=[]
from collections import deque
q=deque([])
for i in range(h):
    tmp=list(input())
    a.append(tmp)
    for j in range(w):
        if tmp[j]=="
            q.append((i,j,0))

ans=0
ll=[[0,1],[0,-1],[1,0],[-1,0]]
while q:
    x,y,v=q.popleft()
    ans=max(ans,v)
    for i,j in ll:
        if 0<=x+i<h and 0<=y+j<w and a[i+x][j+y]==".":
            a[i+x][j+y]="
            q.append((i+x,j+y,v+1))

print(ans)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
cnt = [[float('inf') for _ in range(w)] for _ in range(h)]
ans = 0
searched = [[0 for _ in range(w)] for _ in range(h)]
q = deque([])

def bfs():
  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      next_y = y + dy
      next_x = x + dx 
      if 0 <= next_y < h and 0 <= next_x < w and searched[next_y][next_x] == 0 and a[next_y][next_x] == '.' and cnt[next_y][next_x] > cnt[y][x]+1:
        searched[next_y][next_x] = 1
        q.append([next_y, next_x])
        cnt[next_y][next_x] = cnt[y][x]+1

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

bfs()
for i in range(h):
  for j in range(w):
    ans = max(ans, cnt[i][j])

print(ans)

Solution (Python):
import collections
def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(input())
    cur = []
    visited = collections.defaultdict(dict)
    for i in range(H):
        for j in range(W):
            if A[i][j] == "
                cur.append([i, j])
                visited[i][j] = 1
            else:
                visited[i][j] = 0
    mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    count = 0
    while cur:
        temp = []
        for i, j in cur:
            for di, dj in mv:
                i1, j1 = i+di, j+dj
                if 0 <= i1 < H and 0 <= j1 < W and not visited[i1][j1]:
                    visited[i1][j1] = True
                    temp.append([i1, j1])
        if len(temp) > 0:
            count += 1
        cur = temp
    return count

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

Solution (Python):
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect


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

    checked = [[False] * W for _ in range(H)]
    ans = 0

    que = []
    for h in range(H):
        for w in range(W):
            if A[h][w] == '
                que.append((h, w))
                checked[h][w] = True
    while que:
        next_que = []
        while que:
            h, w = que.pop()
            dx4 = [0, 0, 1, -1]
            dy4 = [1, -1, 0, 0]

            for dx, dy in zip(dx4, dy4):
                next_h = h + dy
                next_w = w + dx
                if 0 <= next_h < H and 0 <= next_w < W and A[next_h][next_w] == '.' and not checked[next_h][next_w]:
                    A[next_h][next_w] = '
                    checked[h][w] = True
                    next_que.append((next_h, next_w))
        que = next_que
        if que:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
a=[input() for _ in range(h)]
dxy=[(0,1),(1,0),(-1,0),(0,-1)]
inf=float("inf")

dp=[[inf]*w for _ in range(h)]
q=deque()

for y,l in enumerate(a):
    for x,c in enumerate(l):
        if c=="
            dp[y][x]=0
            q.append((x,y))
ans=0
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))
        ans=max(ans,d+1)
print(ans)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
a=[input() for _ in range(h)]
dxy=[(0,1),(1,0),(-1,0),(0,-1)]
inf=float("inf")

dp=[[inf]*w for _ in range(h)]
q=deque()

for y,l in enumerate(a):
    for x,c in enumerate(l):
        if c=="
            dp[y][x]=0
            q.append((x,y))
ans=0
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))
        ans=max(ans,d+1)
print(ans)

Solution (Python):

from collections import deque
import copy

def main():
    h, w = map(int, input().split())
    a = [[j == "


    
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))

        if nque:
            que = copy.copy(nque)
        else:
            break

    print(count - 1)

if __name__ == '__main__':
    main()