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):
r,c=map(int,input().split())
meiro=[list(input()) for i in range(r)]

from collections import deque
quest=deque([])

for i in range(r):
    meiro[i].insert(c,"
    meiro[i].insert(0,"
meiro.insert(0,["
meiro.append(["

tesuu=[[-1]*(c+2) for i in range(r+2)]
for i in range(1,r+1):
    for j in range(1,c+1):
        if meiro[i][j]=="
            quest.append([i,j])
            tesuu[i][j]=0


idou=[[0,1],[0,-1],[1,0],[-1,0]]

while len(quest)!=0:
    see=quest.popleft()
    for i in idou:
        if meiro[see[0]+i[0]][see[1]+i[1]]=="
            continue
        if tesuu[see[0]+i[0]][see[1]+i[1]]!=-1:
            continue
        quest.append([see[0]+i[0],see[1]+i[1]])
        tesuu[see[0]+i[0]][see[1]+i[1]]=tesuu[see[0]][see[1]]+1
te=[]
for i in range(r+2):
    te.extend(tesuu[i])
print(max(te))

Solution (Python):
from collections import deque

H,W=map(int,input().split())
field=[]
spos=deque([])
for i in range(H):
  s=list(input())
  for j in range(W):
    if s[j]=="
      spos.append((j,i))
  field.append(s)
  

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

ans=-1
while spos:
  for _ in range(len(spos)):
    x,y=spos.popleft()
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if nx<0 or nx>=W or ny<0 or ny>=H:
        pass
      elif field[ny][nx]==".":
        field[ny][nx]="
        spos.append((nx,ny))
  ans+=1

print(ans)

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

l=[input() for _ in range(H)]


def bfs(H,W,l):
  ans=0
  que=deque()
  count=[[-1]*W for _ in range(H)]
  num=H*W
  dx=[1,-1,0,0]
  dy=[0,0,1,-1]
  for i in range(H):
    for j in range(W):
      if l[i][j]=='
        count[i][j]=0
        que.append([i,j])
        num-=1
  while num>0:
    x,y=que.popleft()
    for k in range(4):
      a, b=x+dx[k], y+dy[k]
      if a<0 or a>=H or b<0 or b>=W or count[a][b]!=-1:
        continue
      else:
        count[a][b]=count[x][y]+1
        que.append([a,b])
        num-=1
  for i in range(H):
    ans=max(ans,max(count[i]))
  return ans
print(bfs(H,W,l))

Solution (Python):
from scipy.ndimage import distance_transform_cdt
 
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
n = [[1 if x == "." else 0 for x in row] for row in a]
 
distance = distance_transform_cdt(n, metric='taxicab')
res = distance.max()
print(res)

Solution (Python):
h,w=map(int,input().split())
g=[]
for i in range(h):
    g.append(list(input()))
q=[]
v=[[0 for i in range(w)] for j in range(h)]
for i in range(h):
    for j in range(w):
        if g[i][j]=='
            q.append([i,j])
            v[i][j]=1
ans=0
while len(q)>0:
    tmp=[]
    for i in q:
        a=i[0]
        b=i[1]
        if a==0:
            hi=[1]
        elif a==h-1:
            hi=[-1]
        else:
            hi=[1,-1]
        if h==1:
            hi=[]
        if b==0:
            wi=[1]
        elif b==w-1:
            wi=[-1]
        else:
            wi=[1,-1]
        if w==1:
            wi=[]
        for c in hi:
            if v[a+c][b]==0:
                tmp.append([a+c,b])
                v[a+c][b]=1
        for d in wi:
            if v[a][b+d]==0:
                tmp.append([a,b+d])
                v[a][b+d]=1
    q=tmp
    ans+=1
print(ans-1)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
c = []
d = [[-1 for i in range(w)] for j in range(h)]
q = deque()
for i in range(h):
	s = input()
	c.append(s)
	for j in range(w):
		if c[i][j] == '
			q.append([i, j, 0])
			d[i][j] = 0

dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]

while len(q) != 0:
	y, x, z = q[0]

	for i in range(4):
		ny, nx = y + dirr[i][0], x + dirr[i][1]
		if 0 <= ny < h and 0 <= nx < w and d[ny][nx] == -1 and c[ny][nx] != "
			q.append([ny, nx, z + 1])
			d[ny][nx] = z + 1

	q.popleft()

print(z)

Solution (Python):
import sys
from collections import defaultdict

input = sys.stdin.readline


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

        blacks = []
        for h in range(H):
            for w in range(W):
                if A[h][w] == '
                    blacks.append((h + 1, w + 1))

        moving_range = ((1, 0), (-1, 0), (0, -1), (0, 1))

        ans = 0
        while blacks:
            next_blacks = []
            for b_h, b_w in blacks:
                for m_h, m_w in moving_range:
                    h, w = b_h + m_h, b_w + m_w
                    if not (0 < h <= H and 0 < w <= W):
                        continue
                    if A[h-1][w-1] == '.':
                        A[h-1][w-1] = '
                        next_blacks.append((h, w))
            if len(next_blacks) > 0:
                ans += 1
            blacks = next_blacks

        print(ans)



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

Solution (Python):
from collections import deque

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

queue = deque([])
Distance = [-1]*(h*w)

for i in range(h):
    for j in range(w):
        if A[i*w+j]=='
            queue.append([i,j])
            Distance[i*w+j] = 0

ans = 0

while queue:
    x,y = queue.popleft()
    d = Distance[x*w+y]
    if x!=0 and Distance[(x-1)*w+y] == -1:
            queue.append([x-1,y])
            ans = Distance[(x-1)*w+y] = d+1
    if x!=h-1 and Distance[(x+1)*w+y] == -1:
            queue.append([x+1,y])
            ans = Distance[(x+1)*w+y] = d+1
    if y!=0 and Distance[x*w+y-1] == -1:
            queue.append([x,y-1])
            ans = Distance[x*w+y-1] = d+1
    if y!=w-1 and Distance[x*w+y+1] == -1:
            queue.append([x,y+1])
            ans = Distance[x*w+y+1] = d+1

print(ans)

Solution (Python):
def main():
    from collections import deque

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

    queue = deque([])
    Distance = [-1]*(h*w)

    for i in range(h):
        for j in range(w):
            if A[i*w+j]=='
                queue.append([i,j])
                Distance[i*w+j] = 0

    ans = 0

    while queue:
        x,y = queue.popleft()
        d = Distance[x*w+y]
        if x!=0 and Distance[(x-1)*w+y] == -1:
                queue.append([x-1,y])
                ans = Distance[(x-1)*w+y] = d+1
        if x!=h-1 and Distance[(x+1)*w+y] == -1:
                queue.append([x+1,y])
                ans = Distance[(x+1)*w+y] = d+1
        if y!=0 and Distance[x*w+y-1] == -1:
                queue.append([x,y-1])
                ans = Distance[x*w+y-1] = d+1
        if y!=w-1 and Distance[x*w+y+1] == -1:
                queue.append([x,y+1])
                ans = Distance[x*w+y+1] = d+1

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

Solution (Python):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)

from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque



def main():
    high, width = map(int, input().split())
    data = [list(input()) for i in range(high)]
    for i in range(high):
        for j in range(width):
            if data[i][j] == '.':
                data[i][j] = 10 ** 5
            else:
                data[i][j] = 0

    for i in range(high):
        for j in range(1, width):
            data[i][j] = min(data[i][j], data[i][j - 1] + 1)

    for i in range(high):
        for j in range(width - 1)[::-1]:
            data[i][j] = min(data[i][j], data[i][j + 1] + 1)

    for j in range(width):
        for i in range(1, high):
            data[i][j] = min(data[i][j], data[i - 1][j] + 1)

    for j in range(width):
        for i in range(high - 1)[::-1]:
            data[i][j] = min(data[i][j], data[i + 1][j] + 1)


    ans = 0
    for i in range(high):
        ans = max(ans, max(data[i]))

    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

class Grid():
    def __init__(self,i,j,isblack):
        self.i=i
        self.j=j
        self.isblack=isblack
        self.distance=0

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

g=[]
for i in range(H):
    Ai=input()
    gi=[]    
    for j in range(W):
        gi.append(Grid(i,j,Ai[j]=='
    g.append(gi)

d=deque()


for row in g:
    for grid in row:
        if grid.isblack:
            d.append(grid)

while d:
    tg=d.popleft()
    i=tg.i
    j=tg.j
    if i>0 and not g[i-1][j].isblack:
        g[i-1][j].isblack=True
        g[i-1][j].distance=tg.distance+1
        d.append(g[i-1][j])
    if i<H-1 and not g[i+1][j].isblack:
        g[i+1][j].isblack=True
        g[i+1][j].distance=tg.distance+1
        d.append(g[i+1][j])
    if j>0 and not g[i][j-1].isblack:
        g[i][j-1].isblack=True
        g[i][j-1].distance=tg.distance+1
        d.append(g[i][j-1])
    if j<W-1 and not g[i][j+1].isblack:
        g[i][j+1].isblack=True
        g[i][j+1].distance=tg.distance+1
        d.append(g[i][j+1])

'''
for row in g:
    for grid in row:


'''

print(max([max([grid.distance for grid in row]) for row in g]))

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

Q = []
V = [[0] * w for i in range(h)]
D = [[0] * w for i in range(h)]

for i in range(h):
    for j in range(w):
        if A[i][j] == "
            Q.append([i, j, 0])
            V[i][j] = 1
            D[i][j] = 0


st = 0
while st < len(Q):
    for i in [[-1,0], [1,0], [0,-1], [0,1]]:
        x = Q[st][0] + i[0]
        y = Q[st][1] + i[1]
        if 0 <= x < h and 0 <= y < w and V[x][y] == 0:
            V[x][y] = 1
            Q.append([x, y, Q[st][2]+1])
            D[x][y] = Q[st][2]+1
    st += 1

print(max([max(i) for i in D]))

Solution (Python):
def main():
    H, W = (int(i) for i in input().split())
    A = [input() for j in range(H)]
    from collections import deque
    st = deque()
    dist = [[-1]*W for i in range(H)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '
                st.append((h,w))
                dist[h][w] = 0
    
    def bfs():
        ans = 0
        que = st
        d = ((1,0),(0,1),(-1,0),(0,-1))

        while que:
            uy,ux = que.popleft()
            for dy, dx in d:
                next_y = uy + dy
                next_x = ux + dx
                if not(0 <= next_y < H and 0 <= next_x < W): continue
                if dist[next_y][next_x] != -1: continue
                if A[next_y][next_x] == '
                dist[next_y][next_x] = dist[uy][ux] + 1
                ans = max(ans, dist[next_y][next_x])
                que.append((next_y, next_x))
        return ans
    
    print(bfs())

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
import sys

buf = sys.stdin.buffer
H,W = map(int,buf.readline().split())

black = np.zeros((H+2,W+2),dtype=np.bool)

black[1:-1,1:] = (np.frombuffer(buf.read(H*(W+1)),dtype='S1') == b'

INF = 10 ** 4
dist = np.zeros((H,W),dtype=np.int16)

dist[~black[1:-1,1:-1]] = INF

for n in range(1,H):
    np.minimum(dist[n-1]+1,dist[n],out=dist[n])
for n in range(H-2,-1,-1):
    np.minimum(dist[n+1]+1,dist[n],out=dist[n])
for n in range(1,W):
    np.minimum(dist[:,n-1]+1,dist[:,n],out=dist[:,n])
for n in range(W-2,-1,-1):
    np.minimum(dist[:,n+1]+1,dist[:,n],out=dist[:,n])

print(dist.max())

Solution (Python):

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions
from operator import itemgetter

import sys
def input():
	return sys.stdin.readline().strip()

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

A = []
for i in range(H):
	A.append(input())

num = [[0]*W for _ in range(H)]
black_list = deque()
for i in range(H):
	for j in range(W):
		if A[i][j] == ".":
			num[i][j] = 1000000
		else:
			black_list.append((i, j))
dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]

max_num = 0
while len(black_list) > 0:
	i, j = black_list.popleft()
	for n in range(4):
		x = i + dxy[n][0]
		y = j + dxy[n][1]
		if x < H and y < W and 0 <= x and 0 <= y:
			if num[x][y] > 10000:
				num[x][y] = num[i][j] + 1
				black_list.append((x, y))
				max_num = max(max_num, num[x][y])

print(max_num)

Solution (Python):
h, w = map(int, input().split())
a = [['*' for _ in range(w+2)]]
for _ in range(h):
    a.append(['*'] + list(input()) + ['*'])
a.append(['*' for _ in range(w+2)])

q = set()

def encode(i, j):
    return i*w + j-1

def decode(x):
    i = x // w
    j = x % w + 1
    return [i, j]

for i in range(1, h+1):
    for j in range(1, w+1):
        if a[i][j] == '
            q.add(encode(i, j))

for ans in range(h+w):
    nq = set()
    for x in q:
        i, j = decode(x)
        for k in [-1,1]:
            if a[i+k][j] == '.':
                nq.add(encode(i+k, j))
                a[i+k][j] = '
        for k in [-1,1]:
            if a[i][j+k] == '.':
                nq.add(encode(i, j+k))
                a[i][j+k] = '
    if len(nq) == 0:
        print(ans)
        exit()
    else:
        q = set()
        q = q | nq

Solution (Python):
h, w = [ int(v) for v in input().split() ]
field = []
search_list = []
adjust_list = ((0,1),(0,-1),(1,0),(-1,0))

for i in range(h):
    line = list(input())
    field.append(line)
    for j, v in enumerate(line):
        if v == "
            search_list.append((i,j))

t = 0
while search_list:
    new_search_list = []
    for i in search_list:
        for j in adjust_list:
            if 0 <= i[0]+j[0] < h and 0 <= i[1]+j[1] < w:
                if field[i[0]+j[0]][i[1]+j[1]] == ".":
                    field[i[0]+j[0]][i[1]+j[1]] = "
                    new_search_list.append((i[0]+j[0], i[1]+j[1]))
    search_list = new_search_list
    if search_list:
        t += 1

print(t)

Solution (Python):
from collections import deque


def bfs(h, w, board, visited):
    queue = deque([])
    for i in range(h):
        for j in range(w):
            if board[i][j] == "
                queue.append([i, j])
                visited[i][j] = 0
    ans = 0
    while queue:
        y, x = queue.popleft()
        for i, j in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            yn, xn = y+i, x+j
            if yn >= h or xn >= w or yn < 0 or xn < 0:
                continue
            if visited[yn][xn] == -1 and board[yn][xn] == ".":
                visited[yn][xn] = visited[y][x] + 1
                queue.append([yn, xn])
                ans = max(ans, visited[yn][xn])

    return ans


def main():
    h, w = map(int, input().split())
    board = [input() for _ in range(h)]
    visited = [[-1 for _ in range(w)] for _ in range(h)]
    print(bfs(h, w, board, visited))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



def bfs(A):
    d = [[0,1],[0,-1],[1,0],[-1,0]]
    used = [[False]*W for _ in range(H)]
    q = []
    for i in range(H):
        for j in range(W):
            if A[i][j] == '
                used[i][j] = True
                q.append([i,j])
    c = 0
    while q:
        q1 = []
        count_flag = False
        for place in q:
            for move in d:
                new_x, new_y = place[0]+move[0], place[1]+move[1]
                if 0<=new_x<H and 0<=new_y<W:
                    if used[new_x][new_y]==False:
                        used[new_x][new_y] = True
                        q1.append([new_x,new_y])
                        count_flag = True
        q = q1
        if count_flag:
            c += 1
    return c

H,W = II()
A = [list(map(str, input())) for _ in range(H)]
print(bfs(A))

Solution (Python):
from collections import deque


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

    q = deque()

    arrived = [[True] * (w + 2)] + \
              [[True] + [False] * w + [True] for _ in range(h)] + \
              [[True] * (w + 2)]

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

    ans = 0
    while q:
        ans += 1
        pop_max = len(q)
        cnt = 0
        while cnt != pop_max:
            i, j = q.popleft()
            if not arrived[i-1][j]:
                arrived[i-1][j] = True
                q.append((i-1, j))

            if not arrived[i+1][j]:
                arrived[i+1][j] = True
                q.append((i+1, j))

            if not arrived[i][j-1]:
                arrived[i][j-1] = True
                q.append((i, j-1))

            if not arrived[i][j+1]:
                arrived[i][j+1] = True
                q.append((i, j+1))

            cnt += 1

    ans -= 1
    print(ans)


def main():
    solve()


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque


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

    q = deque()

    arrived = [[True] * (w + 2)] + \
              [[True] + [False] * w + [True] for _ in range(h)] + \
              [[True] * (w + 2)]

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

    ans = 0
    while q:
        ans += 1
        pop_max = len(q)
        cnt = 0
        while cnt != pop_max:
            i, j = q.popleft()
            if not arrived[i-1][j]:
                arrived[i-1][j] = True
                q.append([i-1, j])

            if not arrived[i+1][j]:
                arrived[i+1][j] = True
                q.append([i+1, j])

            if not arrived[i][j-1]:
                arrived[i][j-1] = True
                q.append([i, j-1])

            if not arrived[i][j+1]:
                arrived[i][j+1] = True
                q.append([i, j+1])

            cnt += 1

    ans -= 1
    print(ans)


def main():
    solve()


if __name__ == "__main__":
    main()

Solution (Python):
from scipy.ndimage import distance_transform_cdt


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

    sq = [[1 if e == "." else 0 for e in row] for row in a]

    cnt = distance_transform_cdt(sq, metric="taxicab")

    print(cnt.max())


if __name__ == "__main__":
    main()

Solution (Python):
import array
import itertools
from collections import defaultdict, deque


def log(s):
    
    pass


def output(x):
    print(x, flush=True)


def input_ints():
    return map(int, input().split())


def solve():
    def fill(queue):
        footsteps = [[None] * width for _ in range(height)]

        for x, y in queue:
            footsteps[y][x] = 0

        s = 0
        while queue:
            queue2 = deque()
            s += 1
            while queue:
                x, y = queue.popleft()

                if x > 0 and footsteps[y][x - 1] is None:
                    queue2.append((x - 1, y))
                    footsteps[y][x - 1] = s
                if x < width - 1 and footsteps[y][x + 1] is None:
                    queue2.append((x + 1, y))
                    footsteps[y][x + 1] = s
                if y > 0 and footsteps[y - 1][x] is None:
                    queue2.append((x, y - 1))
                    footsteps[y - 1][x] = s
                if y < height - 1 and footsteps[y + 1][x] is None:
                    queue2.append((x, y + 1))
                    footsteps[y + 1][x] = s

            queue = queue2

        return s - 1

    height, width = tuple(input_ints())
    field = [input() for _ in range(height)]
    queue = deque()

    for y, line in enumerate(field):
        for x, c in enumerate(line):
            if c == '
                queue.append((x, y))
    


    return fill(queue)


def main():
    print(solve())


main()

Solution (Python):
h, w = map(int, input().split())
visited = [[False] * w for _ in range(h)]
pts = []
for i in range(h):
    s = input().rstrip()
    for j in range(w):
        if s[j] == '
            visited[i][j] = True
            pts.append((i, j))
res = 0
ds = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while True:
    new_pts = []
    for i, j in pts:
        for dx, dy in ds:
            new_i = i + dy
            new_j = j + dx
            if 0 <= new_i < h and 0 <= new_j < w and not visited[new_i][new_j]:
                visited[new_i][new_j] = True
                new_pts.append((new_i, new_j))
    if len(new_pts) > 0:
        res += 1
        pts = new_pts
    else:
        break
print(res)

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):
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):
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):
h, w = map(int, input().split())
b = [[0] * w for _ in range(h)]
q = []

for i in range(h):
    for j, m in enumerate(input()):
        if m == "
            q.append((i, j))
            b[i][j] = 1

cnt = -1

while q:
    nq = []
    for y, x in q:
        if y > 0:
            if not b[y-1][x]:
                b[y-1][x] = 1
                nq.append((y-1, x))
        if y < h-1:
            if not b[y+1][x]:
                b[y+1][x] = 1
                nq.append((y+1, x))
        if x > 0:
            if not b[y][x-1]: 
                b[y][x-1] = 1
                nq.append((y, x-1))
        if x < w-1:
            if not b[y][x+1]: 
                b[y][x+1] = 1
                nq.append((y, x+1))
    
    q = nq    
    cnt += 1
    
print(cnt)

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,w = LI()
maze = [list(input()) for _ in range(h)]
check = [[True]*w for _ in range(h)]
dx,dy = [0,1,0,-1],[1,0,-1,0]
que = deque()
for i in range(h):
    for j in range(w):
        if maze[i][j] == '
            check[i][j] = False
            que.append((j,i))
res = 0
while que:
    que2 = deque(que)
    que = deque()
    flg = False
    while que2:
        x,y = que2.popleft()
        for i in range(4):
            nx,ny = x + dx[i], y + dy[i]
            if 0 <= nx < w and 0 <= ny < h:
                if check[ny][nx]:
                    check[ny][nx] = False
                    que.append((nx,ny))
                    flg = True
    if flg:
        res += 1
print(res)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
q=deque()

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

ans=0
while q:
    nq=deque()
    while True:        
        y,x=q.popleft()
        for dy,dx in ((1,0),(-1,0),(0,1),(0,-1)):
            ny=dy+y
            nx=dx+x
            if 0<=ny<h and 0<=nx<w and a[ny][nx]!='
                a[ny][nx]='
                nq.append((ny,nx))
        if not q:
            ans+=1
            q=nq
            break
print(ans-1)

Solution (Python):
import sys
from collections import defaultdict, deque
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())




L = [list(input().strip())  for _ in range(N)]


al = [[False for _ in range(M)] for _ in range(N)]
d = []
for i in range(N):
    for j in range(M):
        if L[i][j] == "
            al[i][j] = True
            d.append((i, j))
            pass

for i in range(10000):
    if len(d) == 0:
        print(i - 1)
        exit()
    else:
        d2 = list()
        for x, y in d:
            if x - 1 >= 0 and al[x - 1][y] == False:
                al[x - 1][y] = True
                d2.append((x - 1, y))

            if x + 1 < N and al[x + 1][y] == False:
                al[x + 1][y] = True
                d2.append((x + 1, y))

            if y - 1 >= 0 and al[x][y - 1] == False:
                al[x][y - 1] = True
                d2.append((x, y - 1))

            if y + 1 < M and al[x][y + 1] == False:
                al[x][y + 1] = True
                d2.append((x, y + 1))

        d = d2

Solution (Python):
from collections import deque

h,w=map(int,input().split())
a=[input() for i in range(h)]
lis=[[-1 for i in range(w)] for j in range(h)]
q=deque()


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


while q:
  cur=q.popleft()
  i,j=cur[0],cur[1]

  if 0<=i+1<=h-1 and 0<=j<=w-1:
    if lis[i+1][j]==-1:
      lis[i+1][j]=lis[i][j]+1
      q.append((i+1,j))
  
  if 0<=i-1<=h-1 and 0<=j<=w-1:
    if lis[i-1][j]==-1:
      lis[i-1][j]=lis[i][j]+1
      q.append((i-1,j))

  
  if 0<=i<=h-1 and 0<=j+1<=w-1:
    if lis[i][j+1]==-1:
      lis[i][j+1]=lis[i][j]+1
      q.append((i,j+1))
      
  if 0<=i<=h-1 and 0<=cur[1]-1<=w-1:
    if lis[i][j-1]==-1:
      lis[i][j-1]=lis[i][j]+1
      q.append((i,j-1))      
  
print(max(max(l) for l in lis))

Solution (Python):
H, W = map(int, input().split())
A = []
q = []
for i in range(H):
  As = list(input())
  A.append(As)
  for j in range(W):
    if A[i][j] == "
      q.append((i, j))
r = 0
while q:
  q2 = []
  for i, j in q:
    if i-1 >= 0 and A[i-1][j] == ".":
      A[i-1][j] = "
      q2.append((i-1, j))
    if i+1 < H and A[i+1][j] == ".":
      A[i+1][j] = "
      q2.append((i+1, j))
    if j-1 >= 0 and A[i][j-1] == ".":
      A[i][j-1] = "
      q2.append((i, j-1))
    if j+1 < W and A[i][j+1] == ".":
      A[i][j+1] = "
      q2.append((i, j+1))
  q = q2
  r += 1
r -= 1
print(r)

Solution (Python):
from collections import deque
h, w = map(int,input().split())
graph = []
finished = [[False for _ in range(w)] for _ in range(h)]
y = [0, 0, 1,-1]
x = [1,-1, 0, 0]
q = deque([])
for i in range(h):
    a = input()
    graph.append(a)
    for j in range(w):
        if a[j] == "
            q.append((i,j,0))
while q:
    c = q.popleft()
    for i in range(4):
        nh = c[0]+y[i]
        nw = c[1]+x[i]
        if nh < 0 or nh >= h or nw < 0 or nw >= w or graph[nh][nw] == "
        finished[nh][nw] = True
        q.append((nh,nw,c[2]+1))
print(c[2])

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))
 
dx=[1,0,-1,0]            
dy=[0,1,0,-1]
ans=0
 
while q:
    nq=deque()
    while True:
        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 a[ny][nx]!='
                a[ny][nx]='
                nq.append((ny,nx))

        if not q:
            ans+=1
            q=nq
            break
print(ans-1)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
a=[list(input()) for _ in range(h)]
field=[[False for i in range(w)] for j in range(h)]
 
q=deque()
 
for i in range(h):
    for j in range(w):
        if a[i][j]=='
            q.append((i,j))
            field[i][j]=True
 
dx=[1,0,-1,0]            
dy=[0,1,0,-1]
ans=0
 
while q:
    nq=deque()
    while True:
        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 field[ny][nx]==False:
                field[ny][nx]=True
                nq.append((ny,nx))

        if not q:
            ans+=1
            q=nq
            break
print(ans-1)