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



Sample input:
3 3
...
.#.
...


Sample output:
2

Submission status: Accepted

Solution code:
from collections import deque

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

queue = deque()
visited = [[-1] * w for _ in range(h)]
for row in range(h):
    for col in range(w):
        if a[row][col] == "#":
            visited[row][col] = 0
            queue.append((row, col, 0))
dist = 0
while queue:
    row, col, dist = queue.popleft()
    for drow, dcol in move:
        if row+drow>=0 and row+drow<h and col+dcol>=0 and col+dcol<w and visited[row+drow][col+dcol] == -1 and a[row+drow][col+dcol] == ".":
            visited[row+drow][col+dcol] = dist + 1
            queue.append((row+drow, col+dcol, dist+1))


print(dist)

Submission status: Accepted

Solution code:
from collections import deque

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

queue = deque()
visited = [[-1] * w for _ in range(h)]
for row in range(h):
    for col in range(w):
        if a[row][col] == "#":
            visited[row][col] = 0
            queue.append((row, col, 0))
dist = 0
while queue:
    row, col, dist = queue.popleft()
    for drow, dcol in move:
        if a[row+drow:row+drow+1] and a[row+drow][col+dcol:col+dcol+1] and visited[row+drow][col+dcol] == -1 and a[row+drow][col+dcol] == ".":
            visited[row+drow][col+dcol] = dist + 1
            queue.append((row+drow, col+dcol, dist+1))


print(dist)

Submission status: Accepted

Solution code:
from scipy.ndimage import distance_transform_cdt
H,W=map(int, input().split())
S=list(list(input()) for h in range(H))
for h in range(H):
    for w in range(W):
        if S[h][w]=="#":
            S[h][w]=0
        else:
            S[h][w]=1

print(distance_transform_cdt(S, metric='taxicab').max())

Submission status: Accepted

Solution code:
from subprocess import call
call(('pypy3','-c',"""
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
dy=[0,0,1,-1]
dx=[1,-1,0,0]
m=[[-1]*W for i in range(H)]

from collections import deque
q=deque()
for y in range(H):
  for x in range(W):
    if A[y][x]=='#':
      q.append((y,x))
      m[y][x]=0      
      
def bfs(q,m):
  d=0
  while q:
    y,x=q.popleft()
    d=m[y][x]
    for i in range(4):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W and m[ny][nx]==-1 and A[ny][nx]!='#':
        q.append((ny,nx))
        m[ny][nx]=m[y][x]+1            
bfs(q,m)
ans=0
for i in range(H):
  for j in range(W):
    ans=max(ans,m[i][j])    
print(ans)     
"""))

Submission status: Accepted

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

que = deque()
seen = [[-1]*W for _ in range(H)]
max = 0



for i in range(H):
    for j in range(W):
        if map[i][j] == "#":
            que.append([i,j])
            seen[i][j] = 0

while que:
    #print(que)
    y, x = que.popleft()
    for dy, dx in ([0,1],[0,-1],[1,0],[-1,0]):
        ny = y + dy
        nx = x + dx
        if 0<=ny<H and 0<=nx<W and seen[ny][nx]==-1:
            seen[ny][nx] = seen[y][x] + 1
            que.append([ny,nx])
            if max < seen[ny][nx]:
                max = seen[ny][nx]

print(max)

Submission status: Accepted

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

from collections import deque
def bfs(maze):
    ans = 0
    d = [[-1] * w for _ in range(h)]
    que = deque([])
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '#':
                que.append([i, j])
                d[i][j] = 0
    #que = deque([[sy, sx]])
    #d[sy][sx] = 0
    while que:
        y, x = que.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            ny, nx = y + j, x + k
            if 0 <= nx < w  and 0 <= ny < h  and d[ny][nx] == -1 and maze[ny][nx] != "#":
                d[ny][nx] = d[y][x] + 1
                ans = max(ans, d[ny][nx])
                que.append([ny, nx])
                
    return ans

