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())
grid = [input() for i in range(h)]

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

black = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            black.append((i, j))
            dist[i][j] = 0

def bfs(black, dist):
    d = 0
    while black:
        x, y = black.popleft()
        d = dist[x][y]
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            nx = x + dx
            ny = y + dy
            if not(0 <= nx < h) or not(0 <= ny < w):
                continue
            if dist[nx][ny] == -1:
                dist[nx][ny] = d+1
                black.append((nx, ny))
    return d

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

Submission status: Accepted

Solution code:
from collections import deque

row, col = map(int, input().split())
graph = [list(input()) for i in range(row)]

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

seen = deque([])
finished = deque([])

for i in range(row):
  for j in range(col):
    if graph[i][j] == "#":
      finished.append([i, j])
      
while True:

  while len(finished) > 0:
    v = finished.popleft()
    for j in range(4):
      next_y, next_x = v[0]+dy[j], v[1]+dx[j]
      if not 0 <= next_y < row or not 0 <= next_x < col:
        continue
      if graph[next_y][next_x] == '#':
        continue 

      graph[next_y][next_x] = "#"
      seen.append([next_y, next_x])
  
  if len(seen) == 0:
    break
  seen, finished = deque([]), seen
  ans += 1
      
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
inf = 10 ** 6
a = [[0] * (w + 2)] + [[0] + [inf] * w + [0] for _ in range(h)] + [[0] * (w + 2)]
d = deque()

for i in range(h):
    for j, k in enumerate(input()):
        if k == "#":
            a[i + 1][j + 1] = 0
            d.append((i + 1, j + 1))

stp = ((0, 1), (0, -1), (1, 0), (-1, 0))
res = 0

while d:
    x, y = d.popleft()
    for k, l in stp:
        nx, ny = x + k, y + l
        if a[x][y] + 1 < a[nx][ny]:
            a[nx][ny] = a[x][y] + 1
            res = max(res, a[nx][ny])
            d.append((nx, ny))
print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
  h,w=map(int,input().split())
  a=[input() for _ in range(h)]
  seen=[[1]*w for _ in range(h)]
  from collections import deque
  todo=deque([])
  for hi,ai in enumerate(a):
    for wj,aij in enumerate(ai):
      if aij=='#':
        seen[hi][wj]=0
        todo.append((hi,wj))
  ans=-1
  while todo:
    ans+=1
    next_todo=[]
    for hi,wi in todo:
      if hi>0 and seen[hi-1][wi]:
        next_todo.append((hi-1,wi))
        seen[hi-1][wi]=0
      if hi<h-1 and seen[hi+1][wi]:
        next_todo.append((hi+1,wi))
        seen[hi+1][wi]=0
      if wi>0 and seen[hi][wi-1]:
        next_todo.append((hi,wi-1))
        seen[hi][wi-1]=0
      if wi<w-1 and seen[hi][wi+1]:
        next_todo.append((hi,wi+1))
        seen[hi][wi+1]=0
    todo=next_todo
  print(ans)
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[input() for _ in range(h)]
seen=[[-1]*w for _ in range(h)]
from collections import deque
todo=deque([])
for hi in range(h):
  for wi in range(w):
    if a[hi][wi]=='#':
      seen[hi][wi]=0
      todo.append((hi,wi,0))
while len(todo)>0:
  hi,wi,i=todo.popleft()
  if hi>0 and seen[hi-1][wi]==-1:
    todo.append((hi-1,wi,i+1))
    seen[hi-1][wi]=i+1
  if hi<h-1 and seen[hi+1][wi]==-1:
    todo.append((hi+1,wi,i+1))
    seen[hi+1][wi]=i+1
  if wi>0 and seen[hi][wi-1]==-1:
    todo.append((hi,wi-1,i+1))
    seen[hi][wi-1]=i+1
  if wi<w-1 and seen[hi][wi+1]==-1:
    todo.append((hi,wi+1,i+1))
    seen[hi][wi+1]=i+1
