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 = [input().strip() for _ in range(H)]
B = [[0 for _ in range(W)] for _ in range(H)]
que = []
for i in range(H):
    for j in range(W):
        if A[i][j]=="
            que.append((i,j,0))
que = deque(que)
while que:
    y,x,d = que.popleft()
    if x+1<W and A[y][x+1]=="." and B[y][x+1]==0:
        B[y][x+1]=d+1
        que.append((y,x+1,d+1))
    if y-1>=0 and A[y-1][x]=="." and B[y-1][x]==0:
        B[y-1][x]=d+1
        que.append((y-1,x,d+1))
    if x-1>=0 and A[y][x-1]=="." and B[y][x-1]==0:
        B[y][x-1]=d+1
        que.append((y,x-1,d+1))
    if y+1<H and A[y+1][x]=="." and B[y+1][x]==0:
        B[y+1][x]=d+1
        que.append((y+1,x,d+1))
bmax = 0
for i in range(H):
    for j in range(W):
        bmax = max(bmax,B[i][j])
print(bmax)

Solution (Python):
from collections import deque
from itertools import product


def bfs():
    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 not (0 <= ni < H and 0 <= nj < W and dist[ni][nj] < 0):
                continue
            dist[ni][nj] = dist[i][j] + 1
            q.append((ni, nj))


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

q = deque()
dist = [[-1] * W for _ in range(H)]
for i, j in product(range(H), range(W)):
    if A[i][j] == ".":
        continue
    q.append((i, j))
    dist[i][j] = 0
bfs()
print(max(max(row) for row in dist))

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

