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

Solution (Python):

import sys
from collections import deque


sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def main():
    BLACK = '
    WHITE = '.'
    H, W = map(int, input().split())
    graph = [None] * H
    
    
    options = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    visited = [[False for i in range(W)] for i in range(H)]
    initial = []

    for i in range(H):
        graph[i] = list(input())

        for j in range(W):
            if graph[i][j] == BLACK:
                initial.append((i, j))
                visited[i][j] = True

    
    

    q = deque()
    q.append(initial)
    ans = 0
    while len(q) != 0:
        n = q.popleft()
        

        items = set()
        for p in n:
            for d in options:
                i = p[0] + d[0]
                j = p[1] + d[1]

                if i >= 0 and i < H and j >= 0 and j < W and not visited[i][j] and graph[i][j] == WHITE:
                    visited[i][j] = True
                    graph[i][j] = BLACK
                    items.add((i, j))
                
                

        if len(items) > 0:
            ans += 1
            q.append(items)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):



from collections import Counter,deque


from sys import stdin,setrecursionlimit







setrecursionlimit(10**6)
input=stdin.readline

h,w=map(int,input().split())
a=[list(input()) for _ in range(h)]
d=[[False]*w for _ in range(h)]
dx=[1,-1,0,0]
dy=[0,0,1,-1]
q=deque()
nowi=[]
ans=0

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

while len(q):
    nowq=q.popleft()
    nextq=[]
    
    for i in nowq:
        ny,nx=i
        for yx in range(4):
            if ny+dy[yx]<0 or ny+dy[yx]>=h:
                continue
            if nx+dx[yx]<0 or nx+dx[yx]>=w:
                continue
            if d[ny+dy[yx]][nx+dx[yx]]:
                continue
            nextq.append((ny+dy[yx],nx+dx[yx]))
            d[ny+dy[yx]][nx+dx[yx]]=True
    if len(nextq):
        q.append(nextq)
        ans+=1
    
print(ans)

Solution (Python):
import math

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors







h,w = list(map(int, input().split()))
queue=[]
mp=[[-1 for i in range(h)]for j in range(w)]
for i in range(h):
    temp = input()
    for j in range(len(temp)):
        if(temp[j]=='
            queue.append([j,i,0])
            mp[j][i]=0
            
nowq = 0
while(True):
    x,y,times = queue[nowq]
    if(mp[min(x+1,w-1)][y]==-1):
        mp[min(x+1,w-1)][y]=times+1
        queue.append([x+1,y,times+1])
    if(mp[max(x-1,0)][y]==-1):
        mp[max(x-1,0)][y]=times+1
        queue.append([x-1,y,times+1])
    if(mp[x][min(y+1,h-1)]==-1):
        mp[x][min(y+1,h-1)]=times+1
        queue.append([x,y+1,times+1])
    if(mp[x][max(y-1,0)]==-1):
        mp[x][max(y-1,0)]=times+1
        queue.append([x,y-1,times+1])
    nowq+=1
    if(len(queue)==nowq):
        break
ans=0
for i in range(w):
    ans=max(ans,max(mp[i]))
print(ans)

Solution (Python):
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, readline().split()))
    a = [list(str(readline().rstrip().decode('utf-8'))) for _ in range(h)]
    fq = [[True] * w for _ in range(h)]
    ql = collections.deque()
    for i in range(h):
        for j in range(w):
            if a[i][j] == "
                fq[i][j] = False
                ql.append([0, i, j])
    mt = 0
    while True:
        if len(ql) != 0:
            cost, x, y = ql.popleft()
            mt = max(mt, cost)
            for xv, yv in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if fq[xv][yv]:
                        ql.append([cost + 1, xv, yv])
                        fq[xv][yv] = False
        else:
            break
    print(mt)


if __name__ == '__main__':
    solve()

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

field = [] 
mark = [] 
INF = 10**6

for i in range(h):
    field.append(list(input()))
    mark.append([0 for i in range(w)])

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

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

while len(queue) > 0:
    y, x = queue.popleft()
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= ny < h and 0 <= nx < w:
            if field[ny][nx] == ".":
                mark[ny][nx] = mark[y][x] + 1
                queue.append([ny, nx])
                field[ny][nx] = "