print(max([max(seeni) for seeni in seen]))

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
#template
H,W = inputlist()
graph = [0]*H
for i in range(H):
    graph[i] = list(input())
from collections import deque
que = deque()
seen = [[False]*W for _ in range(H)]
li = []
for x in range(H):
    for y in range(W):
        if graph[x][y] == '#':
            tp = (x,y)
            li.append(tp)
que.append(li)
dx = [1,0,-1,0]
dy = [0,1,0,-1]
count = 0
while len(que) != 0:
    l = que.popleft()
    lis = []
    for tup in l:
        xa = tup[0]
        ya = tup[1]
        for i in range(4):
            nx = xa + dx[i]
            ny = ya + dy[i]
            if nx >= H or ny >= W or nx < 0 or ny < 0:
                continue
            if graph[nx][ny] == '#':
                continue
            graph[nx][ny] = '#'
            lis.append((nx,ny))
    count+=1
    if len(lis) == 0:
        print(count-1)
        exit()
    que.append(lis)

Submission status: Accepted

Solution code:
from collections import deque


def BFS():
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[0 for _ in range(w)] for _ in range(h)]

    num=0
    queue=deque([])
    for i in range(h):
        for j in range(w):
            if A[i][j]=="#":
                queue.append([i,j])
                color[i][j]="gray"

    while len(queue)>0:
        a,b=queue.popleft()
        for c,d in [[1,0],[-1,0],[0,1],[0,-1]]:
            X,Y=a+c,b+d
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]=="white":
                    D[X][Y]=D[a][b]+1
                    num=max(num,D[X][Y])
                    color[X][Y]="gray"
                    queue.append([X,Y])
        color[a][b]="black"

    return num


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

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
graph = [[2000 for i in range(w)] for j in range(h)]
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False

#graph => そこまでの距離を保存した二次元配列　grid=>与えられた迷路
def bfs(que):
    finished = set()
    while que:
        x ,y = que.popleft()
        if y*w+x not in finished:
            finished.add(y*w+x)
            for n_x,n_y in [(x+1,y),(x,y+1),(x-1,y),(x,y-1)]:
                if check(n_y,n_x) and graph[n_y][n_x] > graph[y][x] + 1:
                    graph[n_y][n_x] = graph[y][x] + 1
                    que.append((n_x,n_y))
for i in range(h):
    grid.append(list(input()))
que = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            graph[i][j] = 0
            que.append((j,i))
bfs(que)
ans = 0
for i in range(h):
    ans = max(ans, max(graph[i]))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

black_idx = []
for h in range(H):
    for w in range(W):
        if A[h][w] == "#":
            black_idx.append([h,w])

distance = [[float("inf")]*W for _ in range(H)]
for b in black_idx:
    distance[b[0]][b[1]] = 0

d = deque(black_idx)
ans = 0

while d:
    y, x = d.popleft()
    for new_y, new_x in ([y+1, x], [y, x+1], [y-1, x], [y, x-1]):
        if 0 <= new_y <= H-1 and 0 <= new_x <= W-1 and distance[y][x] + 1 < distance[new_y][new_x]:
            distance[new_y][new_x] = distance[y][x] + 1
            ans = max(ans, distance[y][x] + 1)
            d.append([new_y, new_x])

print(ans)

Submission status: Accepted

Solution code:
#AGC033-A Darker and Darker
"""
愚直にbfs(queueが無くなるまで)
"""
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

#迷路plane
H,W = map(int,readline().split())
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]

def bfs(lst):
    deq = deque(lst)
    ans = 0
    while deq:
        h,w,now = deq.popleft()
        for a,b in [(0,1),(1,0),(0,-1),(-1,0)]:
            if not (0 <= h+a < H and 0 <= w+b < W):continue
            if maze[h+a][w+b]=="#":continue
            else:
                maze[h+a][w+b] = "#"
                ans = max(ans,now+1)
                deq.append([h+a,w+b,now+1])
    return ans

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