from collections import deque
q = deque([])
visit = [[-1]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if A[i][j] == '
            q.append((i, j))
            visit[i][j] = 0

while q:
    y, x = q.popleft()
    for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
        ny, nx = y+dy, x+dx
        if 0 <= ny < h and 0 <= nx < w:
            if visit[ny][nx] == -1:
                visit[ny][nx] = visit[y][x]+1
                q.append((ny, nx))
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, visit[i][j])
print(ans)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
q = deque()
A = []
for h in range(H):
    r = input()
    for w in range(W):
        if r[w] == "
            q.append([h, w])
    A.append([0 if s=="

d = [[-1, 0], [0, -1], [0, 1], [1, 0]]
p = 0

while q:
    h, w = q.popleft()
    p = A[h][w]+1
    for dh, dw in d:
        nh = h+dh
        nw = w+dw
        if not (0 <= nh < H):
            continue
        if not (0 <= nw < W):
            continue
        if A[nh][nw] == -1:
            A[nh][nw] = p
            q.append([nh, nw])

print(p-1)

Solution (Python):

import sys
sys.setrecursionlimit(1000000)
from collections import deque

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

data = [list(input()) for _ in range(H)]

memo = [[-1 for _ in range(W)]for _ in range(H)]
que = deque()

for h in range(H):
    for w in range(W):
        if data[h][w] == '
            memo[h][w] = 0
            que.append((h, w))

offset = ((-1, 0), (1, 0), (0, -1), (0, 1))
while que:
    now_h, now_w = que.popleft()
    for nh, nw in offset:
        if now_h+nh < 0 or H-1 < now_h+nh or now_w+nw < 0 or W-1 < now_w+nw:
            continue

        if memo[now_h+nh][now_w+nw] >= 0:
            continue

        memo[now_h+nh][now_w+nw] = memo[now_h][now_w]+1
        que.append((now_h+nh,now_w+nw))


ans = -1
for h in range(H):
    ans = max(ans, max(memo[h]))
print(ans)

Solution (Python):
import sys



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


def input_int():
    return int(input())


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


def main():
    from collections import deque

    h, w = input_int_list()
    grid = []
    visited = []
    grid.append(["@"] * (w + 2))
    visited.append([True] * (w + 2))
    for _ in range(h):
        grid.append(["@"] + list(input()) + ["@"])
        visited.append([True] + [False] * w + [True])
    grid.append(["@"] * (w + 2))
    visited.append([True] * (w + 2))

    
    
    direction = ((0, 1), (1, 0), (-1, 0), (0, -1))
    dq = deque()
    
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if grid[i][j] == "
                dq.append((i, j, 0))
                visited[i][j] = True
    ans = 0
    
    while dq:
        i, j, d = dq.popleft()
        for di, dj in direction:
            if grid[i + di][j + dj] == "." and not visited[i + di][j + dj]:
                dq.append((i + di, j + dj, d + 1))
                visited[i + di][j + dj] = True
                ans = max(ans, d + 1)

    print(ans)
    return


if __name__ == "__main__":
    main()

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

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    H, W = NMI()
    grid = [SI() for _ in range(H)]
    step = [[-1]*W for _ in range(H)]
    que = deque()
    for h in range(H):
        for w in range(W):
            p = grid[h][w]
            if p == "
                que.append((h, w))
                step[h][w] = 0
    DIR = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    while que:
        x, y = que.popleft()

        for dx, dy in DIR:
            if not(0 <= x+dx < H and 0 <= y+dy < W):
                continue
            if step[x+dx][y+dy] >= 0:
                continue
            que.append((x+dx, y+dy))
            step[x+dx][y+dy] = step[x][y] + 1

    print(max([max(s) for s in step]))



if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin
from collections import deque
def main():
    readline = stdin.readline
    H,W = map(int,readline()[:-1].split())
    A = ['' for i in range(H)]
    visited = [[False] * W for i in range(H)]
    q = deque()
    for i in range(H):
        A[i] = readline()[:-1]
        
        for j,color in enumerate(A[i]):
            if '
                q.append([i,j,0])
                visited[i][j] = True
            
            
    mx = 0
    direction = [[1,0],[0,1],[-1,0],[0,-1]]
    op = -1
    while len(q) > 0:
        
        tmp = [y,x,op] = q.popleft()
        
        mx = mx if mx > op else op
        for [dx,dy] in direction:
            ny,nx = y + dy , x + dx
            if  0 <= ny and ny < H and 0 <= nx and nx < W:
                if A[ny][nx] == '
                    continue
                q.append([ny,nx,op+1])
                visited[ny][nx] = True
    print(op)

main()

Solution (Python):
import sys
from sys import stdin
def I():
    return stdin.readline().rstrip()
def MI():
    return map(int,stdin.readline().rstrip().split())
def LI():
    return list(map(int,stdin.readline().rstrip().split()))

from collections import deque
H,W=MI()
route=[list(I()) for _ in range(H)]
d=deque()
for h in range(H):
    for w in range(W):
        if route[h][w]=='
            d.append([h,w])
cnt=0
while d:
    l=list(d)
    d.clear()
    for Y,X in l:
        for y,x in [[Y-1,X],[Y+1,X],[Y,X-1],[Y,X+1]]:
            if 0<=y<H and 0<=x<W:
                if route[y][x]=='.':
                    route[y][x]='
                    d.append([y,x])
    cnt+=1
print(cnt-1)

Solution (Python):
"""
    Author - Satwik Tiwari .
    25th Sept , 2020  - Friday
"""





from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase



from heapq import *
from math import gcd, factorial,floor,ceil

from copy import deepcopy
from collections import deque







from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect



BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)





from types import GeneratorType
def iterative(f, stack=[]):
  def wrapped_func(*args, **kwargs):
    if stack: return f(*args, **kwargs)
    to = f(*args, **kwargs)
    while True:
      if type(to) is GeneratorType:
        stack.append(to)
        to = next(to)
        continue
      stack.pop()
      if not stack: break
      to = stack[-1].send(to)
    return to
  return wrapped_func





mod = 10**9+7
def inp(): return sys.stdin.readline().rstrip("\r\n") 
def out(var): sys.stdout.write(str(var))  
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())

def zerolist(n): return [0]*n
def nextline(): out("\n")  
def testcase(t):
    for pp in range(t):
        solve(pp)
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def google(p):
    print('Case 
def lcm(a,b): return (a*b)//gcd(a,b)
def power(x, y, p) :
    res = 1     
    x = x % p  
    if (x == 0) :
        return 0
    while (y > 0) :
        if ((y & 1) == 1) : 
            res = (res * x) % p

        y = y >> 1      
        x = (x * x) % p
    return res
def ncr(n,r): return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))
def isPrime(n) :
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True