ans=0

for i in mark:
    ans = max(ans, max(i))

print(ans)

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

field=[]
m=[]
INF=10**6

for i in range(h):
    row=list(input())
    field.append(row)
    m.append([INF for i in range(w)])

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

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

while len(queue)>0:
    y,x=queue.popleft()
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=ny<h and 0<=nx<w:
            if m[ny][nx]>m[y][x]+1 and field[ny][nx]==".":
                m[ny][nx]=m[y][x]+1
                queue.append([ny,nx])
                field[ny][nx]="

ans=0

for i in range(h):
    ans=max(ans,max(m[i]))

print(ans)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
q=deque()
l=[]
for i in range(h):
  l.append(list(input()))
lb=[[0 for i in range(w)] for j in range(h)]
for i in range(h):
  for j in range(w):
    if l[i][j]=="
      q.append([i,j])
move=[[1,0],[-1,0],[0,1],[0,-1]]
count=0
b=True
q2=deque()
while b:
  while q:
    q1=q.popleft()
    x1=q1[0]
    y1=q1[1]
    for i in range(4):
      dx=move[i][0]
      dy=move[i][1]
      x=x1+dx
      y=y1+dy
      if x<0 or x>h-1 or y<0 or y>w-1:
        pass
      elif l[x][y]=="
        pass
      else:
        l[x][y]="
        q2.append([x,y])
  if len(q2)!=0:
    q=q2
    q2=deque()
    count+=1
  else:
    b=False
print(count)

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

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

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

bfs()

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

Solution (Python):
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    h, w = list(map(int, readline().split()))
    a = [list(str(readline().rstrip().decode('utf-8'))) for _ in range(h)]
    ql = []
    ql = collections.deque(ql)
    for i in range(h):
        for j in range(w):
            if a[i][j] == "
                ql.append([0, i, j])

    mt = 0
    while True:
        if len(ql) != 0:
            cost, x, y = ql.popleft()
            mt = max(mt, cost)
            for xv, yv in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if a[xv][yv] == ".":
                        ql.append([cost + 1, xv, yv])
                        a[xv][yv] = "
        else:
            break
    print(mt)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    h, w = list(map(int, readline().split()))
    a = [[True] * w for _ in range(h)]
    ql = []
    ql = collections.deque(ql)
    for i in range(h):
        s = str(readline().rstrip().decode('utf-8'))
        for j in range(w):
            if s[j] == "
                a[i][j] = False
                ql.append([0, i, j])

    mt = 0
    while True:
        if len(ql) != 0:
            cost, x, y = ql.popleft()
            mt = max(mt, cost)
            for xv, yv in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if a[xv][yv]:
                        ql.append([cost + 1, xv, yv])
                        a[xv][yv] = False
        else:
            break
    print(mt)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    h, w = list(map(int, readline().split()))
    a = [[True] * w for _ in range(h)]
    ql = collections.deque()
    for i in range(h):
        s = list(str(readline().rstrip().decode('utf-8')))
        for j in range(w):
            if s[j] == "
                ql.append([0, i, j])
                a[i][j] = False
    while ql:
        cost, x, y = ql.popleft()
        for xv, yv in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
            if 0 <= xv < h and 0 <= yv < w:
                if a[xv][yv]:
                    ql.append([cost + 1, xv, yv])
                    a[xv][yv] = False
    print(cost)


if __name__ == '__main__':
    solve()

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

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):
    d = 0
    while black_cells:
        
        h, w = black_cells.popleft()  
        d = 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] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)

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

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

d = 0
while black_cells:
    
    h, w = black_cells.popleft()  
    d = 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] = d+1
            black_cells.append((new_h, new_w))

print(d)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
grid = [list(input()) for i 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, 0])

ans = 0
while len(black_cells) > 0:
    one_black_cell = black_cells.popleft()  
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = one_black_cell[0] + dy
        nw = one_black_cell[1] + dx
        d = one_black_cell[2]
        if nh < 0 or H <= nh or nw < 0 or W <= nw:
            continue
        if grid[nh][nw] == '.':
            grid[nh][nw] = '
            black_cells.append([nh, nw, d + 1])
        ans = d

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()

Solution (Python):
from collections import deque
H,W = map(int, input().split())
A = []
for _ in range(H):
    temp = list(input())
    A.append(temp)
