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:
def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        a = input()
        A.append(a)
    bl = set()
    wl = set()
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                bl.add((i, j))
            else:
                wl.add((i, j))
    r = 0
    while wl:
        bln = set()
        for i in bl:
            if (i[0] + 1, i[1]) in wl:
                wl.remove((i[0] + 1, i[1]))
                bln.add((i[0] + 1, i[1]))
            if (i[0] - 1, i[1]) in wl:
                wl.remove((i[0] - 1, i[1]))
                bln.add((i[0] - 1, i[1]))
            if (i[0], i[1] + 1) in wl:
                wl.remove((i[0], i[1] + 1))
                bln.add((i[0], i[1] + 1))
            if (i[0], i[1] - 1) in wl:
                wl.remove((i[0], i[1] - 1))
                bln.add((i[0], i[1] - 1))
        bl = bln
        r += 1
    return r
print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        a = input()
        A.append(a)
    bl = []
    wl = []
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                bl.append((i, j))
            else:
                wl.append((i, j))
    r = 0
    for i in wl:
        t = 10**9
        for j in bl:
            t = min(t, abs(i[0]-j[0]) + abs(i[1]-j[1]))
        r = max(r, t)
    return r
print(main())

Submission status: Time Limit Exceeded

Solution code:
import copy

def bfs(x, y):
    global tmp
    global cnt
    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 maze[nx][ny] == ".":
            tmp.append((nx, ny))
            maze[nx][ny] = "#"
            cnt += 1
    return tmp

h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
ans = 0
cnt = 0
tmp = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            tmp.append((i, j))
            cnt += 1

while cnt < h * w:
    tmp_ = copy.copy(tmp)
    tmp = []
    while tmp_:
        p = tmp_.pop()
        bfs(p[0], p[1])
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

def bfs(x, y):
    global tmp
    global cnt
    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 maze[nx][ny] == "." and not (nx, ny) in tmp:
            tmp.append((nx, ny))
            maze[nx][ny] = "#"
            cnt += 1
    return tmp

h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
ans = 0
cnt = 0
tmp = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            tmp.append((i, j))
            cnt += 1

while cnt < h * w:
    tmp_ = copy.copy(tmp)
    tmp = []
    while tmp_:
        p = tmp_.pop()
        bfs(p[0], p[1])
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
from collections import deque

def bfs(x, y):
    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 maze[nx][ny] == ".":
            maze[nx][ny] = "#"

h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
cnt = 0
ans = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            cnt += 1

while cnt > 0:
    tmp = []
    for i in range(h):
        for j in range(w):
            if maze[i][j] == "#":
                tmp.append((i, j))
    while tmp:
        p = tmp.pop()
        bfs(p[0], p[1])

    ans += 1
    cnt = 0   
    for i in range(h):
        for j in range(w):
            if maze[i][j] == ".":
                cnt += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [input() for i in range(H)]
A = [[0 for j in range(W)] for i in range(H)]
pos = []
for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      pos.append([i, j])
      A[i][j] = 1
cnt = 0
while pos != []:
  n = len(pos)
  cnt += 1
  for i in range(n):
    x, y = pos[i][0], pos[i][1]
    if x > 0:
      if A[x-1][y] == 0:
        A[x-1][y] = 1
        pos.append([x-1, y])
    if x < H-1:
      if A[x+1][y] == 0:
        A[x+1][y] = 1
        pos.append([x+1, y])
    if y > 0:
      if A[x][y-1] == 0:
        A[x][y-1] = 1
        pos.append([x, y-1])
    if y < W-1:
      if A[x][y+1] == 0:
        A[x][y+1] = 1
        pos.append([x, y+1])
  pos = pos[n:]
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
def main():
  num_r,num_c = map(int,input().split())
  field = [input() for i in range(num_r)]
  q = []
  seen = [0]*(num_c*num_r)
  count = 0

  for i in range(num_r):
    for j in range(num_c):
      if field[i][j] == "#":
        seen[i*num_c+j] = 1
        q.append([i,j])
      
  while q:
    tank = []
    for i in q:
      r = i[0]
      c = i[1]
      if (0<=r-1) and (seen[(r-1)*num_c+c] == 0):
        tank.append([r-1,c])
        seen[(r-1)*num_c+c] = 1
      if (r+1<num_r) and (seen[(r+1)*num_c+c] == 0):
        tank.append([r+1,c])
        seen[(r+1)*num_c+c] = 1
      if (0<=c-1) and (seen[r*num_c+(c-1)] == 0):
        tank.append([r,c-1])
        seen[r*num_c+(c-1)] = 1
      if (c+1<num_c) and (seen[r*num_c+(c+1)] == 0):
        tank.append([r,c+1])
        seen[r*num_c+(c+1)] = 1

    count = count + 1
    q = tank

  print(count-1)
  
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
num_r,num_c = map(int,input().split())
field = [input() for i in range(num_r)]
q = []
seen = [0]*(num_c*num_r)
count = 0

