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:
#初期地点
h,w = map(int,input().split())
n=[]
a=[]
a.append(["&"]*(w+2))
for i in range(h):
    arrc = list(input())
    arrc = ["&"]+arrc+["&"]
    b = arrc
    for j in range(len(arrc)):
        if b[j] == "#":
            n.append((i+1,j))
    a.append(b)
a.append(["&"]*(w+2))


#方向
p=[[1,0],[0,1],[-1,0],[0,-1]]
#距離のカウント
cnt=-1
#探索
while n:
    cnt +=1
    n2=[]
    #通った所で総当り
    for i,j in n:
        for di,dj in p:
            di +=i
            dj +=j
            if a[di][dj]==".":
                a[di][dj]="#"
                n2.append((di,dj))
    n=n2
print(cnt)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import collections


##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##
def main():
    H, W = rip()
    S = [rs() for i in range(H)]
    #min = np.full((H,W),-1, dtype = 'int')
    min = [[-1] * W for i in range(H)]
    q = collections.deque()
    def enc(h, w): return h * W + w
    def inRange(t, l, r): return l <= t and t < r
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]

    for i in range(H):
        for j in range(W):
            if S[i][j] == '#':
                q.append(enc(i,j))
                min[i][j] = 0
    while(len(q) > 0):
        rc = q.popleft()
        y = rc // W
        x = rc % W
        for t in range(4):
            nx = x + dx[t]
            ny = y + dy[t]
            if (not inRange(nx,0,W)) or (not inRange(ny,0,H)): continue
            if min[ny][nx] == -1:
                min[ny][nx] = min[y][x] + 1
                q.append(enc(ny,nx))
    
    ma = 0
    for i in range(H):
        for j in range(W):
            ma = max(ma, min[i][j])
    print(ma)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
import copy
 
def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]
 
 
    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()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
H,W=map(int,input().split())


def dfs(h,w):
    A[h][w]="#"
    que=[]
    if h>0:
        if A[h-1][w]!="#":
            que.append([h-1,w])
            A[h-1][w]="#"
    if w>0:
        if A[h][w-1]!="#":
            que.append([h,w-1])
            A[h][w-1]="#"
    if h<H-1:
        if A[h+1][w]!="#":
            que.append([h+1,w])
            A[h+1][w]="#"
    if w<W-1:
        if A[h][w+1]!="#":
            que.append([h,w+1])
            A[h][w+1]="#"
    
    return que


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

#print(A)

ans=0
lis=[]
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            lis.append([h,w])
while True:
    pre=[]
    if lis:
        N=len(lis)
        lis=lis[::-1]
        for i in range(N):
            item=lis.pop(-1)
            pre+=dfs(item[0],item[1])
        lis=pre
    if len(lis)==0:
        break
    ans+=1
    #print(lis)
    #print(A)
    
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 collections import deque

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

check = [[-1 for _ in range(W)] for _ in range(H)]
q = deque()
for i in range(H):
  for j in range(W):
    if  A[i][j] == "#":
      check[i][j] = 0
      q.append((i, j))

while q:
  i, j = q.popleft()
  
  if i - 1 >= 0 and check[i - 1][j] == -1:
      check[i - 1][j] = check[i][j] + 1
      q.append((i - 1, j))

  if i + 1 < H and check[i + 1][j] == -1:
      check[i + 1][j] = check[i][j] + 1
      q.append((i + 1, j))

  if j - 1 >= 0 and check[i][j - 1] == -1:
      check[i][j - 1] = check[i][j] + 1
      q.append((i, j - 1))

  if j + 1 < W and check[i][j + 1] == -1:
      check[i][j + 1] = check[i][j] + 1
      q.append((i, j + 1))

answer = -1
for i in range(H):
  answer = max(answer, max(check[i]))
print(answer)

Submission status: Accepted

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

from collections import deque

def main():
  h,w=map(int,input().split())
  #global mp
  mp=[list(input()) for _ in range(h)]
  #global dist
  dist=[[-1]*w for i in range(h)]
  q=deque([])
  
  for i in range(h):
    for j in range(w):
      if mp[i][j]=="#":
        dist[i][j]=0
        q.append([i,j])
      else:
        dist[i][j]=-1
  
  while q:
    x,y=q.popleft()
    for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
      xx,yy=x+i,y+j
      if (0<=xx<h and 0<=yy<w and dist[xx][yy]==-1):
        dist[xx][yy]=dist[x][y]+1
        q.append([xx,yy])
  
  ret=0
  for i in range(h):
    for j in range(w):
      ret=max(ret,dist[i][j])
      
  print(ret)
  return