def solve(case):
    n,m = sep()
    grid = []
    for i in range(n):
        temp = list(inp())
        grid.append(temp)

    sources = []
    for i in range(n):
        for j in range(m):
            if(grid[i][j] == '
                sources.append(i*m+j)

    g = [[] for i in range(n*m)]
    for i in range(n):
        for j in range(m):
            if(i>0):
                g[i*m+j].append((i-1)*m+j)
                g[(i-1)*m+j].append(i*m+j)
            if(j>0):
                g[i*m+j].append(i*m+j-1)
                g[i*m+j-1].append(i*m+j)
            if(i<n-1):
                g[i*m+j].append((i+1)*m+j)
                g[(i+1)*m+j].append(i*m+j)
            if(j<m-1):
                g[i*m+j].append(i*m+j+1)
                g[i*m+j+1].append(i*m+j)
    
    dist = [0]*(n*m)
    q = deque([])
    vis = [False]*(n*m)
    for i in sources:
        q.append(i)
        vis[i] = True
    while(len(q)!=0):
        curr = q.popleft()
        for i in g[curr]:
            if(not vis[i]):
                dist[i] = dist[curr]+1
                vis[i] = True
                q.append(i)

    print(max(dist))



testcase(1)

Solution (Python):
h,w=map(int,input().split())
l=[list(input()) for i in range(h)]
connection=[[] for i in range(h*w)]
start=[]

for i in range(h):
  for j in range(w):
    if i!=0:
      connection[i*w+j].append((i-1)*w+j)
    if i!=h-1:
      connection[i*w+j].append((i+1)*w+j)
    if j!=0:
      connection[i*w+j].append(i*w+j-1)
    if j!=w-1:
      connection[i*w+j].append(i*w+j+1)
    if l[i][j]=='
      start.append(i*w+j)
n=h*w

def bfs(l):
  distance=[-1]*n
  next=set()
  next2=set()
  visited=[-1]*n
  visitct=0
  for i in range(len(l)):
    distance[l[i]]=0
    for j in range(len(connection[l[i]])):
      next.add(connection[l[i]][j])
    visited[l[i]]=1
    visitct=+1
  next=list(next)
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

print(max(bfs(start)))

Solution (Python):

import sys


sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush


sys.setrecursionlimit(10 ** 7)





from collections import deque



INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())

def bfs(MAP, queue):

    while queue:
        turn, ci, cj = queue.popleft()
        for ii, jj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            ni = ci + ii
            nj = cj + jj
            if MAP[ni][nj] == 0:
                MAP[ni][nj] = 1
                queue.append((turn + 1, ni, nj))
    return turn