for i in range(num_r):
  for j in range(num_c):
    if field[i][j] == "#":
      seen[i*num_c+j] = 1
      q.append([i,j])

while q:
  tank = []
  for i in q:
    r = i[0]
    c = i[1]
    if (0<=r-1) and (seen[(r-1)*num_c+c] == 0):
      tank.append([r-1,c])
      seen[(r-1)*num_c+c] = 1
    if (r+1<num_r) and (seen[(r+1)*num_c+c] == 0):
      tank.append([r+1,c])
      seen[(r+1)*num_c+c] = 1
    if (0<=c-1) and (seen[r*num_c+(c-1)] == 0):
      tank.append([r,c-1])
      seen[r*num_c+(c-1)] = 1
    if (c+1<num_c) and (seen[r*num_c+(c+1)] == 0):
      tank.append([r,c+1])
      seen[r*num_c+(c+1)] = 1
   
  count = count + 1
  q = tank

print(count-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

num_r,num_c = map(int,input().split())
field = [list(input()) for i in range(num_r)]
q_r = deque([])
q_c = deque([])
seen = [[0]*num_c for i in range(num_r)]
step_r = [1,0,-1,0]
step_c = [0,1,0,-1]

for i in range(num_r):
  for j in range(num_c):
    if field[i][j] == "#":
      q_r.append(i)
      q_c.append(j)
      g_r = 0
      g_c = 0

while q_r:
  r = q_r.popleft()
  c = q_c.popleft()

  for i in range(4):
    next_r = r + step_r[i]
    next_c = c + step_c[i]
    
    if (0 <= next_r < num_r) and (0 <= next_c < num_c) and (field[next_r][next_c] != "#"):
      field[next_r][next_c] = "#"
      q_r.append(next_r)
      q_c.append(next_c)
      seen[next_r][next_c] = seen[r][c] + 1
  #    print(seen[next_r][next_c],next_r,next_c)
      g_r = next_r
      g_c = next_c

print(int(seen[g_r][g_c]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

num_r,num_c = map(int,input().split())
field = [list(input()) for i in range(num_r)]
q_r = deque([])
q_c = deque([])
seen = np.zeros((num_r,num_c))
step_r = [1,0,-1,0]
step_c = [0,1,0,-1]

for i in range(num_r):
  for j in range(num_c):
    if field[i][j] == "#":
      q_r.append(i)
      q_c.append(j)
      g_r = 0
      g_c = 0

while q_r:
  r = q_r.popleft()
  c = q_c.popleft()

  for i in range(4):
    next_r = r + step_r[i]
    next_c = c + step_c[i]
    
    if (0 <= next_r < num_r) and (0 <= next_c < num_c) and (field[next_r][next_c] != "#"):
      field[next_r][next_c] = "#"
      q_r.append(next_r)
      q_c.append(next_c)
      seen[next_r][next_c] = seen[r][c] + 1
  #    print(seen[next_r][next_c],next_r,next_c)
      g_r = next_r
      g_c = next_c

print(int(seen[g_r][g_c]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

num_r,num_c = map(int,input().split())
field = [list(input()) for i in range(num_r)]
q_r = deque([])
q_c = deque([])
seen = np.zeros((num_r,num_c))
step_r = [1,0,-1,0]
step_c = [0,1,0,-1]

for i in range(num_r):
  for j in range(num_c):
    if field[i][j] == "#":
      q_r.append(i)
      q_c.append(j)
      g_r = 0
      g_c = 0

while q_r:
  r = q_r.popleft()
  c = q_c.popleft()

  for i in range(4):
    next_r = r + step_r[i]
    next_c = c + step_c[i]
    
    if (next_r<0) or (num_r<=next_r) or (next_c<0) or (num_c<=next_c) or (field[next_r][next_c] == "#"):
      continue
    
    field[next_r][next_c] = "#"
    q_r.append(next_r)
    q_c.append(next_c)
    seen[next_r][next_c] = seen[r][c] + 1
#    print(seen[next_r][next_c],next_r,next_c)
    g_r = next_r
    g_c = next_c

print(int(seen[g_r][g_c]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

num_r,num_c = list(map(int,input().split()))
field = [list(input()) for i in range(num_r)]
q_r = deque([])
q_c = deque([])
seen = np.zeros((num_r,num_c))
step_r = [1,0,-1,0]
step_c = [0,1,0,-1]

for i in range(num_r):
  for j in range(num_c):
    if field[i][j] == "#":
      q_r.append(i)
      q_c.append(j)
      g_r = 0
      g_c = 0

while q_r:
  r = q_r.popleft()
  c = q_c.popleft()

  for i in range(4):
    next_r = r + step_r[i]
    next_c = c + step_c[i]
    
    if (next_r<0) or (num_r<=next_r) or (next_c<0) or (num_c<=next_c) or (field[next_r][next_c] == "#"):
      continue
    
    field[next_r][next_c] = "#"
    q_r.append(next_r)
    q_c.append(next_c)
    seen[next_r][next_c] = seen[r][c] + 1
#    print(seen[next_r][next_c],next_r,next_c)
    g_r = next_r
    g_c = next_c

print(int(seen[g_r][g_c]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

num = list(map(int,input().split()))
field = [list(input()) for i in range(num[0])]
q_r = deque([])
q_c = deque([])
seen = np.zeros((num[0],num[1]))
step_r = [1,0,-1,0]
step_c = [0,1,0,-1]

for i in range(num[0]):
  for j in range(num[1]):
    if field[i][j] == "#":
      q_r.append(i)
      q_c.append(j)
      g_r = 0
      g_c = 0

while q_r:
  r = q_r.popleft()
  c = q_c.popleft()

  for i in range(4):
    next_r = r + step_r[i]
    next_c = c + step_c[i]
    
    if (next_r<0) or (num[0]<=next_r) or (next_c<0) or (num[1]<=next_c) or (field[next_r][next_c] == "#"):
      continue
    
    field[next_r][next_c] = "#"
    q_r.append(next_r)
    q_c.append(next_c)
    seen[next_r][next_c] = seen[r][c] + 1
#    print(seen[next_r][next_c],next_r,next_c)
    g_r = next_r
    g_c = next_c

print(int(seen[g_r][g_c]))

Submission status: Time Limit Exceeded

Solution code:
import queue
import numpy as np

num = list(map(int,input().split()))
field = [list(input()) for i in range(num[0])]
q_r = queue.Queue()
q_c = queue.Queue()
seen = np.zeros((num[0],num[1]))
step_r = [1,0,-1,0]
step_c = [0,1,0,-1]

for i in range(num[0]):
  for j in range(num[1]):
    if field[i][j] == "#":
      q_r.put(i)
      q_c.put(j)
      g_r = 0
      g_c = 0
      
while not q_r.empty():
  r = q_r.get()
  c = q_c.get()
  
  for i in range(4):
    next_r = r + step_r[i]
    next_c = c + step_c[i]
    
    if (next_r<0) or (num[0]<=next_r) or (next_c<0) or (num[1]<=next_c) or (field[next_r][next_c] == "#"):
      continue
    
    field[next_r][next_c] = "#"
    q_r.put(next_r)
    q_c.put(next_c)
    seen[next_r][next_c] = seen[r][c] + 1
#    print(seen[next_r][next_c],next_r,next_c)
    g_r = next_r
    g_c = next_c

print(int(seen[g_r][g_c]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
G = [list(input()) for _ in range(H)]
que = deque()
# 始点を追加
for i in range(H):
    for j in range(W):
        if G[i][j] == '#':
            que.append([i, j])
cnt = -1
while que:
    cnt += 1
    next_que = deque()
    while que:
        h, w = que.popleft()  # BFSで探索
        dh = [1, 0, -1, 0]
        dw = [0, 1, 0, -1]
        for j in range(4):
            nh = h + dh[j]
            nw = w + dw[j]
            if 0 <= nh < H and 0 <= nw < W and G[nh][nw] == '.':
                G[nh][nw] = '#'
                next_que.append([nh, nw])
    que = next_que
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int,input().split())
mz = []
q = deque()
for i in range(h):
    mz.append(list(input()))
    ls = [[i,j,0] for j, a in enumerate(mz[-1]) if a == '#'] #i黒のところのindexをqueに追加
    q.extend(ls)


delta = [[-1,0],[0,-1],[1,0],[0,1]]
while q:
    y,x,c = q.popleft()
    for dy,dx in delta:
        if (0<= y+dy <h) and (0<=x+dx <w):
            if mz[y+dy][x+dx] == ".":
                mz[y+dy][x+dx]="#" #黒に置き換え
                q.append([y+dy,x+dx,c+1])

            else: #すでに黒なら訪問しなくてよい
                pass

print(c)#cは最後にpopされたcost

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque

####入力
H,W = map(int,input().split())

#gridの定義
grid = []
for i in range(H):
  S = input()
  grid.append( [S[i] for i in range(W) ])
####入力終了


#l_blackの設定
l_black = deque([])
for i in range(H):
  for j in range(W):
    if grid[i][j] == "#":
      l_black.append( [i,j] ) # [行,列]


#探索
cnt = 0

while len(l_black) > 0:

  l_change = deque([])

  #vは黒マスリスト #新たに黒マスになる白マスの座標をl_changeに詰めていく
  while len(l_black) > 0:
    v = l_black.popleft()
    #iはvの上下左右のマスの座標[行,列]
    for i in [ [v[0]+1,v[1]] , [v[0],v[1]+1] , [v[0]-1,v[1]] ,[v[0],v[1]-1] ]:
      #場外アウトの場合はスルー
      if (i[1]<0 or i[0] <0 or i[0]>=H or i[1] >= W ):
        continue
      #移動先がもう黒マスの場合スルー
      if grid[i[0]][i[1]] == "#":
        continue
      #移動先が白マスならばそこの座標をl_changeに追加
      if grid[i[0]][i[1]] == ".":
        l_change.append( i )
        
  #l_blackの中を新たに黒鱒になったやつの座標だけにする
  l_black = copy.deepcopy( l_change )
  #l_changeの中の白マスを黒にする
  while len(l_change) > 0:
    i = l_change.popleft()
    grid[i[0]][i[1]] = "#" 
  if len(l_black) > 0:
    cnt = cnt + 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque

####入力
H,W = map(int,input().split())

#gridの定義
grid = []
for i in range(H):
  S = input()
  grid.append( [S[i] for i in range(W) ])
####入力終了


#l_blackの設定
l_black = []
for i in range(H):
  for j in range(W):
    if grid[i][j] == "#":
      l_black.append( [i,j] ) # [行,列]


#探索
cnt = 0

while len(l_black) > 0:

  l_change = deque([])

  #vは黒マスリスト #新たに黒マスになる白マスの座標をl_changeに詰めていく
  for v in l_black:
    #iはvの上下左右のマスの座標[行,列]
    for i in [ [v[0]+1,v[1]] , [v[0],v[1]+1] , [v[0]-1,v[1]] ,[v[0],v[1]-1] ]:
      #場外アウトの場合はスルー
      if (i[1]<0 or i[0] <0 or i[0]>=H or i[1] >= W ):
        continue
      #移動先がもう黒マスの場合スルー
      if grid[i[0]][i[1]] == "#":
        continue
      #移動先が白マスならばそこの座標をl_changeに追加
      if grid[i[0]][i[1]] == ".":
        l_change.append( i )
  
  #l_changeの中の白マスを黒にする
  for i in l_change:
    grid[i[0]][i[1]] = "#" 
  #l_blackの中を新たに黒鱒になったやつの座標だけにする
  l_black = copy.deepcopy( list(l_change ))
  if len(l_black) > 0:
    cnt = cnt + 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import copy

####入力
H,W = map(int,input().split())

#gridの定義
grid = []
for i in range(H):
  S = input()
  grid.append( [S[i] for i in range(W) ])
####入力終了


#l_blackの設定
l_black = []
for i in range(H):
  for j in range(W):
    if grid[i][j] == "#":
      l_black.append( [i,j] ) # [行,列]


#探索
cnt = 0

while len(l_black) > 0:

  l_change = []

  #vは黒マスリスト #新たに黒マスになる白マスの座標をl_changeに詰めていく
  for v in l_black:
    #iはvの上下左右のマスの座標[行,列]
    for i in [ [v[0]+1,v[1]] , [v[0],v[1]+1] , [v[0]-1,v[1]] ,[v[0],v[1]-1] ]:
      #場外アウトの場合はスルー
      if (i[1]<0 or i[0] <0 or i[0]>=H or i[1] >= W ):
        continue
      #移動先がもう黒マスの場合スルー
      if grid[i[0]][i[1]] == "#":
        continue
      #移動先が白マスならばそこの座標をl_changeに追加
      if grid[i[0]][i[1]] == ".":
        l_change.append( i )
  
  #l_changeの中の白マスを黒にする
  for i in l_change:
    grid[i[0]][i[1]] = "#" 
  #l_blackの中を新たに黒鱒になったやつの座標だけにする
  l_black = copy.deepcopy( l_change )
  if len(l_black) > 0:
    cnt = cnt + 1
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:
        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:
import queue
h, w = map(int, input().split())
a = [list(input()) for i in range(h)]

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
aa = [["W"] * w for i in range(h)]
def bfs(sx, sy):
    q = queue.Queue()
    q.put([sx, sy])
    aa[sx][sy] = "B"
    while not q.empty():
        now = q.get()
        nowx = now[0]
        nowy = now[1]
        for i in range(4):
            nextx = nowx + dx[i]
            nexty = nowy + dy[i]
            if nextx >= 0 and nexty >= 0 and nextx < h and nexty < w:
                if aa[nextx][nexty] == "W" and a[nextx][nexty] != "#":
                    aa[nextx][nexty] = "B"

for i in range(h):
    for j in range(w):
        if a[i][j] == ".":
            flag = True
            break
        else:
            flag = False

ans = 0
while flag:
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                bfs(i, j)
    ans += 1
    flag = False
    for i in range(h):
        for j in range(w):
            if aa[i][j] == "B":
                a[i][j] = "#"
            else:
                flag = True

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10**9)

def dfs():             
    d = list([float("inf")] * w * h)

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

    que = deque([])
    # スタート地点をキューにしまう
    for i in range(len(maze)):
        x = i // w
        y = i - w * x
        if maze[i] == "#":
            que.append((x,y))
        # スタート地点に初期移動回数をしまう
            d[i] = 0
    while que:
        # キューの左端を取り出す
        now = que.popleft()
        # ゴールにたどり着いていれば終了
        if "." not in maze:
            break
        for i in range(4):
            nx = now[0] + dx[i]
            ny = now[1] + dy[i]
            next = w * nx + ny
            # 移動できてまだ到達していない場合以下の処理を行う
            if 0 <= nx < h and 0 <= ny < w and maze[next] != "#" and d[next] == float("inf"):
                # 次の地点をキューに加える
                que.append((nx, ny))
                # 次の位置に移動回数をしまう
                d[next] = d[w * now[0] + now[1]] + 1
                maze[next] = "#"

    return max(d)

h, w = map(int, input().split())
maze = list(''.join(input() for _ in range(h)))

print(dfs())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

# スタートから1を目指す、1から....Nを目指す
def dfs():             
    d = list([float("inf")] * w *h)

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

    que = deque([])
    # スタート地点をキューにしまう
    for i in range(len(maze)):
        x = i // w
        y = i - w * x
        if maze[i] == "#":
            que.append((x,y))
        # スタート地点に初期移動回数をしまう
            d[i] = 0
    while que:
        # キューの左端を取り出す
        now = que.popleft()
        # ゴールにたどり着いていれば終了
        if "." not in maze:
            break
        for i in range(4):
            nx = now[0] + dx[i]
            ny = now[1] + dy[i]
            next = w * nx + ny
            # 移動できてまだ到達していない場合以下の処理を行う
            if 0 <= nx < h and 0 <= ny < w and maze[next] != "#" and d[next] == float("inf"):
                # 次の地点をキューに加える
                que.append((nx, ny))
                # 次の位置に移動回数をしまう
                d[next] = d[w * now[0] + now[1]] + 1
                maze[next] = "#"

    return max(d)

h, w = map(int, input().split())
maze = list(''.join(input() for _ in range(h)))

print(dfs())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

# スタートから1を目指す、1から....Nを目指す
def dfs():             
    d = list([float("inf")] * w *h)

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

    que = deque([])
    # スタート地点をキューにしまう
    for i in range(len(maze)):
        x = i // w
        y = i - w * x
        if maze[i] == "#":
            que.append((x,y))
        # スタート地点に初期移動回数をしまう
            d[i] = 0
    while que:
        # キューの左端を取り出す
        now = que.popleft()
        # ゴールにたどり着いていれば終了
        for i in range(4):
            nx = now[0] + dx[i]
            ny = now[1] + dy[i]
            next = w * nx + ny
            # 移動できてまだ到達していない場合以下の処理を行う
            if 0 <= nx < h and 0 <= ny < w and maze[next] != "#" and d[next] == float("inf"):
                # 次の地点をキューに加える
                que.append((nx, ny))
                # 次の位置に移動回数をしまう
                d[next] = d[w * now[0] + now[1]] + 1

    return max(d)

h, w = map(int, input().split())
maze = ''.join(input() for _ in range(h))

print(dfs())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = [int(x) for x in input().split()]
m = []
for _ in range(h):
    m.append(list(input()))

q = deque()
d = [[-1]*w for x in range(h)]

for i in range(h):
    for j in range(w):
        if m[i][j] == "#":
            q.append([i,j])
            d[i][j] = 0

aa = 0
while q:
    v = q.popleft()
    count = 0
    for i in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny = v[0] + i[0]
        nx = v[1] + i[1]
        if (0<=ny<h and 0<=nx<w and m[ny][nx] == "."):
            m[ny][nx] = "#"
            q.append([ny,nx])
            d[ny][nx] = d[v[0]][v[1]] + 1
            aa = max(aa,d[ny][nx])

######
print(aa)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = [int(x) for x in input().split()]
m = []
for _ in range(h):
    m.append(list(input()))

q = deque()
d = [[-1]*w for x in range(h)]

for i in range(h):
    for j in range(w):
        if m[i][j] == "#":
            q.append([i,j])
            d[i][j] = 0

aa = 0
while q:
    v = q.popleft()
    count = 0
    for i in m:
        jj = set(i)
        if len(jj) == 2:
            break
    else:
        break
    for i in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny = v[0] + i[0]
        nx = v[1] + i[1]
        if (0<=ny<h and 0<=nx<w and m[ny][nx] == "."):
            m[ny][nx] = "#"
            q.append([ny,nx])
            d[ny][nx] = d[v[0]][v[1]] + 1
            aa = max(aa,d[ny][nx])

######
print(aa)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = [int(x) for x in input().split()]
m = []
for _ in range(h):
    m.append(list(input()))

q = deque()
d = [[-1]*w for x in range(h)]

for i in range(h):
    for j in range(w):
        if m[i][j] == "#":
            q.append([i,j])
            d[i][j] = 0

while q:
    v = q.popleft()
    count = 0
    for i in m:
        jj = set(i)
        if len(jj) == 2:
            break
    else:
        break
    for i in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny = v[0] + i[0]
        nx = v[1] + i[1]
        if (0<=ny<h and 0<=nx<w and m[ny][nx] == "."):
            m[ny][nx] = "#"
            q.append([ny,nx])
            d[ny][nx] = d[v[0]][v[1]] + 1

######
ans = 0
for i in d:
    ans = max(ans,max(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = [int(x) for x in input().split()]
m = [list(input()) for x in range(h)]

q = deque()
d = [[-1]*w for x in range(h)]

for i in range(h):
    for j in range(w):
        if m[i][j] == "#":
            q.append([i,j])
            d[i][j] = 0

while q:
    v = q.popleft()
    count = 0
    for i in m:
        jj = set(i)
        if len(jj) == 2:
            break
    else:
        break
    for i in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny = v[0] + i[0]
        nx = v[1] + i[1]
        if (0<=ny<h and 0<=nx<w and m[ny][nx] == "."):
            m[ny][nx] = "#"
            q.append([ny,nx])
            d[ny][nx] = d[v[0]][v[1]] + 1

######
ans = 0
for i in d:
    ans = max(ans,max(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = [int(x) for x in input().split()]
m = [list(input()) for x in range(h)]

q = deque()
d = [[-1]*w for x in range(h)]

for i in range(h):
    for j in range(w):
        if m[i][j] == "#":
            q.append([i,j])
            d[i][j] = 0

while q:
    v = q.popleft()
    count = 0
    for i in m:
        count += i.count("#")
    if count == h*w:
        break
    for i in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny = v[0] + i[0]
        nx = v[1] + i[1]
        if (0<=ny<h and 0<=nx<w and m[ny][nx] == "."):
            m[ny][nx] = "#"
            q.append([ny,nx])
            d[ny][nx] = d[v[0]][v[1]] + 1

######
ans = 0
for i in d:
    ans = max(ans,max(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs():
    while len(que) != 0:
        p = que.popleft()
        for i in range(4):
            nextX = p[0] + moveR[i]
            nextY = p[1] + moveC[i]
            if 0 <= nextX and nextX < H\
                and 0 <= nextY and nextY < W\
                and s[nextX][nextY] != '#'\
                and s[nextX][nextY] == '.':
                s[nextX][nextY] = s[p[0]][p[1]] + 1
                que.append([nextX, nextY])

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
moveR = [0, 1, -1, 0]
moveC = [1, 0, 0, -1]

que = deque()
for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            que.append([i, j])
            s[i][j] = 0
bfs()
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, s[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

def bfs():
    while queueX.empty() == False:
        x = queueX.get()
        y = queueY.get()

        for i in range(4):
            nextX = x + moveR[i]
            nextY = y + moveC[i]
            if 0 <= nextX and nextX < H\
                and 0 <= nextY and nextY < W\
                and s[nextX][nextY] != '#'\
                and s[nextX][nextY] == '.':
                    s[nextX][nextY] = s[x][y] + 1
                    queueX.put(nextX)
                    queueY.put(nextY)

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
moveR = [0, 1, -1, 0]
moveC = [1, 0, 0, -1]

queueX = queue.Queue()
queueY = queue.Queue()
for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            queueX.put(i)
            queueY.put(j)
            s[i][j] = 0
bfs()
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, s[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

def bfs(s1,s2):
    queueX = queue.Queue()
    queueY = queue.Queue()
    queueX.put(s1)
    queueY.put(s2)
    s[s1][s2] = 0
    while queueX.empty() == False:
        x = queueX.get()
        y = queueY.get()

        for i in range(4):
            nextX = x + moveR[i]
            nextY = y + moveC[i]
            if 0 <= nextX and nextX < H\
                and 0 <= nextY and nextY < W\
                and s[nextX][nextY] != '#'\
                and (s[nextX][nextY] == '.' or s[nextX][nextY] > s[x][y] + 1):
                    s[nextX][nextY] = s[x][y] + 1
                    queueX.put(nextX)
                    queueY.put(nextY)

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
moveR = [0, 1, -1, 0]
moveC = [1, 0, 0, -1]

cnt = 0
cntlst = []
for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            cntlst.append([i, j])
            cnt += 1
if cnt == (W * H):
    print(0)
    exit()

for i in cntlst:
    bfs(i[0], i[1])
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, s[i][j])

print(ans)