print(bfs(maze))

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
a=[list(input()) for i in range(H)]
#黒のマスを探索する
#黒のマスの周囲四マスを黒に変更する
log=[[-1]*W for i in range(H)]
def bfs():
    task=deque([])
    #初め黒のマスをキューに入れる
    for i in range(H):
        for j in range(W):
            if a[i][j]=='#':
                task.append((i,j))
                log[i][j]=0

    dh=[0,1,0,-1]
    dw=[1,0,-1,0]

    while task:
        h,w=task.popleft()
        #四マスを探索する
        for i in range(4):
            nh=h+dh[i]
            nw=w+dw[i]
            if not(0<=nh<H and 0<=nw<W):continue
            if a[nh][nw]=='#':continue
            a[nh][nw]='#'
            log[nh][nw]=log[h][w]+1
            task.append((nh,nw))

def ans_check():
    ans=0
    for i in range(H):
        for j in range(W):
            if ans<log[i][j]:ans=log[i][j]

    print(ans)

bfs()
ans_check()

Submission status: Accepted

Solution code:
from collections import deque

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

paint=((1,0),(-1,0),(0,1),(0,-1))
que=deque([])

dark=[[0]*W for _ in range(H)] # 1が黒、0はまだ白

for i in range(H): # 初期化(最初に黒いマスをdarkリストに入れて、キューに入れる。)
    for j in range(W):
        if S[i][j]=='#':
            que.append((i,j,0))
            dark[i][j]=1
ans=0
while len(que)>0:
    di,dj,c=que.popleft()
    
    for pi,pj in paint:
        ni,nj=pi+di,pj+dj # 移動先がni,nj
        if 0<=ni<H and 0<=nj<W and dark[ni][nj]==0:
            dark[ni][nj]=1
            que.append((ni,nj,c+1))
            ans=c+1
print(ans)

Submission status: Accepted

Solution code:

"""
メモ型再起？
ダイクストラじゃあきつそう
1sec!?

各点高々1回しか選ばれない工夫が必要
qにいれて少しづつ進めてく？
→各点高々4回しか選択されない
"""


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

A = []
q = []

for i in range(H):

    a = list(input())
    A.append(a)

    for j in range(W):
        if a[j] == "#":
            q.append([i,j])

ans = 0
while len(q) > 0:

    #print (q)
    
    nq = []
    flag = False

    for i,j in q:
        if i > 0 and A[i-1][j] == ".":
            A[i-1][j] = "#"
            nq.append([i-1,j])
            flag = True
        if i < H-1 and A[i+1][j] == ".":
            A[i+1][j] = "#"
            nq.append([i+1,j])
            flag = True
        if j > 0 and A[i][j-1] == ".":
            A[i][j-1] = "#"
            nq.append([i,j-1])
            flag = True
        if j < W-1 and A[i][j+1] == ".":
            A[i][j+1] = "#"
            nq.append([i,j+1])
            flag = True
    q = nq
    if flag:
        ans += 1


print (ans)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    H,W = list(map(int,input().split()))
    A = [["#"]*(W+2)]
    for i in range(H):
        A.append(list("#"+input()+"#"))
    A.append(["#"]*(W+2))

    queue = deque()
    for i in range(1,H+1):
        for j in range(1,W+1):
            if A[i][j] == "#":
                queue.append((i,j,0))

    ans = 0
    while queue:
        point = queue.popleft()
        ans = max(ans,point[2])
        for y,x in ((1,0),(0,1),(-1,0),(0,-1)):
            if A[point[0]+y][point[1]+x] == ".":
                A[point[0]+y][point[1]+x] = "#"
                queue.append((point[0]+y,point[1]+x,point[2]+1))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
h,w = map(int,input().split())
a = [list(input().rstrip()) for i in range(h)]
q = deque()
for i in range(h):
  for j in range(w):
    if a[i][j] == "#":
      a[i][j] = 0
      q.append((i,j,0))
    else:
      a[i][j] = -1
while q:
  s,t,cnt = q.popleft()
  for ns,nt in ((s+1,t),(s-1,t),(s,t+1),(s,t-1)):
    if 0<=ns<=h-1 and 0<=nt<=w-1 and a[ns][nt] == -1:
      q.append((ns,nt,cnt+1))
      a[ns][nt] = cnt+1
ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans,a[i][j])
print(ans)

Submission status: Accepted

Solution code:
# 迷路読み込み
h,w = map(int, input().split())
maze=[list(input()) for i in range(h)]

import collections
from collections import deque

