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: Time Limit Exceeded

Solution code:
#!/bin/python3
import sys
import operator
from collections import deque,Counter

input=sys.stdin.readline
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]

#移動先4方向
dx = [1, 0, -1,  0]
dy = [0, 1,  0, -1]
#訪問リストを作る
visited=[[-1]*w for _ in range(h)]

def bfs(x,y):
  queue=deque([[x,y]])
  visited[x][y]=0
  while queue:
    x,y=queue.popleft()
    for i in range(4):
      nx,ny=x+dx[i],y+dy[i]
      if nx>=0 and nx<h and ny>=0 and ny<w and s[nx][ny]=="." \
      	and (visited[nx][ny]==-1 or visited[nx][ny]>visited[x][y]+1):
        visited[nx][ny]=visited[x][y]+1
        queue.append([nx,ny])
        #print(queue)
  return
if __name__ == '__main__':
  #黒マスの位置を取得
  starts=[[i,j] for i in range(h) for j in range(w) if s[i][j]=="#"]
  #print(*starts,sep="\n")
  for sx,sy in starts:
    bfs(sx,sy)
    #print("sx",sx,"sy",sy)
    #print(*visited,sep="\n")
  max_=0
  for i in range(h):
    max_=max(max(visited[i]),max_)
  print(max_)

Submission status: Time Limit Exceeded

Solution code:
#!/bin/python3
import sys
import operator
from collections import deque,Counter

input=sys.stdin.readline
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]

#移動先4方向
dx = [1, 0, -1,  0]
dy = [0, 1,  0, -1]
#訪問リストを作る
visited=[[-1]*w for _ in range(h)]

def bfs(x,y):
  queue=deque([[x,y]])
  visited[x][y]=0
  while queue:
    x,y=queue.popleft()
    for i in range(4):
      nx,ny=x+dx[i],y+dy[i]
      if nx>=0 and nx<h and ny>=0 and ny<w and s[nx][ny]=="." \
      	and (visited[nx][ny]==-1 or visited[nx][ny]>visited[x][y]+1):
        visited[nx][ny]=visited[x][y]+1
        queue.append([nx,ny])
        #print(queue)
  return
def main():
  #黒マスの位置を取得
  starts=[[i,j] for i in range(h) for j in range(w) if s[i][j]=="#"]
  #print(*starts,sep="\n")
  for sx,sy in starts:
    bfs(sx,sy)
    #print("sx",sx,"sy",sy)
    #print(*visited,sep="\n")
  max_=0
  for i in range(h):
    max_=max(max(visited[i]),max_)
  print(max_)
main()

Submission status: Time Limit Exceeded

Solution code:
#!/bin/python3
import sys
import operator
from collections import deque,Counter

input=sys.stdin.readline
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]

#移動先4方向
dx = [1, 0, -1,  0]
dy = [0, 1,  0, -1]
#訪問リストを作る
visited=[[-1]*w for _ in range(h)]

def bfs(x,y):
  queue=deque([[x,y]])
  visited[x][y]=0
  while queue:
    x,y=queue.popleft()
    for i in range(4):
      nx,ny=x+dx[i],y+dy[i]
      if nx>=0 and nx<h and ny>=0 and ny<w and s[nx][ny]=="." \
      	and (visited[nx][ny]==-1 or visited[nx][ny]>visited[x][y]+1):
        visited[nx][ny]=visited[x][y]+1
        queue.append([nx,ny])
        #print(queue)
  return
starts=[[i,j] for i in range(h) for j in range(w) if s[i][j]=="#"]
#print(*starts,sep="\n")
for sx,sy in starts:
  bfs(sx,sy)
  #print("sx",sx,"sy",sy)
  #print(*visited,sep="\n")
max_=0
for i in range(h):
  max_=max(max(visited[i]),max_)
print(max_)

Submission status: Time Limit Exceeded

Solution code:
#!/bin/python3
import sys
import operator
from collections import deque,Counter