print(bfs(lst1))

Submission status: Accepted

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

#まずは#を0、.をinfにして初期化
for i in range(H):
    for j in range(W):
        if A[i][j]==".":
            A[i][j]=float("inf")
        else:
            A[i][j]=0
#上下左右に値を流し、最小を格納することで、暗黒からの最短距離を出せるはず
for i in range(H):
    for j in range(0,W-1):
        A[i][j+1]=min(A[i][j+1],A[i][j]+1)
#print(A)
for i in range(H):
    for j in range(W-1,0,-1):
        A[i][j-1]=min(A[i][j-1],A[i][j]+1)
#print(A)
for j in range(W):
    for i in range(0,H-1):
        A[i+1][j] = min(A[i+1][j], A[i][j] + 1)
#print(A)
for j in range(W):
    for i in range(H-1,0,-1):
        A[i-1][j] = min(A[i-1][j], A[i][j] + 1)
#pprint.pprint(A)
ma=0
for i in range(H):
    for j in range(W):
        ma=max(ma,A[i][j])
print(ma)

Submission status: Accepted

Solution code:
from collections import deque

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

black_idx = [(h,w) for h in range(H) for w in range(W) if A[h][w] == "#"]

distance = [[float("inf")]*W for _ in range(H)]
for b in black_idx:
    distance[b[0]][b[1]] = 0

d = deque(black_idx)
ans = 0

while d:
    y, x = d.popleft()
    for new_y, new_x in ([y+1, x], [y, x+1], [y-1, x], [y, x-1]):
        if 0 <= new_y <= H-1 and 0 <= new_x <= W-1 and distance[y][x] + 1 < distance[new_y][new_x]:
            distance[new_y][new_x] = distance[y][x] + 1
            ans = max(ans, distance[y][x] + 1)
            d.append([new_y, new_x])

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

black_idx = []
for h in range(H):
    for w in range(W):
        if A[h][w] == "#":
            black_idx.append([h,w])

distance = [[float("inf")]*W for _ in range(H)]
for b in black_idx:
    distance[b[0]][b[1]] = 0

d = deque(black_idx)
ans = 0

while d:
    y, x = d.popleft()
    for new_y, new_x in ([y+1, x], [y, x+1], [y-1, x], [y, x-1]):
        if 0 <= new_y <= H-1 and 0 <= new_x <= W-1 and distance[y][x] + 1 < distance[new_y][new_x]:
            distance[new_y][new_x] = distance[y][x] + 1
            ans = max(ans, distance[y][x] + 1)
            d.append([new_y, new_x])

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

black_idx = []
for h in range(H):
    for w in range(W):
        if A[h][w] == "#":
            black_idx.append([h,w])

distance = [[float("inf")]*W for _ in range(H)]
for b in black_idx:
    distance[b[0]][b[1]] = 0

d = deque(black_idx)
ans = 0

while d:
    y, x = d.popleft()
    for new_y, new_x in ([int(y)+1, int(x)], [int(y), int(x)+1], [int(y)-1, int(x)], [int(y), int(x)-1]):
        if 0 <= new_y <= H-1 and 0 <= new_x <= W-1 and distance[y][x] + 1 < distance[new_y][new_x]:
            distance[new_y][new_x] = distance[y][x] + 1
            ans = max(ans, distance[y][x] + 1)
            d.append([new_y, new_x])

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

d = deque()
op = [[-1] * w for i in range(h)]

for i in range(h):
    s = input().rstrip()
    for j in range(len(s)):
        if s[j] == '#':
            d.append((i, j, 0))
            op[i][j] = 0

while d:
    i, j, step = d.popleft()

    for i2, j2 in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
        if 0 <= i2 < h and 0 <= j2 < w:
            if op[i2][j2] == -1:
                d.append((i2, j2, step+1))
                op[i2][j2] = step + 1