def run():
    H, W = map(int, input().split())
    queue = deque([])
    MAP = [[1] * (W+2)]
    d = {'
    for i in range(1, H+1):
        X = input()
        S = [1]
        for j, s in enumerate(X, 1):
            S.append(d[s])
            if s == '
                queue.append((0, i, j))
        S.append(1)
        MAP.append(S)

    
    MAP.append([1] * (W+2))

    print(bfs(MAP, queue))


if __name__ == "__main__":
    
    run()

Solution (Python):
from collections import deque

H, W = map(int, input().split())
s_l = [input() for _ in range(H)]
dist = [(1, 0), (-1, 0), (0, 1), (0, -1)]
queue = deque()
results = []
for y, s in enumerate(s_l):
    result = []
    for x, p in enumerate(s):
        result.append(False if p == "." else True)
        if p == "
            queue.append((y, x))
    results.append(result)

count = 0
while queue:
    starts = []
    while queue:
        starts.append(queue.popleft())
    for y, x in starts:
        for dy, dx in dist:
            ny = y + dy
            nx = x + dx
            if ny < 0 or ny >= H or nx < 0 or nx >= W:
                continue
            if s_l[ny][nx] == "." and not results[ny][nx]:
                queue.append((ny, nx))
                results[ny][nx] = True
    if queue:
        count += 1

print(count)

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline
h, w = map(int, input().rstrip("\n").split())
matrix = [[-1 for j in range(w)] for i in range(h)]
queue = deque()
for i in range(h):
    cells = list(input().rstrip("\n"))
    for j, cell in enumerate(cells):
        if cell == "
            matrix[i][j] = 0
            queue.append((i, j))
while queue:
    i, j = queue.popleft()
    for i_diff, j_diff in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
        i_current = i + i_diff
        j_current = j + j_diff
        if (
            0 <= i_current < h
            and 0 <= j_current < w
            and matrix[i_current][j_current] == -1
        ):
            matrix[i_current][j_current] = matrix[i][j] + 1
            queue.append((i_current, j_current))

max_step = max([max(row) for row in matrix])
print(max_step)

Solution (Python):
from collections import deque

def cal():
    h, w = map(int, input().split())
    q = deque()
    counts = [[True for _ in range(w+2)]]+[[True]+[False]*w+[True] for _ in range(h)]+[[True for _ in range(w+2)]]
    for i in range(h):
        a = input()
        for j in range(w):
            if a[j] == '
                q.append([i+1, j+1, 0])
                counts[i+1][j+1] = True

    while q:
        x, y, z = q.popleft()    
        if not counts[x+1][y]:
            counts[x+1][y] = True
            q.append([x+1, y, z+1])
        if not counts[x-1][y]:
            counts[x-1][y] = True
            q.append([x-1, y, z+1])
        if not counts[x][y+1]:
            counts[x][y+1] = True
            q.append([x, y+1, z+1])
        if not counts[x][y-1]:
            counts[x][y-1] = True
            q.append([x, y-1, z+1])
    print(z)
    

cal()

Solution (Python):
from collections import deque
def main():
    h,w = map(int,input().split())
    S = [list(input()) for i in range(h)]
    q = [(i,j) for i,a in enumerate(S) for j,b in enumerate(a) if b=='
    q = deque(q)
    ans = 0
    s = h*w
    cnt = len(q)
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt < s:
        ans += 1
        q_ = deque([])
        while q:
            a,b = q.pop()
            for x,y in nxt:
                X,Y = a+x,b+y
                if 0>X or X>h-1 or 0>Y or Y>w-1:
                    continue
                if S[X][Y]=='.':
                    S[X][Y]='
                    q_.append((X,Y))
        q = q_
        cnt += len(q_)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))



H,W=mint()
A=[input() for _ in range(H)]
C=[[0]*W for _ in range(H)]
for i,j in product(range(H),range(W)):
    if A[i][j]=='.':
        C[i][j]=INF
for i,j in product(range(H),range(1,W)):
    C[i][j] = min(C[i][j],C[i][j-1]+1)
for i,j in product(range(1,H),range(W)):
    C[i][j] = min(C[i][j],C[i-1][j]+1)
for i,j in product(range(H),range(W-2,-1,-1)):
    C[i][j] = min(C[i][j],C[i][j+1]+1)
for i,j in product(range(H-2,-1,-1),range(W)):
    C[i][j] = min(C[i][j],C[i+1][j]+1)
print(max([max(c) for c in C]))

Solution (Python):
h,w=map(int,input().split())
A=[list(input()) for i in range(h)]
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict 
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal as D  
  
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
from fractions import Fraction as F  