main()


"""))

Submission status: Accepted

Solution code:
#writer:yutaka1999さんの見ながらPythonで写経 通るかな？一応O(HW)=O(10**6)らしいけど...？
#pypy3でだす
from collections import deque

def main():
  h,w=map(int,input().split())
  #global mp
  mp=[list(input()) for _ in range(h)]
  #global dist
  dist=[[-1]*w for i in range(h)]
  q=deque([])
  
  for i in range(h):
    for j in range(w):
      if mp[i][j]=="#":
        dist[i][j]=0
        q.append([i,j])
      else:
        dist[i][j]=-1
  
  while q:
    x,y=q.popleft()
    for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
      xx,yy=x+i,y+j
      if (0<=xx<h and 0<=yy<w and dist[xx][yy]==-1):
        dist[xx][yy]=dist[x][y]+1
        q.append([xx,yy])
  
  ret=0
  for i in range(h):
    for j in range(w):
      ret=max(ret,dist[i][j])
      
  print(ret)
  return

main()

Submission status: Accepted

Solution code:
#copipe
#1次元で格納

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

    used = [True]*(h*w)

    p = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                p.append(i*w+j)
                used[i*w+j] = False


    
    res = 0
    while p:
        tank = []
        for e in p:
            if e>w-1 and used[e-w]:
                tank.append(e-w)
                used[e-w] = False
            if e%w > 0 and used[e-1]:
                tank.append(e-1)
                used[e-1] = False
            if e<(h-1)*w and used[e+w]:
                tank.append(e+w)
                used[e+w] = False
            if e%w<w-1 and used[e+1]:
                tank.append(e+1)
                used[e+1] =  False
        p = tank
        res += 1
    print(res-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

    # 番兵法 (#を外周に設置する)
    visited = [[True]*(W+2)]
    visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
    visited.append([True]*(W+2))

    # #の位置をqに格納
    q = []
    for i in range(1,H+1):
        for j in range(1,W+1):
            if visited[i][j]:
                q.append((i,j))

    # dx,dyを使用せずにBFS 
    # 定数倍改善
    ans = -1
    while q:
        qq = []
        # 新たに#となった地点をqqに格納
        for x,y in q:
            if not visited[x-1][y]:
                visited[x-1][y] = True
                qq.append((x-1,y))
            if not visited[x+1][y]:
                visited[x+1][y] = True
                qq.append((x+1,y))
            if not visited[x][y-1]:
                visited[x][y-1] = True
                qq.append((x,y-1))
            if not visited[x][y+1]:
                visited[x][y+1] = True
                qq.append((x,y+1))
        q = qq
        ans += 1
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
  
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

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

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to only numbers
rs = lambda: stdin.readline().rstrip()  # ignores trailing space

H, W = rl()
A = [list(rs()) for _ in range(H)]

INF = 10 ** 5
B = np.array([[0 if x == '#' else INF for x in row] for row in A])

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

print(B.max())

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

H,W = map(int,readline().split())
INF = 10 ** 9
A = INF * (np.frombuffer(read(),'S1').reshape(H,-1)[:,:W] == b'.')

for _ in range(4):
    # 回転
    A = A.T[:,::-1]
    N = A.shape[0]
    for i in range(1,N):
        A[i] = np.minimum(A[i-1] + 1, A[i])

answer = A.max()
print(answer)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
H, W =  map(int, input().split(' '))
table = [list(input()) for _ in range(H)]

buf = []

n = 0
for i in range(H):
    for j in range(W):
        if table[i][j] == '#':
            buf.append((i, j))
            n += 1


ans = 0
while n != H * W:
    ans += 1

    buf2 = []
    for i, j in buf:
        if i-1 >= 0 and table[i-1][j] != '#':
            table[i - 1][j] = '#'
            buf2.append((i-1, j))
            n += 1

        if i+1 < H and table[i+1][j] != '#':
            table[i + 1][j] = '#'
            buf2.append((i+1, j))
            n += 1

        if j-1 >= 0 and table[i][j-1] != '#':
            table[i][j-1] = '#'
            buf2.append((i, j-1))
            n += 1

        if j+1 < W and table[i][j+1] != '#':
            table[i][j+1] = '#'
            buf2.append((i, j+1))
            n += 1

    buf = buf2

    # print('-- -- --')
    # print(buf)
    # for row in table:
    #     print(''.join(row))


print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

def main():
    input = sys.stdin.readline  
    H,W = map(int,input().split())
    isVisited = [[False]*W for _ in range(H)]
    queue = deque()

    for i in range(H):
        st = input()
        for j in range(W):
            if st[j] == "#":
                queue.append((i,j))

    answer = 0
    a =  [(0,1),(1,0),(-1,0),(0,-1)]
    while True:
        nqueue = deque()
        while queue:
            i,j = queue.popleft()

            if not isVisited[i][j]:
                isVisited[i][j] = True
                for ix,iy in a:
                    if 0<=i+ix<H and 0<=j+iy<W:
                        nqueue.append((i+ix,j+iy))
        
        if nqueue:
            answer += 1
            queue = nqueue
        else:
            break
 
    print(max(answer-1,0))
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H,W=map(int,input().split())

MAP=[["." for i in range (W)]for i in range(H)]
LIST=[0]*(10**6+100)

l=0
r=0
for i in range(H):
    A=list(input())
    for j in range(W):
        if(A[j]=="#"):
            MAP[i][j]="#"
            LIST[r]=(i,j,0)
            r+=1

while(True):
    T=LIST[l]
    i=T[0]
    j=T[1]
    if(i>0):
        if(MAP[i-1][j]=="."):
            MAP[i-1][j]="#"
            LIST[r]=(i-1,j,T[2]+1)
            r+=1  
    if(i+1<H):
        if(MAP[i+1][j]=="."):
            MAP[i+1][j]="#"
            LIST[r]=(i+1,j,T[2]+1)
            r+=1  
    if(j>0):
        if(MAP[i][j-1]=="."):
            MAP[i][j-1]="#"
            LIST[r]=(i,j-1,T[2]+1)
            r+=1  
    if(j+1<W):
        if(MAP[i][j+1]=="."):
            MAP[i][j+1]="#"
            LIST[r]=(i,j+1,T[2]+1)
            r+=1
    l+=1
    if(r<=l):
        print(LIST[r-1][2])
        exit()

Submission status: Accepted

Solution code:
import numpy as np
import copy

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

a = np.array([[0 if (ai[j] == "#") else np.inf for j in range(w)] for ai in a])

for i in range(1, h):
    a[i] = np.minimum(a[i], a[i - 1] + 1)
for i in range(h - 2, -1, -1):
    a[i] = np.minimum(a[i], a[i + 1] + 1)
for i in range(1, w):
    a[:, i] = np.minimum(a[:, i], a[:, i - 1] + 1)
for i in range(w - 2, -1, -1):
    a[:, i] = np.minimum(a[:, i], a[:, i + 1] + 1)

print(int(a.max()))

Submission status: Accepted

Solution code:
from collections import deque

H,W=map(int,input().split())
if H==1 and W==1:
    print(0)
    exit()

A=[]
B=deque([])
C=[[-1]*W for i in range(H)]
ans=[]
for h in range(H):
    temp=list(input())
    A.append(temp)
    for w in range(W):
        if A[h][w]=="#":
            B.append([h,w,0])
            C[h][w]=0
            ans.append(0)



step=[[1,0],[-1,0],[0,1],[0,-1]]

while B:
    P=B.popleft()
    for x,y in step:
        if 0<=P[0]+y<=H-1 and 0<=P[1]+x<=W-1:
            if C[P[0]+y][P[1]+x]==-1:
                B.append([P[0]+y,P[1]+x,P[2]+1])
                C[P[0]+y][P[1]+x]=1
                ans.append(P[2]+1)


print(max(ans))

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
que=[]
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            que.append((i, j))
            A[i][j]=1
        else:
            A[i][j]=0
d=[(1,0),(0,1),(-1,0),(0,-1)]
count=0
while que:
    h=[]
    for x,y in que:
        for dx,dy in d:
            nx,ny=x+dx,y+dy
            if 0<=nx<H and 0<=ny<W and A[nx][ny]==0:
                A[nx][ny]=1
                h.append((nx,ny))
    que=h
    count+=1
print(count-1)

Submission status: Accepted

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


d = [[-1]*W for _ in range(H)]
dx = [0,1,0,-1]
dy = [1,0,-1,0]


que = deque()
for x in range(W):
    for y in range(H):
        if grid[y][x] == '#':
            d[y][x] = 0
            que.append([x,y])

while len(que) != 0:
    p = que.popleft()
    for i in range(4):
        nx = p[0] + dx[i]
        ny = p[1] + dy[i]
        #print(nx,ny)
        if 0 <= nx <= W-1 and 0 <= ny <= H-1 and grid[ny][nx] == '.' and d[ny][nx] == -1:
            que.append([nx,ny])
            d[ny][nx] = d[p[1]][p[0]] + 1

# print(d)
# print(d[H-1][W-1])
res = 0
for x in range(W):
    for y in range(H):
        res = max(res,d[y][x])
print(res)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
INF=10**4
import numpy as np
a=np.full((H,W),INF,dtype=int)
for i in range(H):
  s=input()
  for j in range(len(s)):
    if s[j]=="#":
      a[i,j]=0

for i in range(0,W-1):
  np.minimum(a[:,i]+1,a[:,i+1],out=a[:,i+1])
for i in range(W-1,0,-1):
  np.minimum(a[:,i]+1,a[:,i-1],out=a[:,i-1])
for j in range(0,H-1):
  np.minimum(a[j,]+1,a[j+1,],out=a[j+1,])
for j in range(H-1,0,-1):
  np.minimum(a[j,]+1,a[j-1,],out=a[j-1,])

print(a.max())

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 - 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 - 1)[::-1]:
    cost[:, i] = np.minimum(cost[:, i], cost[:, i + 1] + 1)

print(np.max(cost))

Submission status: Accepted

Solution code:
def grid_bfs(h,w,start,maxD):
    INF = 10**9+7
    distance = [[INF for _ in range(w)] for _ in range(h)]
    queue = deque()
    for s in start:
        queue.append(s)
        distance[s[0]][s[1]] = 0
    while len(queue):
        y, x = queue.popleft()
        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
            if (0 <= nx < w and 0 <= ny < h):
                if (distance[ny][nx] > distance[y][x] + 1):
                    queue.append([ny, nx])
                    distance[ny][nx] = distance[y][x] + 1
                    if maxD<distance[ny][nx]:
                        maxD = distance[ny][nx]
    return maxD
def examA():
    H, W = LI()
    A = [[1 if a == "#" else 0 for a in SI()] for _ in range(H)]
    start = []
    for i in range(H):
        for j in range(W):
            if A[i][j]==1:
                start.append([i,j])
    ans = grid_bfs(H,W,start,0)
#    print(D,V)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examA()

Submission status: Accepted

Solution code:
def solve():
    from collections import deque
    from sys import stdin
    f_i = stdin
    
    H, W = map(int, f_i.readline().split())
    
    grid = ['W'] * (W + 2)
    for i in range(H):
        grid += ['W'] + list(f_i.readline().rstrip()) + ['W']
    grid += ['W'] * (W + 2)
    
    q = deque()
    for i, cell in enumerate(grid):
        if cell == '#':
            q.append((i, 0)) # (pos, operation count)
    move = (1, -1, W + 2, -W - 2)
    
    while q:
        pos, count = q.popleft()
        for mv in move:
            next_pos = pos + mv
            if grid[next_pos] == '.':
                grid[next_pos] = '#'
                q.append((next_pos, count + 1))
    
    print(count)
    
solve()

Submission status: Accepted

Solution code:
#darker　and darker
from collections import deque
d=deque()
e=deque()
h,w=map(int,input().split())
field=[0 for i in range(h+2)]
field[0]=[True for i in range(w+2)]
distance=0
for i in range(h):
    s=input()
    a=[False for i in range(w+2)]
    a[0]=True
    for j in range(w):
        if s[j]=="#":
            a[j+1]=True
            d.append((i+1,j+1))
    a[w+1]=True
    field[i+1]=a
field[h+1]=[True for i in range(w+2)]
while d:
    while d:
        some=d.popleft()
        index1,index2=some[0],some[1]
        if field[index1-1][index2]==False:
                field[index1-1][index2]=True
                e.append((index1-1,index2))
        if field[index1+1][index2]==False:
                field[index1+1][index2]=True
                e.append((index1+1,index2))
        if field[index1][index2+1]==False:
                field[index1][index2+1]=True
                e.append((index1,index2+1))
        if  field[index1][index2-1]==False:
                field[index1][index2-1]=True
                e.append((index1,index2-1))
    distance+=1
    d=e
    e=deque()
print(distance-1)

Submission status: Accepted

Solution code:
import sys
import collections


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

    mc = 0
    while True:
        if len(ql) != 0:
            cost, xv, yv = ql.popleft()
            mc = max(mc, cost)
            for xv, yv in [[xv + 1, yv], [xv - 1, yv], [xv, yv + 1], [xv, yv - 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(mc)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
a = list(list(input())for i in range(h))
stack = []
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            stack.append((i,j))
        
vec = ((1,0),(0,1),(-1,0),(0,-1))
move = 0
while stack:
    next = []
    move +=1
    for y,x in stack:
        for ny,nx in vec:
            ty,tx = y+ny,x+nx
            if ty>h-1 or tx>w-1 or ty<0 or tx <0:continue
            if a[ty][tx] == ".":
                a[ty][tx] = move
                next.append((ty,tx))
    stack = next

print(move-1)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
A = [[1 if a == "#" else 0 for a in input()] for _ in range(H)]
L = []
for i in range(H):
    for j in range(W):
        if A[i][j]: L.append((i, j))
def BFS():
    Q = deque(L)
    D = [[-1] * W for _ in range(H)]
    for i, j in L:
        D[i][j] = 0
    while Q:
        i, j = Q.popleft()
        for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            ni, nj = i+di, j+dj
            if 0 <= ni < H and 0 <= nj < W:
                if D[ni][nj] == -1:
                    D[ni][nj] = D[i][j] + 1
                    Q.append((ni, nj))
    return D

print(max([max(a) for a in BFS()]))

Submission status: Accepted

Solution code:
from collections import deque
from copy import copy

row, column = map(int, input().split())
map_ = [[c == "#" for c in input().strip()] for _ in range(row)]

queue = deque([(i, j) for j in range(column) for i in range(row) if map_[i][j]])

def bfs(maze, queue):
    depth = 0
    while True:
        depth += 1
        nextqueue = deque()
        while queue:
            posr, posc = queue.popleft()
            for dr, dc in zip([1, -1, 0, 0], [0, 0, 1, -1]):
                nextr = posr + dr
                nextc = posc + dc
                if 0 <= nextr < row and 0 <= nextc < column and not maze[nextr][nextc]:
                    maze[nextr][nextc] = True
                    nextqueue.append((nextr, nextc))
        if nextqueue:
            queue = copy(nextqueue)
        else:
            return depth - 1

print(bfs(map_, queue))

Submission status: Accepted

Solution code:
from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    
    h, w = map(int, input().split())
    a = [list(input()) for i in range(h)]
    queue = deque()
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                queue.append((i, j))

    visited = [[-1 for i in range(w)] for j in range(h)]
    ans = 0
    nqueue = deque()
    while queue:
        x, y = queue.popleft()
        visited[x][y] = 1
        for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            nx = x + i
            ny = y + j
            if nx >= 0 and ny >= 0 and nx < h and ny < w:
                if visited[nx][ny] == -1 and a[nx][ny] != "#":
                    nqueue.append([nx, ny])
                    visited[nx][ny] = 1
                    a[nx][ny] = "#"
        
        if len(queue) == 0:
            queue = nqueue
            nqueue = deque()
            ans += 1
        
    print(ans-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
p=[list("#"*(w+2))]+[list("#"+input()+"#") for i in range(h)]+[list("#"*(w+2))]
q=deque([])
for i in range(1,h+1):
	for j in range(1,w+1):
		if p[i][j]=='#':
			p[i][j]=0
			q.append([i,j])
d=[(1,0),(-1,0),(0,1),(0,-1)]
while q:
	x,y=q.popleft()
	for dx,dy in d:
		if p[x+dx][y+dy]==".":
			p[x+dx][y+dy]=p[x][y]+1
			q.append([x+dx,y+dy])
ans=0
for i in range(1,h+1):
	for j in range(1,w+1):
		ans=max(ans,p[i][j])
print(ans)

Submission status: Accepted

Solution code:
import collections
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
dp = [[H+W]*W for i in range(H)]

q = collections.deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            dp[i][j] = 0
            q.append([i, j])
            break
    if q:
        break


while(q):
    x, y = q.popleft()
    if x > 0:
        if dp[x-1][y] > dp[x][y]+1:
            if A[x-1][y] == ".":
                dp[x-1][y] = dp[x][y]+1
            else:
                dp[x-1][y] = 0
            q.append([x-1, y])
    if x < H-1:
        if dp[x+1][y] > dp[x][y]+1:
            if A[x+1][y] == ".":
                dp[x+1][y] = dp[x][y]+1
            else:
                dp[x+1][y] = 0
            q.append([x+1, y])
    if y > 0:
        if dp[x][y-1] > dp[x][y]+1:
            if A[x][y-1] == ".":
                dp[x][y-1] = dp[x][y]+1
            else:
                dp[x][y-1] = 0
            q.append([x, y-1])
    if y < W-1:
        if dp[x][y+1] > dp[x][y]+1:
            if A[x][y+1] == ".":
                dp[x][y+1] = dp[x][y]+1
            else:
                dp[x][y+1] = 0
            q.append([x, y+1])
ans = 0
for i in range(H):
    ans = max(ans, max(dp[i]))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


h,w=map(int,input().split())
maze=[list(input()) for i in range(h)]
d=[[-1]*w for i in range(h)]
que=deque([])
dd=((1,0),(0,1),(-1,0),(0,-1))
for i in range(h):
    for j in range(w):
        if maze[i][j]=="#":
            que.append((i,j))           
            d[i][j]=0
ans=0
while que:
    p=que.popleft()
    ans=d[p[0]][p[1]]
    for dx,dy in dd:
        nx=p[0]+dx
        ny=p[1]+dy
        if 0<=nx and nx<h and 0<=ny and ny<w and maze[nx][ny]!="#" and d[nx][ny]==-1:
            d[nx][ny]=ans+1
            que.append((nx,ny))  
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    h,w=map(int,input().split())
    maze=[list(input()) for i in range(h)]
    d=[[-1]*w for i in range(h)]
    que=deque([])
    dd=((1,0),(0,1),(-1,0),(0,-1))
    for i in range(h):
        for j in range(w):
            if maze[i][j]=="#":
                que.append((i,j))           
                d[i][j]=0
    ans=0
    while que:
        p=que.popleft()
        ans=d[p[0]][p[1]]
        for dx,dy in dd:
            nx=p[0]+dx
            ny=p[1]+dy
            if 0<=nx and nx<h and 0<=ny and ny<w and maze[nx][ny]!="#" and d[nx][ny]==-1:
                d[nx][ny]=ans+1
                que.append((nx,ny))  
    return ans
if __name__=='__main__':
    print(main())

Submission status: Accepted

Solution code:
from collections import deque

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

INF = 10**7

# 探索用ベクトル
vx = (0, -1, 0, 1)
vy = (-1, 0, 1, 0)

# 幅探索用キューの準備
q = deque()
for i, vi in enumerate(p):
    for j, vj in enumerate(vi):
        if vj == '#':
            q.appendleft((j, i))
            
qans = deque()

# 新しく黒に塗りつぶした座標をキューで返却
def bfs(q):
    for i in range(INF):
        # キューが空なら終了
        if len(q) == 0:
            return qans

        # キューから一つ取り出す
        x, y = map(int, q.pop())

        # 4方向のいずれかに白があれば、黒にする
        for j in range(4):
            nx, ny = x+vx[j], y+vy[j]

            # エリア外 or 黒色なら探索しない
            if nx < 0 or w <= nx or ny < 0 or h <= ny or p[ny][nx] == '#':
                continue

            p[ny][nx] = '#'
            qans.appendleft((nx, ny))

# 操作を白がなくなるまで繰り返す
for i in range(INF):
    qans = deque()
    q = bfs(q)
    # キューが空なら終了
    if len(q) == 0:
        ans = i
        break
    
print(ans)