print(max([max(op[i]) for i in range(h)]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

H, W = map(int, input().split())
grid = (np.array([list(input())
                  for _ in range(H)]) == "#")
cost = np.full((H, W), 10 ** 9, dtype=np.int64)
cost[grid[:, :]] = 0

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

for i in range(H - 2, -1, -1):
    cost[i] = np.minimum(cost[i], cost[i + 1] + 1)

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

for i in range(W - 2, -1, -1):
    cost[:, i] = np.minimum(cost[:, i], cost[:, i + 1] + 1)

print(np.max(cost))

Submission status: Accepted

Solution code:
## coding: UTF-8


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

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

fresh = [True] * (H*W)
#print(fresh)


queue = []
n = []
for i in range(H):
    for j in range(W):
        if(c[i][j] == '#'):
            fresh[i*W+j] = False
            queue.append(i*W+j)
#print('initial')
#print('fresh:{}'.format(fresh))
#print('queue:{}'.format(queue))

step = 0
status = True
while status:
    if(len(queue)>0):
        #処理を行う
        pivot = queue.pop()
        #print('pivot:{}, queue:{}, n:{}'.format(pivot, queue, n))        
        #右へ移動
        if(pivot%W != W-1 and fresh[pivot+1]):
            n.append(pivot+1)
            fresh[pivot+1] = False
        #左へ移動
        if(pivot%W != 0 and fresh[pivot-1]):
            n.append(pivot-1)
            fresh[pivot-1] = False
        #下へ移動
        if( int(pivot/W)<(H-1) and fresh[pivot+W]):
            n.append(pivot+W)
            fresh[pivot+W] = False
        #上へ移動
        if( int(pivot/W)>0 and fresh[pivot-W] ):
            n.append(pivot-W)
            fresh[pivot-W] = False
        #print('pivot:{}, queue:{}, n:{}'.format(pivot, queue, n))
    elif(len(n)>0):
        queue = n
        n = []
        #歩数を増やそう
        step += 1
        #print('step{}end,queue:{}, n:{}'.format(step, queue, n))
    else:
        status = False


print(step)

Submission status: Accepted

Solution code:
from collections import deque
 
h,w = map(int,input().split())
s = [None]*h
 
for i in range(h):
    s[i] = input()
 
d = [[10000000 for i in range(w)] for j in range(h)]
sharp = 0
 
sx = []
sy = []
            
dx = [1,0,-1,0]
dy = [0,1,0,-1]
 
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            sx.append(j)
            sy.append(i)
            d[i][j] = 0
            
            
def bfs():
    que = deque()
    ans = 0
    for i in range(len(sx)):
        que.append([sy[i],sx[i]])
    
    while que:
        y,x = que.popleft()
        
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            
            if 0<=nx and nx<w and 0<=ny and ny<h and d[ny][nx] == 10000000:
                if d[ny][nx] > d[y][x]+1:
                    d[ny][nx] = d[y][x]+1
                    que.append([ny,nx])
                    
                    if d[ny][nx] > ans:
                        ans = d[ny][nx]
    
    print(ans)
        
bfs()

Submission status: Accepted

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

dist = [[-1]*W for i in range(H)]
dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      dist[i][j] = 0
      que.append((i, j))

d = 0
while que:
  y, x = que.popleft()
  d = dist[y][x]
  for dx, dy in dd:
    nx = x + dx; ny = y + dy
    if not 0 <= nx < W or not 0 <= ny < H or dist[ny][nx] != -1:
      continue
    dist[ny][nx] = d + 1
    que.append((ny, nx))

print(d)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
fields = [list(map(lambda c: c == '#', input())) for _ in range(H)]

checking = []
for i, row in enumerate(fields):
    for j, elem in enumerate(row):
        if elem:
            checking.append( (i, j) )

counter = 0
while True:
    to_check = []
    for y, x in checking:
        for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            if 0 <= x+dx < W and 0 <= y+dy < H and not fields[y+dy][x+dx]:
                fields[y+dy][x+dx] = True
                to_check.append( (y+dy, x+dx) )

    if not to_check:
        break
    checking = to_check
    counter += 1

print(counter)

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    H,W=map(int,input().split())
    A=[[] for _ in range(H+2)]
    A[0]=A[H+1]=['#']*(W+2)
    black=[]
    for i in range(1,H+1):
        row=list(input())
        A[i]=['#']+row+['#']
        for j,cell in enumerate(row):
            if cell=='#':
                black.append([i,j+1])
    nextcells=[]
    nextcells.extend(black)
    c=-1
    dx=[0,1,0,-1]
    dy=[1,0,-1,0]
    while nextcells:
        c+=1
        cells=[]
        cells.extend(nextcells)
        nextcells=[]
        for cell in cells:
            for k in range(4):
                if A[cell[0]+dy[k]][cell[1]+dx[k]]=='.':
                    nextcells.append([cell[0]+dy[k],cell[1]+dx[k]])
                    A[cell[0]+dy[k]][cell[1]+dx[k]]='#'
    print(c)
        

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 = [input().rstrip() for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
queue = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            dist[i][j] = 0
            queue.append((i, j))
while queue:
    i, j = queue.popleft()
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i+di, j+dj
        if 0 <= ni < H and 0 <= nj < W and dist[ni][nj] == -1:
            dist[ni][nj] = dist[i][j] + 1
            queue.append((ni, nj))
print(max(max(row) for row in dist))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
A = [input().rstrip() for _ in range(H)]
dp = [[float('inf') if A[i][j] == '.' else 0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if i > 0:
            dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
        if j > 0:
            dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)
for i in range(H)[::-1]:
    for j in range(W)[::-1]:
        if i < H-1:
            dp[i][j] = min(dp[i][j], dp[i+1][j] + 1)
        if j < W-1:
            dp[i][j] = min(dp[i][j], dp[i][j+1] + 1)
for i in range(H):
    for j in range(W)[::-1]:
        if i > 0:
            dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
        if j < W-1:
            dp[i][j] = min(dp[i][j], dp[i][j+1] + 1)
for i in range(H)[::-1]:
    for j in range(W):
        if i < H-1:
            dp[i][j] = min(dp[i][j], dp[i+1][j] + 1)
        if j > 0:
            dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)
print(max(max(row) for row in dp))

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input():return sys.stdin.readline().strip()

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

    field = "#" * (W+2)
    field += "#" + "##".join([input() for _ in range(H)]) + "#"
    field += "#" * (W+2)

    move = [-1, 1, -(W+2), W+2]
    cost = [-1] * (H+2) * (W+2)

    def dfs(s):
        q = deque()
        enqueue = q.append
        dequeue = q.popleft

        for v in s:
            cost[v] = 0
            enqueue(v)

        while q:
            now = dequeue()
            cost_now = cost[now]
            for dx in move:
                nv = now + dx
                if field[nv] == "." and cost[nv] < 0:
                    cost[nv] = cost_now + 1
                    enqueue(nv)
    
    starts = [i*(W+2)+j for j in range(1, W+1) for i in range(1, H+1) if field[i*(W+2)+j] == "#"]
    dfs(starts)

    print(max(cost))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

C = [[-1 for w in range(W)] for h in range(H)]


start = deque([])
for h in range(H):
    for w in range(W):
        if A[h][w] == "#":
            start.append([h,w])
            C[h][w] = 0
            
while start:
    h,w = start.popleft()
    c_old = C[h][w]
    
    if h > 0:
        c_new = C[h-1][w]
        
        if c_new == -1:
            C[h-1][w] = c_old+1
            start.append([h-1,w])
            
    if w > 0:
        c_new = C[h][w-1]
        
        if c_new == -1:
            C[h][w-1] = c_old+1
            start.append([h,w-1])
            
    if w < W-1:
        c_new = C[h][w+1]
        
        if c_new == -1:
            C[h][w+1] = c_old+1
            start.append([h,w+1])
            
    if h < H-1:
        c_new = C[h+1][w]
        
        if c_new == -1:
            C[h+1][w] = c_old+1
            start.append([h+1,w])
            
            
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans,C[h][w])
        
        
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
que = deque()
A = [[0 for i in range(W)] for j in range(H)]
white_num = 0
for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == '.':
            A[i][j] = -1
            white_num += 1
        elif S[j] == '#':
            A[i][j] = 0
            que.append([j, i])

ans = 0
while len(que) > 0:
    x, y = que.popleft()
    for k in range(4):
        nx = x + [1, 0, -1, 0][k]
        ny = y + [0, 1, 0, -1][k]
        if nx < 0 or ny < 0 or nx >= W or ny >= H:
            continue
        if A[ny][nx] == -1:
            que.append([nx, ny])
            A[ny][nx] = A[y][x] + 1
            ans = max(ans, A[ny][nx])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
# H,Wの向きに注意
H,W=map(int,input().split())
A=[input() for i in range(H)]
ans=0
V=[[0 for i in range(W)] for j in range(H)]

def bfs(q):
    tmp=deque(q)
    ch = [[False for i in range(W)] for j in range(H)]
    count = 0
    d=[[-1,0],[1,0],[0,-1],[0,1]]
    while tmp:
        x,y=tmp.popleft()
        for a,b in d:
            nx=x+a
            ny=y+b
            if 0<=nx<H and 0<=ny<W:
                if ch[nx][ny]!=True and A[nx][ny]==".":
                    V[nx][ny]=V[x][y]+1
                    ch[nx][ny]=True
                    tmp.append([nx,ny])
            else:
                continue
ju=[]
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            ju.append([i,j])
bfs(ju)
for i in range(H):
    for j in range(W):
        if not A[i][j]=="#":
             ans=max(ans,V[i][j])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [input() for _ in range(h)]
inf = 10 ** 7

d = [[inf for _ in range(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

while que:
    px, py = que.popleft()
    for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        qx, qy = px + dx, py + dy
        if 0 <= qx < h and 0 <= qy < w:
            if d[qx][qy] > d[px][py] + 1:
                d[qx][qy] = d[px][py] + 1
                que.append((qx, qy))

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

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

H, W = map(int, input().split())
field = []
q = deque()
for i in range(H):
    line = []
    A = input()
    for j in range(W):
        if A[j] == ".":
            line.append(True)
        else:
            line.append(False)
            q.append(((j, i), 0))
    field.append(line)

dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]

ans = 0

while len(q) != 0:
    (x, y), d = q.popleft()
    ans = max(d, ans)
    for dir in dirs:
        nx = x + dir[0]
        ny = y + dir[1]
        if 0 <= nx <= W - 1 and 0 <= ny <= H - 1 and field[ny][nx]:
            field[ny][nx] = False
            q.append(((nx, ny), d+1))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def mbfs(S,H,W,d):
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    while(len(d)!=0):
        h=d[0][0]
        w=d[0][1]
        x=d[0][2]
        d.popleft()
        for di in range(4):
            nh=h+dx[di]
            nw=w+dy[di]
            if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                continue
            if(S[nh][nw]=='#'):
                continue
            S[nh][nw]='#'
            d.append([nh,nw,x+1])
    return x
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
d=deque()
for i in range(H):
    for j in range(W):
        if(A[i][j]=='#'):
            d.append([i,j,0])
print(mbfs(A,H,W,d))

Submission status: Accepted

Solution code:
from collections import deque
def mbfs(S,H,W):
    dxy=[[1,0],[0,1],[-1,0],[0,-1]]
    while(len(d)!=0):
        h,w,x=d.popleft()
        for t,y in dxy:
            if(0<=h+t<=H-1 and 0<=w+y<=W-1 and S[h+t][w+y]!='#'):
                S[h+t][w+y]='#'
                d.append([h+t,w+y,x+1])
    return x
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
d=deque()
for i in range(H):
    for j in range(W):
        if(A[i][j]=='#'):
            d.append([i,j,0])
print(mbfs(A,H,W))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[]

from collections import deque
fifo = deque()
a.append(["@"]*(w+2))
for i in range(h):
    s=input()
    temp=["@"]
    for j in range(w):
        if s[j]=="#":
            fifo.append([i+1,j+1])
            temp.append(0)
        else:
            temp.append(s[j])
    temp.append("@")
    a.append(temp)
a.append(["@"]*(w+2))

result=0
#print(a)

while len(fifo)>0:
    temp=fifo.popleft()
    y,x=temp[0],temp[1]

    for item in [[0,1],[1,0],[-1,0],[0,-1]]:
        #print(y+item[0],x+item[1])
        if a[y+item[0]][x+item[1]]==".":
            fifo.append([y+item[0],x+item[1]])
            a[y+item[0]][x+item[1]]=a[y][x]+1
            result=max(result,a[y+item[0]][x+item[1]])
    
print(result)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

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


from collections import deque
todo = deque()
seen = [[False] * W for _ in range(H)]
for y in range(H):
    for x in range(W):
        if A[y][x] == '#':
            todo.append((x, y))
            seen[y][x] = True

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
cnt = -1
while todo:
    cnt += 1
    for _ in range(len(todo)):
        x, y = todo.popleft()
        for i in range(4):
            if 0 <= x + dx[i] < W and 0 <= y + dy[i] < H:
                if seen[y + dy[i]][x + dx[i]] == False:
                    seen[y + dy[i]][x + dx[i]] = True
                    todo.append((x + dx[i], y + dy[i]))

print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

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


from collections import deque
todo = deque()
seen = [[False] * W for _ in range(H)]
route= [[0] * W for _ in range(H)]
for y in range(H):
    for x in range(W):
        if A[y][x] == '#':
            todo.append((x, y))
            seen[y][x] = True



dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
cnt = -1
while todo:
    cnt += 1
    for _ in range(len(todo)):
        x, y = todo.popleft()
        #print(x, y)
        for i in range(4):
            if 0 <= x + dx[i] < W and 0 <= y + dy[i] < H:
                if seen[y + dy[i]][x + dx[i]] == False:
                    route[y + dy[i]][x + dx[i]] = route[y][x] + 1
                    seen[y + dy[i]][x + dx[i]] = True
                    todo.append((x + dx[i], y + dy[i]))

#print(seen)
# print(route)
# M = 0
# for y in range(H):
#     for x in range(W):
#         M = max(M, route[y][x])
# print(M)
print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

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


from collections import deque
todo = deque()
seen = [[False] * W for _ in range(H)]
route= [[0] * W for _ in range(H)]
for y in range(H):
    for x in range(W):
        if A[y][x] == '#':
            todo.append((x, y))
            seen[y][x] = True



dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
cnt = 0
while todo:
    for _ in range(len(todo)):
        x, y = todo.popleft()
        #print(x, y)
        for i in range(4):
            if 0 <= x + dx[i] < W and 0 <= y + dy[i] < H:
                if seen[y + dy[i]][x + dx[i]] == False:
                    route[y + dy[i]][x + dx[i]] = route[y][x] + 1
                    seen[y + dy[i]][x + dx[i]] = True
                    todo.append((x + dx[i], y + dy[i]))
    # cnt += 1

#print(seen)
# print(route)
M = 0
for y in range(H):
    for x in range(W):
        M = max(M, route[y][x])
print(M)