input=sys.stdin.readline
h,w=map(int,input().split())

#print(sx,sy)

#print(gx,gy)
s=[list(input()) for _ in range(h)]
#白のブロックを数える
c=[]
for a in s:
  c+=a
c=Counter(c)
#print(c["."])
white=c["."]
#移動先4方向
dx = [1, 0, -1,  0]
dy = [0, 1,  0, -1]
#訪問リストを作る
visited=[[-1]*w for _ in range(h)]

def bfs(x,y):
  queue=deque([[x,y]])
  visited[x][y]=0
  while queue:
    x,y=queue.popleft()
    for i in range(4):
      nx,ny=x+dx[i],y+dy[i]
      if nx>=0 and nx<h and ny>=0 and ny<w and s[nx][ny]=="." \
      	and (visited[nx][ny]==-1 or visited[nx][ny]>visited[x][y]+1):
        visited[nx][ny]=visited[x][y]+1
        queue.append([nx,ny])
        #print(queue)
  return
starts=[[i,j] for i in range(h) for j in range(w) if s[i][j]=="#"]
#print(*starts,sep="\n")
for sx,sy in starts:
  bfs(sx,sy)
  #print("sx",sx,"sy",sy)
  #print(*visited,sep="\n")
max_=0
for i in range(h):
  max_=max(max(visited[i]),max_)
print(max_)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
A=[list(input()) for i in range(h)]
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal as D  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
from fractions import Fraction as F  #F(a,b)で正確なa/b
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

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

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

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

    print(ans)







    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from queue import Queue

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

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

print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