ans = 0
Q = deque([])
break_loop = 1
def bfs(x,y):
    global break_loop
    next_ = [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]
    for i in next_:
        if 0 <= i[0] <= H-1 and 0 <= i[1] <= W-1 and A[i[0]][i[1]] == ".":
            break_loop = 0
            A[i[0]][i[1]] = "
            Q.append([i[0],i[1]])

for j in range(H):
    for k in range(W):
        if A[j][k] == "
            Q.append([j,k])

while len(Q) > 0:
    break_loop = 1
    for _ in range(len(Q)):
        Q_next = Q.popleft()
        bfs(Q_next[0],Q_next[1])
    if break_loop:
        break
    else:
        ans += 1
print(ans)

Solution (Python):
def main():
    H, W = map(int, input().split())
    field = [list(input()) for _ in range(H)]
    dd = ((1, 0), (-1, 0), (0, 1), (0, -1))

    q = []
    for i in range(H):
        for j in range(W):
            if field[i][j] == "
                q.append((i, j))
                field[i][j] = 0
    moves = 0

    while q:
        qn = []
        moves += 1
        for x, y in q:
            for dx, dy in dd:
                nx, ny = int(x + dx), int(y + dy)
                if 0 <= nx < H and 0 <= ny < W:
                    if field[nx][ny] == ".":
                        field[nx][ny] = moves
                        qn.append((nx, ny))

        q = qn

    m = []
    for i in range(H):
        m.append(max(field[i]))
    print(max(m))


main()

Solution (Python):

import sys
import heapq
from collections import deque
input = lambda: sys.stdin.buffer.readline()[:-1].decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

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


dis=[[-1]*w for i in range(h)]
hq=deque()
for i in range(h):
    for j in range(w):
        if A[i][j]=="
            hq.append((0,i,j))
            dis[i][j]=0
dii=[(1,0),(-1,0),(0,1),(0,-1)]

ans=0
while hq:
    count,i,j=hq.popleft()
    for di,dj in dii:
        if not (0<=i+di<h and 0<=j+dj<w):
            continue
        if dis[i+di][j+dj]==-1:
            hq.append((count+1, i+di, j+dj))
            dis[i+di][j+dj]=count+1
            ans=max(ans,count+1)




print(ans)

Solution (Python):
h,w = map(int,input().split())
a1 = [[5000] * (w+2) for i in range(h+2)]
a2 = [['.'] * (w+2) for i in range(h+2)]
for i in range(h):
  a2[i+1][1:-1] = list(input())
for i in range(h):
  for j in range(w):
    if a2[i+1][j+1] == '
      a1[i+1][j+1] = 0
for i in range(w):
  for j in range(h):
    a1[j+1][i+1] = min(a1[j][i+1]+1,a1[j+1][i+1])
for i in range(w):
  for j in range(h):
    a1[h-j][i+1] = min(a1[h-j+1][i+1]+1,a1[h-j][i+1])
for i in range(h):
  for j in range(w):
    a1[i+1][j+1] = min(a1[i+1][j]+1,a1[i+1][j+1])
for i in range(h):
  for j in range(w):
    a1[i+1][w-j] = min(a1[i+1][w-j+1]+1,a1[i+1][w-j])
m = 0
for i in range(h):
  for j in range(w):
    m = max(m,a1[i+1][j+1])
print(m)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
a=[input() for _ in range(h)]
inf=10**10
dist=[[inf if c=='.' else 0 for c in r] for r in a]
dq=deque()
for i in range(h):
    for j in range(w):
        if dist[i][j]==0:
            dq.append([i,j])
diff=[[1,0],[0,1],[-1,0],[0,-1]]
ans=0
while(dq):
    y,x=dq.popleft()
    for dy,dx in diff:
        y2=y+dy
        x2=x+dx
        if 0<=y2<h and 0<=x2<w and dist[y2][x2]>dist[y][x]+1:
            dq.append([y2,x2])
            dist[y2][x2]=dist[y][x]+1
            ans=max(ans,dist[y2][x2])
print(ans)

Solution (Python):


from collections import* 
from fractions import gcd
from functools import* 
from itertools import* 
from operator import mul
from bisect import* 
from heapq import* 
from math import factorial
from copy import deepcopy
import sys