INF = -10 ** 9
distance = [[INF for i in range(w)] for j in range(h)]
d = deque()
def bfs():
    cnt=0
    while len(d):
        x, y = d.pop()
        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

            if (0 <= nx <=h-1) and (0 <= ny<=w-1) and (distance[nx][ny] == INF):
                d.appendleft((nx, ny))
                distance[nx][ny] = distance[x][y] + 1
                if cnt<distance[nx][ny]:
                    cnt=distance[nx][ny]

    return cnt


for i in range(h):
    for j in range(w):
        if maze[i][j]=='#':
            d.append((i,j))
            distance[i][j]=0
print(bfs())

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[list(S()) for _ in range(h)]
  d=0

  q=collections.deque()
  nokori=h*w
  dist=[[-1]*w for _ in range(h)]
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        q.append((i,j))
        dist[i][j]=0
        nokori-=1

  while q:
    if nokori==0:
      return d

    y,x=q.popleft()

    for dy,dx in dd:
      ny=y+dy
      nx=x+dx

      if 0<=ny and ny<h and 0<=nx and nx<w:
        if field[ny][nx]=='.':
          field[ny][nx]='#'
          d=dist[y][x]+1
          dist[ny][nx]=d
          q.append((ny,nx))
          nokori-=1

  return d

# main()
print(main())

Submission status: Accepted

Solution code:
from collections import deque


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

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

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

que = deque()
flag = False
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            que.append((i, j))
            checked[i][j] = True
        else:
            flag = True

if flag is False:
    print('0')
    exit()

n_que = deque()
step = 0
while len(que):

    h, w = que[0][0], que[0][1]
    que.popleft()
    for d in range(4):
        nh, nw = h + dy[d], w + dx[d]
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        if checked[nh][nw] is True:
            continue
        n_que.append((nh, nw))
        checked[nh][nw] = True

    if len(que) == 0:
        if len(n_que) == 0:
            print(step)
            exit()
        que = n_que
        n_que = deque()
        step += 1

Submission status: Accepted

Solution code:
from collections import deque
#import numpy as np

H, W = map(int, input().split())
d = [[-1]*W for i in range(H)]
#temp = [[float("inf")]*W for i in range(H)]
maze = [list(input()) for i in range(H)]

black_cells = deque()
for i in range(H):
    for j in range(W):
        if maze[i][j]=="#":
            black_cells.append((i,j))
            d[i][j] = 0

def bfs():
    #max = 0
    #dx = [1, 0, -1, 0]
    #dy = [0, 1, 0, -1]

    #que = deque([])
    s = 0
    while black_cells:
        p, q = black_cells.popleft()
        s = d[p][q]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            nx = q + dx
            ny = p + dy
            #a = temp[ny][nx]
            if 0<=nx<W and 0<=ny<H and d[ny][nx]==-1:
                #que.append((nx))
                #temp[ny][nx] = d[p[0]][p[1]] + 1
                #a = temp[ny][nx]
                #d[ny][nx] = d[p[0]][p[1]] + 1
                #if a < d[ny][nx]:
                black_cells.append((ny, nx))
                d[ny][nx] = s + 1
                    #if max < d[ny][nx]:
                        #max = d[ny][nx]

    return s






#for i in slist:
#    s = bfs(i[0], i[1])

print(bfs())
#print(s)

Submission status: Accepted

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

from collections import deque
def solve():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    Q = deque()

    cnt=h*w
    for x in range(w):
        for y in range(h):
            if l[y][x]=="#":
                cnt-=1
                Q.append([x,y])
    if cnt==0:
        return 0

    ans=0
    while True:
        nxtQ = deque()

        ans+=1
        while Q:
            p = Q.popleft()
            for i in range(4):
                nx = p[0] + dx[i]
                ny = p[1] + dy[i]

                if 0 <= nx < w and 0 <= ny < h:
                    if l[ny][nx]==".":
                        l[ny][nx] = "#"
                        nxtQ.append([nx,ny])
                        cnt-=1
        Q=nxtQ
        if cnt<=0:
            return ans

print(solve())

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())

l = [input() for i in range(h)]
memo = [[-1]*w for i in range(h)]

black_cells = deque()
for i in range(h):
    for j in range(w):
        if l[i][j] == "#":
            black_cells.append((i, j))
            memo[i][j] = 0

count = 0
while black_cells:
    nh, nw = black_cells.popleft()
    count = memo[nh][nw]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_nh = nh + dy
        new_nw = nw + dx
        if new_nh < 0 or h <= new_nh or new_nw < 0 or w <= new_nw:
            continue
        if memo[new_nh][new_nw] == -1:
            memo[new_nh][new_nw] = count + 1
            black_cells.append((new_nh, new_nw))