ans=0
for i in range(H):
    ans=max(ans,max(dist[i]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

H,W = map(int,input().split())
D = [list(input()) for i in range(H)]
ans = 0
dist = [[float("inf")]*W for i in range(H)]

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

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

Submission status: Time Limit Exceeded

Solution code:
import collections
import math
import copy

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

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

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

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


print(nax)

Submission status: Time Limit Exceeded

Solution code:
import collections
import math
import copy

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

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

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


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

nax=0
for i in range(H):
    for j in range(W):
        nax=max(nax,d[i][j])
print(nax)

Submission status: Time Limit Exceeded

Solution code:
import collections
import math
import copy

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

A=[list(str(input())) for i in range(H)]
#1<=sy<=R
d=[[-1 for j in range(W)]for i in range(H)]
inf=10**6
ans=0
start=[]
for i in range(H):
    for j in range(W):
        if A[i][j]=='#':
            start.append([i,j])
            d[i][j]=0

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

h,w=map(int,input().split())
aa=[list(input()) for i in range(h)]
visited=[[0 for i in range(w)] for i in range(h)]
queue=[]
dy=[0,1,0,-1]
dx=[1,0,-1,0]
ans=0
for i in range(h):
    for j in range(w):
        if aa[i][j]=='#':
            queue.append([i,j])

while len(queue)>0:
    now=queue.pop(0)
    for i in range(4):
        x=now[1]+dx[i]
        y=now[0]+dy[i]
        if 0<=x<w and 0<=y<h:
            if visited[y][x]==0 and aa[y][x]=='.':
                queue.append([y,x])
                visited[y][x]=visited[now[0]][now[1]]+1

anlist=[flatten for inner in visited for flatten in inner]

print(max(anlist))

Submission status: Time Limit Exceeded

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

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

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

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

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

print(ans)

Submission status: Time Limit Exceeded

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

dist = [[-1]*W for _ in range(H)]
black_cells = deque()
#黒マスの位置をblack_cellsに保持
#distの黒マスの部分に0でフラッグ
for h in range(H):
  for w in range(W):
    if grid[h][w]=="#":
      black_cells.append((h,w))
      dist[h][w] = 0
def bfs(black_cells, dist):
  count=0
  while black_cells:
    h,w = black_cells.popleft()
    count = dist[h][w]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_h = h + dy
        new_w = w + dx
        if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
          continue
        if dist[new_h][new_w] == -1:
          dist[new_h][new_w] = count+1
          black_cells.append((new_h,new_w))
  return count
print(bfs(black_cells,dist))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

inf=float('inf')

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

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

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

print(ans)

Submission status: Time Limit Exceeded

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

sq=[list(input()) for i in range(H)]
pos=[]

for j in range(H):
    for k in range(W):
        if sq[j][k]=="#":
            pos.append([j,k,0])
            
while pos!=[]:

    y,x,depth=pos.pop(0)
    
    if 0<=x-1:
        if sq[y][x-1]==".":
            sq[y][x-1]="!"
            pos.append([y,x-1,depth+1])

    if x+1<=W-1:
        if sq[y][x+1]==".":
            sq[y][x+1]="!"
            pos.append([y,x+1,depth+1])

    if 0<=y-1:
        if sq[y-1][x]==".":
            sq[y-1][x]="!"
            pos.append([y-1,x,depth+1])

    if y+1<=H-1:
        if sq[y+1][x]==".":
            sq[y+1][x]="!"
            pos.append([y+1,x,depth+1])

print(depth)

Submission status: Time Limit Exceeded

Solution code:
H,W= list(map(int,input().split()))
l=[list(input()) for i in range(H)]
inf=10**9
visited=[[inf]*W for i in range(H)]
from collections import deque
def ans():
   que=deque([])
   for i in range(H):
      for j in range(W):
         if l[i][j]=="#":
            que.append((i,j))
            visited[i][j]=0
   while que:
      y,x=que.popleft()
      node=visited[y][x]+1
      if y>0:
         if l[y-1][x]=="." and visited[y-1][x]==inf:
            visited[y-1][x]=min(visited[y-1][x],node)
            que.append((y-1,x))
      if x>0:
         if l[y][x-1]=="." and visited[y][x-1]==inf:
            visited[y][x-1]=min(visited[y][x-1],node)
            que.append((y,x-1))
      if H-1>y:
         if l[y+1][x]=="." and visited[y+1][x]==inf:
            visited[y+1][x]=min(visited[y+1][x],node)
            que.append((y+1,x))
      if W-1>x:
         if l[y][x+1]=="." and visited[y][x+1]==inf:
            visited[y][x+1]=min(visited[y][x+1],node)
            que.append((y,x+1))
ans()
visited=sum(visited,[])
print(max(visited))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int,input().split())
grid = [list(input()) for _ in range(h)]
dist = [[-1]*w for _ in range(h)]
black_cells = []
for i in range(h):
    for j in range(w):
        if grid[i][j] == '#':
            black_cells.append((i,j))
dxy = [[1,0],[-1,0],[0,1],[0,-1]]
stack = deque(black_cells)
darked = len(stack)
targetd = h*w
cnt = 0

while darked < targetd:
    next = deque([])
    while stack:
        y, x = stack.popleft()
        for dx, dy in dxy:
            X = x + dx
            Y = y + dy
            if X < 0 or X >= w or Y < 0 or Y >= h:
                continue
            if grid[Y][X] == '.':
                next.append((Y, X))
                grid[Y][X] = '#'
    stack = next
    cnt += 1
    darked += len(next)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

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

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
a = [input() for i in range(h)]
b = [-1]*h*w; c = []; d = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == "#": b[i*w+j] = 0; c.append(i*w+j)
while len(c) < h*w:
    if c[d]//w != 0:
        if b[c[d]-w] == -1: b[c[d]-w] = b[c[d]]+1; c.append(c[d]-w)
    if c[d]%w != 0:
        if b[c[d]-1] == -1: b[c[d]-1] = b[c[d]]+1; c.append(c[d]-1)
    if c[d]%w != w-1:
        if b[c[d]+1] == -1: b[c[d]+1] = b[c[d]]+1; c.append(c[d]+1)
    if c[d]//w != h-1:
        if b[c[d]+w] == -1: b[c[d]+w] = b[c[d]]+1; c.append(c[d]+w)
    d += 1
print(max(b))

Submission status: Time Limit Exceeded

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


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


def main():
    H, W = map(int, input().split())
    grid = [input() for _ in range(H)]
    dist = [[-1]*W for _ in range(H)]

    black_cells = deque()
    for h in range(H):
        for w in range(W):
            if grid[h][w] == '#':
                black_cells.append((h, w))
                dist[h][w] = 0
    print(bfs(H, W, black_cells, dist))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

q = deque()
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            q.append((i, j, 0)) 

while q:
    y, x, d = q.popleft()
    if a[y][x] == '#':
        for xdx, ydy in zip((x, x, x+1, x-1), (y+1, y-1, y, y)):
            if (0 <= xdx < w) and (0 <= ydy < h):
                if a[ydy][xdx] == '.':
                    a[ydy][xdx] = '#'
                    q.append((ydy, xdx, d+1))
print(d)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

cnt = [[10 ** 10] * w for _ in range(h)]
visited = [[0] * w for _ in range(h)]
queue = deque()
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            cnt[i][j] = 0
            queue.append([i, j])
            visited[i][j] = 1

def bfs(q, v, c):
    while q:
        y, x = q.popleft()
        for i, j in ([0, 1], [1, 0], [-1, 0], [0, -1]):
            ny = y + i
            nx = x + j
            if 0 <= nx < w and 0 <= ny < h and v[ny][nx] == 0:
                c[ny][nx] = c[y][x] + 1
                v[ny][nx] = 1
                q.append([ny, nx])

bfs(queue, visited, cnt)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

cnt = [[10 ** 10] * w for _ in range(h)]
queue = deque()
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            cnt[i][j] = 0
            queue.append([i, j])

def bfs(q, c):
    while q:
        y, x = q.pop()
        for i, j in ([0, 1], [1, 0], [-1, 0], [0, -1]):
            ny = y + i
            nx = x + j
            if 0 <= nx < w and 0 <= ny < h and c[ny][nx] >= c[y][x] + 1:
                c[ny][nx] = c[y][x] + 1
                q.append([ny, nx])
    



bfs(queue, cnt)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

cnt = [[10 ** 10] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            cnt[i][j] = 0
def bfs(q, v, c):
    while q:
        y, x = q.pop()
        for i, j in ([0, 1], [1, 0], [-1, 0], [0, -1]):
            ny = y + i
            nx = x + j
            if 0 <= nx < w and 0 <= ny < h and v[ny][nx] == 0:
                v[ny][nx] = 1
                c[ny][nx] = min(c[ny][nx], c[y][x] + 1)
                q.append([ny, nx])





for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            queue = deque()
            queue.append([i, j])
            visited = [[0] * w for _ in range(h)]
            bfs(queue, visited, cnt)
ans = 0
for i in range(h):
    ans = max(ans, max(cnt[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="o"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        # 壁も含めて0-indexed 元々の座標だけ考えると1-indexed
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]


        d = deque()
        for i in range(1, self.h+1):
            for j in range(1, self.w+1):
                if self.getgrid(j, i) == "#":
                    self.set(j, i, 0)
                    d.append((j, i, 0))
        # print(d)
        ans = 0
        while d:
            # print(d)
            cx, cy, cc = d.popleft()
            for dx, dy in move:
                nx, ny = dx + cx, dy + cy
                # print(nx, ny)
                if self.getgrid(nx, ny) == ".":

                    if self.get(nx, ny) > cc + 1:
                        ans = max(ans, cc + 1)
                        self.set(nx, ny, cc + 1)
                        d.append((nx, ny, cc + 1))

        # print(self.getgrid(1, 4))
        print(ans)



def solve():
    h, w = getList()
    g = TwoDimGrid(h, w)
    g.search()
def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()