sys.setrecursionlimit(10**6)



def main():
    h,w=map(int,input().split())
    stack=deque()
    grid=[["
    for i in range(h):
        tmp=[]
        for k,v in enumerate(input()):
            if v=="
                tmp.append("
                stack.appendleft((i+1,k+1))
            else:
                tmp.append(v)
        grid.append(["
    grid.append(["


    for i in range(h*w):
        tmp=deque()
        while stack:
            y,x=stack.pop()
            for my,mx in ((0,1),(1,0),(-1,0),(0,-1)):
                if grid[y+my][x+mx]==".":
                    grid[y+my][x+mx]="
                    tmp.appendleft((y+my,x+mx))
        stack=tmp
        if not len(stack):
            print(i)
            exit()
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
INF = 1001001001
dist = [[INF for _ in range(w)] for _ in range(h)]

d = deque()
for i in range(h):
    for j in range(w):
        if maze[i][j] == '
            d.append([i, j])
            dist[i][j] = 0
ans = 0
while(d):
    y,x = d.popleft()
    difflist = [[1,0], [0,1], [-1, 0], [0, -1]]
    for dy, dx in difflist:
        y2 = y + dy
        x2 = x + dx
        if 0 <= y2 < h and 0 <= x2 < w and dist[y2][x2]>(dist[y][x] + 1):
            d.append([y2, x2])
            dist[y2][x2] = dist[y][x] + 1
            ans = max(ans, dist[y2][x2])

print(ans)

Solution (Python):

import sys
import heapq
from collections import deque
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

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


dis=[[-1]*w for i in range(h)]
hq=deque()
for i in range(h):
    for j in range(w):
        if A[i][j]=="
            hq.append((0,i,j))
            dis[i][j]=0
dii=[(1,0),(-1,0),(0,1),(0,-1)]

ans=0
while hq:
    count,i,j=hq.popleft()
    for di,dj in dii:
        if not (0<=i+di<h and 0<=j+dj<w):
            continue
        if dis[i+di][j+dj]==-1:
            hq.append((count+1, i+di, j+dj))
            dis[i+di][j+dj]=count+1
            ans=max(ans,count+1)




print(ans)

Solution (Python):
h,w=map(int,input().split())
a=['*'*(w+2)]+['*'+input()+'*' for _ in range(h)]+['*'*(w+2)]
from collections import deque
d=deque()
c=[[0]*w for _ in range(h)]
for i in range(1,h+1):
  for j in range(1,w+1):
    if a[i][j]=='
      d.append([i,j])
di=[[0,1],[1,0],[-1,0],[0,-1]]
while d:
  g=d.popleft()
  for i in di:
    x=g[0]+i[0]
    y=g[1]+i[1]
    if a[x][y]=='.':
      if c[x-1][y-1]==0:
        d.append([x,y])
        c[x-1][y-1]=c[g[0]-1][g[1]-1]+1
m=0
for i in range(h):
  for j in range(w):
    m=max(m,c[i][j])
print(m)

Solution (Python):
from collections import deque
 
h, w = map(int, input().split())
s = [input() for i in range(h)]
 
d = [[h+w for j in range(w)] for i in range(h)]
que = deque()
 

for i in range(h):
  for j in range(w):
    if s[i][j]=='
        que.append((i, j))
        d[i][j] = 0
 
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
 
 
while que:
    p = que.popleft()
    
    for i in range(4):
        nx = p[1] + dx[i]
        ny = p[0] + dy[i]
 
        if (0<=nx<w) and (0<=ny<h) and (d[ny][nx]==h+w):
            que.append((ny, nx))
            d[ny][nx] = d[p[0]][p[1]] + 1
 
res = max(map(max, d))
print(res)

Solution (Python):
from collections import deque

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

d = [[10**6]*W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == "
            d[i][j] = 0
            q.append((i, j, 0))
            
while q:
    temp = q.popleft()
    y = temp[0]
    x = temp[1]
    r = temp[2]
    if y != 0:
        if d[y-1][x] > r+1 and A[y-1][x] == ".":
            d[y-1][x] = r+1
            q.append((y-1, x, r+1))
    if y != H-1:
        if d[y+1][x] > r+1 and A[y+1][x] == ".":
            d[y+1][x] = r+1
            q.append((y+1, x, r+1))
    if x != 0:
        if d[y][x-1] > r+1 and A[y][x-1] == ".":
            d[y][x-1] = r+1
            q.append((y, x-1, r+1))
    if x != W-1:
        if d[y][x+1] > r+1 and A[y][x+1] == ".":
            d[y][x+1] = r+1
            q.append((y, x+1, r+1))
                        
ans = 0
for i in range(H):
    ans = max(ans, max(d[i]))
    
print(ans)

Solution (Python):
def main():
    h,w = map(int,input().split())
    a=[]
    que=[]
    for _ in range(h):
        a.append(list(input()))
    for i in range(h):
        for j in range(w):
            if a[i][j]=="
                que.append([i,j])
                a[i][j]=0
    ans=0
    while que!=[]:
        tank=[]
        for i,j in que:
            if j<w-1 and a[i][j+1]==".":
                tank.append([i,j+1])
                a[i][j+1]=a[i][j]+1
            if 0<j and a[i][j-1]==".":
                tank.append([i,j-1])
                a[i][j-1]=a[i][j]+1
            if i<h-1 and a[i+1][j]==".":
                tank.append([i+1,j])
                a[i+1][j]=a[i][j]+1
            if 0<i and a[i-1][j]==".":
                tank.append([i-1,j])
                a[i-1][j]=a[i][j]+1
        que=tank
        ans+=1
    print(ans-1)
if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

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

matrix_list1 = deque()
cnt = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j] == "
            matrix_list1.append([i,j])

while len(matrix_list1) != 0:     
    for _ in range(len(matrix_list1)):
        x,y = matrix_list1.popleft()
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "
            matrix_list1.append([x+1,y])
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "
            matrix_list1.append([x-1,y])
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "
            matrix_list1.append([x,y+1])
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "
            matrix_list1.append([x,y-1])
    else:
        if len(matrix_list1) > 0:
            cnt += 1
    
print(cnt)

Solution (Python):



from collections import deque

h,w = map(int, input().split( ))
a = []
for _ in range(h):
    a_ = input()
    A =[]
    for i in range(w):
        A.append(a_[i])
    a.append(A)

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

Q = deque()

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

while Q:
    i,j = Q.popleft()
    for (k,l) in [(-1,0),(1,0),(0,-1),(0,1)]:
        if 0<=i+k and 0<=j+l and i+k<=h-1 and j+l<=w-1:
            if a[i+k][j+l]==".":
                a[i+k][j+l] ="
                cnt[i+k][j+l]=cnt[i][j]+1
                Q.append((i+k,j+l))
ans = 0
for i in range(h):
    ans = max(ans,max(cnt[i]))


print(ans)

Solution (Python):
from collections import deque

def main():
    h, w = map(int, input().split())
    G = [["
    dy, dx = [-1, 1, 0, 0], [0, 0, -1, 1]
    dist = [[-1 for j in range(w+2)] for i in range(h+2)]
    que = deque()
    
    for i in range(1, h+1):
        for j in range(1, w+1):
            if G[i][j] == "
                dist[i][j] = 0
                que.append((i, j))
    
    while (len(que) != 0):
        y, x = que[0][0], que[0][1]
        que.popleft()

        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if G[ny][nx] == "
                continue
            if dist[ny][nx] == -1:
                dist[ny][nx] = dist[y][x] + 1
                que.append((ny, nx))
    
    ans = 0
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            ans = max(ans, dist[i][j])
    print(ans)
if __name__ == "__main__":
    main()

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

H, W = map(int, line().split())
grid = np.full((H + 2, W + 2), 1000)
grid[1:-1, 1:-1] = (np.array([list(line().rstrip()) for _ in range(H)]).reshape(H, W) == '
grid2 = grid.copy()
grid2[1:-1, 1:-1] = np.where(grid2[1:-1, 1:-1] < 1, 1, 0)

down = grid.copy()
for i in range(1, H + 1):
    down[i, 1:-1] = (down[i - 1, 1:-1] * grid2[i - 1, 1:-1] + grid2[i, 1:-1]) * grid2[i, 1:-1]

up = grid.copy()
for i in range(H, 0, -1):
    up[i, 1:-1] = (up[i + 1, 1:-1] * grid2[i + 1, 1:-1] + grid2[i, 1:-1]) * grid2[i, 1:-1]

right = grid.copy()
for i in range(1, W + 1):
    right[1:-1, i] = (right[1:-1, i - 1] * grid2[1:-1, i - 1] + grid2[1:-1, i]) * grid2[1:-1, i]

left = grid.copy()
for i in range(W, 0, -1):
    left[1:-1, i] = (left[1:-1, i + 1] * grid2[1:-1, i + 1] + grid2[1:-1, i]) * grid2[1:-1, i]

v = np.minimum(down, up)
h = np.minimum(left, right)

answer = np.minimum(v, h)
for i in range(1, H):
    answer[i + 1] = np.minimum(answer[i] + 1, answer[i + 1])
for i in range(H, 0, -1):
    answer[i - 1] = np.minimum(answer[i] + 1, answer[i - 1])
print(int(answer[1:-1, 1:-1].max()))

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

state = []

for h in range(H):
    for w in range(W):
        if field[h][w] == "
            state.append([w, h])

tmp = []
ret = 0
while len(state) > 0:
    tmp = list()
    ret += 1
    for x, y in state:
        for nx, ny in ((1,0), (-1,0), (0,1), (0,-1)):
            nx += x
            ny += y
            if nx < 0 or ny < 0 or nx >= W or ny >= H:
                continue

            if field[ny][nx] == ".":
                field[ny][nx] = "
                tmp.append([nx, ny])
    state = tmp

print(ret-1)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
INF = 10**9
sheet = []
log = [[True]*W for i in range(H)]
step = [(-1,0),(1,0),(0,-1),(0,1)]
stuck = deque()
ans = 0

for i in range(H):
  line = input()
  for j in range(W):
    if line[j]=='
      stuck += [(i,j,0)]
      log[i][j] = False
      
while stuck:
  y, x, m = stuck.popleft()
  for s in step:
    dx, dy = s
    if x+dx<0 or x+dx>W-1 or y+dy<0 or y+dy>H-1:
      continue
    if log[y+dy][x+dx]:
      log[y+dy][x+dx]=False
      stuck += [(y+dy, x+dx, m+1)]
      if ans<m+1:
        ans = m+1
      
print(ans)

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

def bfs(s):
    score = [[-1 for _ in range(W)] for _ in range(H)]
    q = deque()
    for y , x in s:
        score[y][x] = 0
        q.append([y,x])
    diff = [[0,1],[1,0],[-1,0],[0,-1]]

    while q:
        now_y , now_x = q.popleft()
        for dy , dx in diff:
            next_y , next_x = now_y + dy , now_x + dx
            if 0 <= next_y and next_y < H and 0 <= next_x and next_x < W and score[next_y][next_x] == -1:
                score[next_y][next_x] = score[now_y][now_x] + 1
                q.append([next_y,next_x])
    ret_val = 0
    for i in range(H):
        for j in range(W):
            ret_val = max(ret_val , score[i][j])
    return ret_val


print(bfs(start))

Solution (Python):
from collections import deque
h,w=map(int,input().split())
ans=0
field=[["*" for i in range(w+2)]]+[["*"]+list(input())+["*"] for i in range(h)]+[["*" for i in range(w+2)]]
queue=deque([])
for H in range(h+2):
    for W in range(w+2):
        if field[H][W]=="
            queue.append((H,W))
            field[H][W]=0
        elif field[H][W]==".":
          field[H][W]=-1
move=[(0,1),(0,-1),(1,0),(-1,0)]
ans=0
while queue:
    pos=queue.popleft()
    for i in move:
      if field[pos[0]+i[0]][pos[1]+i[1]]!=-1:continue
      if field[pos[0]+i[0]][pos[1]+i[1]]=="*":continue
      field[pos[0]+i[0]][pos[1]+i[1]]=field[pos[0]][pos[1]]+1
      queue.append((pos[0]+i[0],pos[1]+i[1]))
      if ans < field[pos[0]+i[0]][pos[1]+i[1]]:ans=field[pos[0]+i[0]][pos[1]+i[1]]
print(ans)