print(count)

Submission status: Accepted

Solution code:
# BFS
from collections import deque


def main():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    # 頂点数と辺数
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    # 全頂点を未訪問に初期化
    dist = [[-1] * W for _ in range(H)]

    ans = float('inf')
    que = deque()
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                que.append([h, w])
                dist[h][w] = 0

    # bfs開始 (キューが空になるまで探索を行う)
    while len(que) > 0:
        v = que.popleft()  # キューから先頭頂点を取り出す
        for i in range(4):
            nx = v[0] + dx[i]
            ny = v[1] + dy[i]
            if (0 <= nx and nx < H and 0 <= ny and ny < W and dist[nx][ny] == -1):
                que.append([nx, ny])
                dist[nx][ny] = dist[v[0]][v[1]] + 1
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, dist[h][w])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    h, w = map(int, input().split())
    # 蛮兵
    painted = [['#'] * (w + 2)]
    painted += [['#'] + list(input().rstrip()) + ['#'] for _ in range(h)]
    painted.append(['#'] * (w + 2))
    que = []

    for y in range(1, h + 1):
        for x in range(1, w + 1):
            if painted[y][x] == '#':
                painted[y][x] = 0
                que.append((y, x))
    while que:
        qq = []
        for y, x in que:
            if painted[y - 1][x] == '.':
                painted[y - 1][x] = painted[y][x] + 1
                qq.append((y - 1, x))
            if painted[y + 1][x] == '.':
                painted[y + 1][x] = painted[y][x] + 1
                qq.append((y + 1, x))
            if painted[y][x + 1] == '.':
                painted[y][x + 1] = painted[y][x] + 1
                qq.append((y, x + 1))
            if painted[y][x - 1] == '.':
                painted[y][x - 1] = painted[y][x] + 1
                qq.append((y, x - 1))
        que = qq

    print(painted[y][x])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    H, W = list(map(int, input().split()))
    c = [input() for j in range(H)]
    from collections import deque
    que = deque()
    dist = [[-1]*W for i in range(H)]
    for h in range(H):
        for w in range(W):
            if c[h][w] == "#":
                que.append((h, w))
                dist[h][w] = 0
 
    def bfs():
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        while que:
            # popleftにすれば、手の短い方が優先されているので、それで訪れられる所は全て確定でいい。
            # 探索するところが無くなるまで続ける。
            cy, cx = que.popleft()
            for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                ny, nx = cy+dy, cx+dx
                if 0 <= ny < H and 0 <= nx < W and dist[ny][nx] == -1 and c[ny][nx] == '.':
                    dist[ny][nx] = dist[cy][cx] + 1
                    que.append((ny, nx))
 
    bfs()
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, dist[h][w])
    print(ans)
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    H, W = (int(i) for i in input().split())
    c = [input() for j in range(H)]
    from collections import deque
    que = deque()
    dist = [[-1]*W for i in range(H)]
    for h in range(H):
        for w in range(W):
            if c[h][w] == "#":
                que.append((h, w))
                dist[h][w] = 0

    def bfs():
        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 c[next_y][next_x] == '#':
                    continue
                dist[next_y][next_x] = dist[uy][ux] + 1
                que.append((next_y, next_x))

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
h,w=map(int,input().split())
a=[]
for i in range(h):
  a.append([0 if i=='#' else h+w for i in list(input())])
a=np.array(a)
for i in range(h-1):
  a[i+1,:]=np.minimum(a[i,:]+1,a[i+1,:])
for i in range(h-1,0,-1):
  a[i-1,:]=np.minimum(a[i,:]+1,a[i-1,:])
for i in range(w-1):
  a[:,i+1]=np.minimum(a[:,i]+1,a[:,i+1])
for i in range(w-1,0,-1):
  a[:,i-1]=np.minimum(a[:,i]+1,a[:,i-1])
print(np.max(a))

Submission status: Accepted

Solution code:
from collections import deque
H, W = [int(i) for i in input().split()]
A = [input() for _ in range(H)]
seen = [[False]*W for _ in range(H)]
ans = 0
dq = deque([])
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            dq.append((i, j, 0))
            seen[i][j] = True