queue=deque([])
seen=[[0]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if A[i][j]=="
            queue.append([i,j,0])
            seen[i][j]=1

dx=[1,0,-1,0];dy=[0,1,0,-1]
while queue:
    x,y,t=queue.pop()
    for i,j in zip(dx,dy):
        if 0<=x+i<h and 0<=y+j<w and seen[x+i][y+j]==0:
            queue.appendleft([x+i,y+j,t+1])
            seen[x+i][y+j]=1
print(t)

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

def main():
    h, w = map(int, input().split())

    a = [input()[:-1] for i in range(h)]

    already = [[False]*w for i in range(h)]
    key = deque([])
    for i in range(h):
        for j in range(w):
            if a[i][j] == '
                if not key:
                    judge = (i, j)
                key.append((i, j))
                already[i][j] = True
    
    ans = -1
    way = [(-1, 0), (1, 0), (0, 1), (0, -1)]
    change = False
    while key:
        value = key.popleft()
        if value == judge:
            ans += 1
            judge = value
            change = True
        i, j = value
        for x, y in way:
            p, q = i+x, j+y
            if 0 <= p < h and 0 <= q < w  and not already[p][q]:
                already[p][q] = True
                key.append((p, q))
                if change:
                    judge = (p, q)
                    change = False

    print(ans)







    
if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque


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

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

    black = deque()
    for r in range(h):
        for c in range(w):
            if graph[r][c] == "
                black.append((r, c))
                dist[r][c] = 0

    while black:
        r, c = black.popleft()
        ans = max(ans, dist[r][c])
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nr = r + dr
            nc = c + dc
            if not (0 <= nr < h and 0 <= nc < w):
                continue
            if dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                black.append((nr, nc))

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

H,W=map(int,input().split())
field=[]
dist=[[-1]*W for _ in range(H)]
que=deque()

for i in range(H):
    tmp=list(input())
    for j in range(W):
        if tmp[j]=="
            dist[i][j]=0
            que.append([i,j])
    field.append(tmp)

DX=[1,0,-1,0]
DY=[0,1,0,-1]
ans=0
while que:
    y,x=map(int,que.popleft())
    ans=dist[y][x]
    for dx,dy in zip(DX,DY):
        nx=x+dx
        ny=y+dy
        if nx<0 or nx>=W or ny<0 or ny>=H: continue
        if dist[ny][nx]==-1:
            dist[ny][nx]=dist[y][x]+1
            que.append([ny,nx])

print(ans)

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

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

for sy in range(H):
    for sx in range(W):
        if D[sy][sx] == "
            Q.append((sx,sy))
            dist[sy][sx] = 0
while Q:
    x,y = Q.popleft()
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0<=nx<=W-1 and 0<=ny<=H-1 and dist[ny][nx] == -1 and D[ny][nx] == ".":
            Q.append((nx,ny))
            dist[ny][nx] = dist[y][x]+1

for y in range(H):
    for x in range(W):
        if D[y][x] == ".":
            ans = max(ans,dist[y][x])
print(ans)

Solution (Python):
from collections import deque

h,w=map(int,input().split())
INF=float('inf')
G=[]
for _ in range(h):
  s=input()
  S=[]
  for i in range(w):
    S.append(s[i])
  G.append(S)
  
dist=[[INF for i in range(w)] for j in range(h)]
Q=deque()
for i in range(h):
  for j in range(w):
    if G[i][j]=='
      dist[i][j]=0
      Q.append((i,j))
while Q:
  pi,pj=Q.popleft()
  for di,dj in [[-1,0],[1,0],[0,-1],[0,1]]:
    ni,nj=pi+di,pj+dj
    if 0>ni or ni>h-1:
      continue
    if 0>nj or nj>w-1:
      continue
    if G[ni][nj]=='
      continue
    if dist[ni][nj]>dist[pi][pj]+1:
      dist[ni][nj]=dist[pi][pj]+1
      Q.append((ni,nj))
ans=-INF
for i in range(h):
  for j in range(w):
    ans=max(ans,dist[i][j])
print(ans)

Solution (Python):
import collections
import math
import copy

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

A=[list(str(input())) for i in range(H)]

d=[[-1 for j in range(W)]for i in range(H)]
inf=10**6
ans=0
queue=collections.deque()
for i in range(H):
    for j in range(W):
        if A[i][j]=='
            queue.append([i,j])
            d[i][j]=0

moves=[[1,0],[-1,0],[0,1],[0,-1]]

nax=0
while len(queue)>0:
    now=queue.popleft()
    for i in range(4):
        ny=now[0]+moves[i][0]
        nx=now[1]+moves[i][1]
        if 0<=ny and ny<H and 0<=nx and nx<W and A[ny][nx]=='.' and d[ny][nx]==-1:
            d[ny][nx]=d[now[0]][now[1]]+1
            nax=max(nax,d[ny][nx])
            queue.append([ny,nx])


print(nax)

Solution (Python):
from collections import deque

def clamp(a,b,c):
  return min(max(a,b),c)

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

D = [[-1]*W for _ in range(H)]
dd = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque()
res = 0

for i in range(H):
  for j in range(W):
    if A[i][j] == "
      D[i][j] = 0
      Q.append([i,j,0])
      
while len(Q)>0:
  x,y,n = Q.popleft()
  for dx,dy in dd:
    xx = clamp(x+dx,0,H-1)
    yy = clamp(y+dy,0,W-1)
    if D[xx][yy] == -1:
      D[xx][yy] = n+1
      Q.append([xx,yy,n+1])
      res = n+1
      
print(res)

Solution (Python):
from collections import deque

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

def BFS(H, W, grid):
    visited = [[True for _ in range(W+2)] for _ in range(H+2)]
    que = deque()
    for i in range(H):
        visited[i+1][1:-1] = map(lambda _:_=="
        for j in range(W):
            if(grid[i][j] == "
                que.append((i+1, j+1, 0))
    dist = [(0, 1), (-1, 0), (0, -1), (1, 0)]
        
    while que:
        x, y, c = que.popleft()
        for dx, dy in dist:
            nx = x + dx
            ny = y + dy
            
            if(not visited[nx][ny]):
                que.append((nx, ny, c+1))
                visited[nx][ny] = True
    return c
        
print(BFS(H, W, grid))

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

dis = [[1000000 for _ in range(w)] for _ in range(h)]
queue = deque([])

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

while queue:
    now = deque.popleft(queue)
    if now[0] != 0:
        if dis[now[0]-1][now[1]] == 1000000:
            dis[now[0]-1][now[1]] = dis[now[0]][now[1]]+1
            queue.append([now[0]-1, now[1]])
            
    if now[0] != h-1:
        if dis[now[0]+1][now[1]] == 1000000:
            dis[now[0]+1][now[1]] = dis[now[0]][now[1]]+1
            queue.append([now[0]+1, now[1]])
            
    if now[1] != 0:
        if dis[now[0]][now[1]-1] == 1000000:
            dis[now[0]][now[1]-1] = dis[now[0]][now[1]]+1
            queue.append([now[0], now[1]-1])
            
    if now[1] != w-1:
        if dis[now[0]][now[1]+1] == 1000000:
            dis[now[0]][now[1]+1] = dis[now[0]][now[1]]+1
            queue.append([now[0], now[1]+1])

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

print(ans)

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

dist = [[-1]*W for _ in range(H)]
black_cells = deque()


for h in range(H):
  for w in range(W):
    if grid[h][w]=="
      black_cells.append((h,w))
      dist[h][w] = 0
def bfs(black_cells, dist):
  count=0
  while black_cells:
    h,w = black_cells.popleft()
    count = dist[h][w]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_h = h + dy
        new_w = w + dx
        if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
          continue
        if dist[new_h][new_w] == -1:
          dist[new_h][new_w] = count+1
          black_cells.append((new_h,new_w))
  return count
print(bfs(black_cells,dist))

Solution (Python):
from collections import deque

inf=float('inf')

h,w=map(int,input().split())
maze=[]
st=[]
for j in range(h):
  a=list(input())
  for i in range(w):
    if a[i]=='.':
      a[i]=inf
    if a[i]=='
      a[i]=0
      st.append([j,i])
  maze.append(a)
  
de=deque(st)

while de:
  v=de.popleft()
  sy,sx=v[0],v[1]
  for p in ([1,0],[0,1],[-1,0],[0,-1]):
    ny,nx=sy+p[0],sx+p[1]
    if 0<=ny<=h-1 and 0<=nx<=w-1 and maze[ny][nx]!=0:
      if maze[ny][nx]>maze[sy][sx]+1:
        maze[ny][nx]=maze[sy][sx]+1
        de.append([ny,nx])

ans=0
for g in range(h):
  for f in range(w):
    ans=max(maze[g][f],ans)

print(ans)