while len(dq):
    x, y, d = dq.popleft()
    ans = max(ans, d)
    for nx, ny in [(x-1, y), (x+1, y), (x, y+1), (x, y-1)]:
        if 0 <= nx < H and 0 <= ny < W:
            if not seen[nx][ny]:
                dq.append((nx, ny, d+1))
                seen[nx][ny] = True
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = int(1e09) + 7
INF = int(1e15)


def calc(N):
    return sum(int(x) for x in str(N))


def main():
    # sys.stdin = open("sample.txt")
    H, W = Scanner.map_int()
    S = Scanner.string_list(H)
    F = [[False for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if S[h][w] == "#":
                F[h][w] = True
    ans = 0
    q = []
    for h in range(H):
        for w in range(W):
            if S[h][w] == "#":
                q.append((w, h))
    while q != []:
        r = []
        for n in q:
            DIR = [(-1, 0), (1, 0), (0, 1), (0, -1)]
            for d in DIR:
                x, y = n[0] + d[0], n[1] + d[1]
                if 0 <= x < W and 0 <= y < H:
                    if F[y][x] == False:
                        F[y][x] = True
                        r.append((x, y))
        if r == []:
            break
        q = r
        ans += 1
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
h, w = [int(x) for x in input().strip().split()]
g = [[x for x in list(input().strip())] for _ in range(h)]

ans = -1
q = []
for i in range(h):
    for j in range(w):
        if g[i][j] == '#':
            q.append((i, j))
vec = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while q:
    q_ = deque(q)
    q = deque([])
    ans += 1
    while q_:
        i, j = q_.pop()
        for x, y in vec:
            ti, tj = i+x, j+y
            if 0 <= ti < h and 0 <= tj < w:
                if g[ti][tj] == '.':
                    g[ti][tj] = '#'
                    q.append((ti, tj))
print(ans)

Submission status: Accepted

Solution code:
from subprocess import call
call (('pypy3', '-c', """
from collections import deque
 
def main():
    h, w = map(int, input().split())
    A = [list(input()) for _ in range(h)]
    d = [[10**9] * w for _ in range(h)]
    que = deque([])
    
    for i in range(h):
        for j in range(w):
           if A[i][j] == "#":
               que.append([i, j])
               d[i][j] = 0
           else:
               d[i][j] = 10 ** 9
            
    while que:
        x, y = que.popleft()
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and d[nx][ny] == 10**9:
                d[nx][ny] = d[x][y] + 1
                que.append([nx, ny])
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, d[i][j])
    print(ans)
    
    return
    
main()
 
"""))

Submission status: Accepted

Solution code:
from subprocess import call
call (('pypy3', '-c', """
from collections import deque

def main():
    h, w = map(int, input().split())
    A = [list(input()) for _ in range(h)]
    d = [[10**9] * w for _ in range(h)]
    que = deque([])
    
    for i in range(h):
        for j in range(w):
           if A[i][j] == "#":
               que.append([i, j])
               d[i][j] = 0
           else:
               d[i][j] = 10 ** 9
            
    while que:
        x, y = que.popleft()
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and d[nx][ny] == 10**9:
                d[nx][ny] = d[x][y] + 1
                que.append([nx, ny])
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, d[i][j])
    print(ans)
    
    return
    
main()

"""))

Submission status: Accepted

Solution code:
from itertools import product
from collections import deque

H, W = [int(i) for i in input().split()]
grid = [list(input()) for _ in range(H)]
reached = [[0] * W for _ in range(H)]

queue = deque()
for y, x in product(range(H), range(W)):
    if grid[y][x] == "#":
        queue.append((y, x, 0))

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

while queue:
    y, x, steps = queue.popleft()
    for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        ny, nx = y + dy, x + dx
        if not (0 <= ny < H and 0 <= nx < W):
            continue
        if reached[ny][nx]:
            continue
        reached[ny][nx] = 1
        queue.append((ny, nx, steps+1))
print(steps)

Submission status: Accepted

Solution code:
import copy
from collections import deque
def main():
  H, W = map(int, input().split())
  G = [['#' == x for x in input()] for _ in range(H)]
 
  black = deque([(i, j) for i in range(H) for j in range(W) if G[i][j]])
 
  ans = 0
  while True:
    ans += 1
    next_black = deque()
    while black:
      bi, bj = black.popleft()
      if bi > 0 and not G[bi - 1][bj]:
        G[bi - 1][bj] = True
        next_black.append((bi - 1, bj))
      if bj > 0 and not G[bi][bj - 1]:
        G[bi][bj - 1] = True
        next_black.append((bi, bj - 1))
      if bi < H - 1 and not G[bi + 1][bj]:
        G[bi + 1][bj] = True
        next_black.append((bi + 1, bj))
      if bj < W - 1 and not G[bi][bj + 1]:
        G[bi][bj + 1] = True
        next_black.append((bi, bj + 1))
    if next_black:
       black = copy.copy(next_black)
    else:
       break
  print(ans - 1)
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
A = [input() for _ in range(h)]
dist = [[-1]*w for _ in range(h)]
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
que = deque()
for i in range(h):
  for j in range(w):
    if A[i][j] == "#":
      que.append((i, j))
      dist[i][j] = 0
ans = 0
while que:
  y, x = que.popleft()
  for dy, dx in zip(di, dj):
    ny, nx = y+dy, x+dx
    if ny < 0 or ny >= h or nx < 0 or nx >= w:
      continue
    if dist[ny][nx] != -1:
      continue
    dist[ny][nx] = dist[y][x] + 1
    ans = max(ans, dist[ny][nx])
    que.append((ny, nx))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
A = [input() for _ in range(h)]
dist = [[-1]*w for _ in range(h)]
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
que = deque()
for i in range(h):
  for j in range(w):
    if A[i][j] == "#":
      que.append((i, j))
      dist[i][j] = 0
while que:
  y, x = que.popleft()
  for dy, dx in zip(di, dj):
    ny, nx = y+dy, x+dx
    if ny < 0 or ny >= h or nx < 0 or nx >= w:
      continue
    if dist[ny][nx] != -1:
      continue
    dist[ny][nx] = dist[y][x] + 1
    que.append((ny, nx))
ans = 0
for i in dist:
  ans = max(ans, max(i))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
stack=[]
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            stack.append([h,w,0])

stack=deque(stack)
value=0
while stack:
    h,w,m=stack.popleft()
    lst=[]
    if h>0:lst.append([-1,0])
    if h<H-1:lst.append([1,0])
    if w>0:lst.append([0,-1])
    if w<W-1:lst.append([0,1])
    n=m+1
    for y1,x1 in lst:
        Y=h+y1
        X=w+x1
        if A[Y][X]==".":
            A[Y][X]="#"
            stack.append([Y,X,n])
            if value<n:
                value=n
print(value)

Submission status: Accepted

Solution code:
import copy
from collections import deque
def main():
  H, W = map(int, input().split())
  M = [['#' == x for x in input()] for _ in range(H)]

  black = deque([(i, j) for i in range(H) for j in range(W) if M[i][j]])

  ans = 0
  while True:
    ans += 1
    next_black = deque()
    while black:
      bi, bj = black.popleft()
      if bi > 0 and not M[bi - 1][bj]:
        M[bi - 1][bj] = True
        next_black.append((bi - 1, bj))
      if bj > 0 and not M[bi][bj - 1]:
        M[bi][bj - 1] = True
        next_black.append((bi, bj - 1))
      if bi < H - 1 and not M[bi + 1][bj]:
        M[bi + 1][bj] = True
        next_black.append((bi + 1, bj))
      if bj < W - 1 and not M[bi][bj + 1]:
        M[bi][bj + 1] = True
        next_black.append((bi, bj + 1))
    if next_black:
       black = copy.copy(next_black)
    else:
       break
  print(ans - 1)
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
A = [list(input().strip()) for _ in range(H)]
que = deque([])
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            que.append((i,j,0))
tot = 0
while que:
    i,j,cnt = que.popleft()
    if j+1<W and A[i][j+1]==".":
        A[i][j+1]="#"
        que.append((i,j+1,cnt+1))
        tot = cnt+1
    if j-1>-1 and A[i][j-1]==".":
        A[i][j-1]="#"
        que.append((i,j-1,cnt+1))
        tot = cnt+1
    if i+1<H and A[i+1][j]==".":
        A[i+1][j]="#"
        que.append((i+1,j,cnt+1))
        tot = cnt+1
    if i-1>-1 and A[i-1][j]==".":
        A[i-1][j]="#"
        que.append((i-1,j,cnt+1))
        tot = cnt+1
print(tot)