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:
from collections import deque
def gridbfs(grid):
    INF = 10**18

    gridy = len(grid)
    gridx = len(grid[0])

    dist = [[INF]*gridx for _ in range(gridy)]
    q = deque()
    for y in range(gridy):
        for x in range(gridx):
            if grid[y][x] == '#':
                dist[y][x] = 0
                q.append((y,x))

    while q:
        y,x = q.popleft()
        for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
            ny,nx = y+dy, x+dx
            if not (0 <= ny < gridy and 0 <= nx < gridx):
                continue
            if dist[ny][nx] != INF:
                continue
            dist[ny][nx] = dist[y][x] + 1
            q.append((ny,nx))

    return dist

H,W = map(int,input().split())
Grid = [input() for _ in range(H)]
d = gridbfs(Grid)
print(max(max(d[i]) for i in range(H)))

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
field=[list(input()) for i in range(h)]
queue=[]
check=[[True for i in range(w)]for j in range(h)]
for i in range(h):
  for j in range(w):
    if field[i][j]=='#':
      check[i][j]=False
      queue.append([i,j])
p=[[0,1],[0,-1],[1,0],[-1,0]]
ans=0
while len(queue)>0:
  ans+=1
  manu=queue.copy()
  queue.clear()
  save=True
  for now in manu:
    for i in range(4):
      x=now[0]+p[i][0]
      y=now[1]+p[i][1]
      if x>-1 and x<h and y>-1 and y<w and check[x][y]:
        field[x][y]='#'
        queue.append([x,y])
        save=False
        check[x][y]=False
  if save:
    ans-=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
field=[list(input()) for i in range(h)]
queue=[]
for i in range(h):
  for j in range(w):
    if field[i][j]=='#':
      queue.append([i,j])
p=[[0,1],[0,-1],[1,0],[-1,0]]
ans=0
check=[[True for i in range(w)]for j in range(h)]
while len(queue)>0:
  ans+=1
  manu=queue.copy()
  queue.clear()
  save=True
  for now in manu:
    for i in range(4):
      x=now[0]+p[i][0]
      y=now[1]+p[i][1]
      if x>-1 and x<h and y>-1 and y<w and check[x][y] and field[x][y]=='.':
        field[x][y]='#'
        queue.append([x,y])
        save=False
        check[x][y]=False
  if save:
    ans-=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
field=[list(input()) for i in range(h)]
queue=[]
for i in range(h):
  for j in range(w):
    if field[i][j]=='#':
      queue.append([i,j])
p=[[0,1],[0,-1],[1,0],[-1,0]]
ans=0
while len(queue)>0:
  ans+=1
  manu=queue.copy()
  queue.clear()
  save=True
  for now in manu:
    for i in range(4):
      x=now[0]+p[i][0]
      y=now[1]+p[i][1]
      if x>-1 and x<h and y>-1 and y<w and field[x][y]=='.':
        field[x][y]='#'
        queue.append([x,y])
        save=False
  if save:
    ans-=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
A = [[0] * (W + 2)] + [[0] + [H * W] * W + [0] for _ in range(H)] + [[0] * (W + 2)]
que = deque()
for i in range(1, H+1):
    for j, a in enumerate(list(input())):
        if a == '#':
            A[i][j+1] = 0
            que.append((i, j + 1))

step = [(1, 0), (-1, 0), (0, 1), (0, -1)]
res = 0
while que:
    h, w = que.popleft()
    for dh, dw in step:
        nh = h + dh
        nw = w + dw
        if A[h][w] + 1 < A[nh][nw]:
            A[nh][nw] = A[h][w] + 1
            res = max(res, A[nh][nw])
            que.append((nh, nw))
print(res)

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:
        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().rstrip().split())
M = [[False for _ in range(W)]for _ in range(H)]
que = []
k = [0,0,0]
counter = 0
for i in range(H):
    S = input()
    for i2 in range(W):
        if S[i2] == "#":
            M[i][i2] = True
            que.append([i,i2,0])
while counter != H * W:
    k = que[counter]
    if(k[0] + 1 != H and M[k[0] + 1][k[1]] == False):
        M[k[0] + 1][k[1]] = True
        que.append([k[0] + 1,k[1],k[2] + 1])
    if(k[0] - 1 != -1 and M[k[0] - 1][k[1]] == False):
        M[k[0] - 1][k[1]] = True
        que.append([k[0] - 1,k[1],k[2] + 1])
    if(k[1] + 1 != W and M[k[0]][k[1] + 1] == False):
        M[k[0]][k[1] + 1] = True
        que.append([k[0],k[1] + 1,k[2] + 1])
    if(k[1] - 1 != -1 and M[k[0]][k[1] - 1] == False):
        M[k[0]][k[1] - 1] = True
        que.append([k[0],k[1] - 1,k[2] + 1])
    counter += 1
print(k[2])

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().rstrip().split())
M = [[False for _ in range(W)]for _ in range(H)]
que = []
k = [0,0,0]
for i in range(H):
    S = input()
    for i2 in range(W):
        if S[i2] == "#":
            M[i][i2] = True
            que.append([i,i2,0])
while len(que) != 0:
    k = que[0]
    if(k[0] + 1 != H and M[k[0] + 1][k[1]] == False):
        M[k[0] + 1][k[1]] = True
        que.append([k[0] + 1,k[1],k[2] + 1])
    if(k[0] - 1 != -1 and M[k[0] - 1][k[1]] == False):
        M[k[0] - 1][k[1]] = True
        que.append([k[0] - 1,k[1],k[2] + 1])
    if(k[1] + 1 != W and M[k[0]][k[1] + 1] == False):
        M[k[0]][k[1] + 1] = True
        que.append([k[0],k[1] + 1,k[2] + 1])
    if(k[1] - 1 != -1 and M[k[0]][k[1] - 1] == False):
        M[k[0]][k[1] - 1] = True
        que.append([k[0],k[1] - 1,k[2] + 1])
    que.pop(0)
print(k[2])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs():
    d = [[float("inf") for i in range(W)] for j in range(H)]
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    que = deque([])
    ans = 0

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

    while que:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0<=nx<W and 0<=ny<H and S[ny][nx] != "#" and d[ny][nx] == float("inf"):
                que.append((nx,ny))
                d[ny][nx] = d[p[1]][p[0]] + 1
                if d[ny][nx] > ans:
                    ans = d[ny][nx]
    return ans

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

print(bfs())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs():
    d = [[float("inf") for i in range(W)] for j in range(H)]
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    que = deque([])
    ans = 0

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

    while que:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0<=nx<W and 0<=ny<H and S[ny][nx] != "#" and d[ny][nx] == float("inf"):
                que.append((nx,ny))
                d[ny][nx] = d[p[1]][p[0]] + 1
                ans = max(ans,d[ny][nx])
    return ans

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

print(bfs())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs():
    d = [[float("inf") for i in range(W)] for j in range(H)]
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    que = deque([])

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

    while que:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0<=nx<W and 0<=ny<H and S[ny][nx] != "#" and d[ny][nx] == float("inf"):
                que.append((nx,ny))
                d[ny][nx] = d[p[1]][p[0]] + 1
    ans = 0
    for i in range(W):
        for j in range(H):
            if S[j][i] !="#":
                ans = max(ans,d[j][i])
    return ans

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

print(bfs())

Submission status: Time Limit Exceeded

Solution code:
## coding: UTF-8

 
s = input().split()
p = [int(w) for w in s] #これで勝手にNまで拾ってくれます
H = p[0]
W = p[1]
 
a = []
for i in range(H):
    a.append(input())
 
 
#白ベースで最寄りの黒を探す方針
#パディングは'.'でも'#'でもないもので埋める
b = 'w' * (W+2)


#print(b)
#上と下と右と左に空きマスを挿入する
a.insert(0, b)
for i in range(1, 1+H):
    a[i] = 'w' + a[i] + 'w'
a.append(b)
 
 
header = ' '
for i in range(len(a[0])):
    header += ('{}'.format(i))
 
c=[]
for i in range(H+2):
    c.append([])
 
for i in range(H+2):
    for j in range(W+2):
        c[i].append(a[i][j])
 
 
def see_banmen():
    print(header)
    for i in range(len(c)):
        print('{}{}'.format(i,''.join(c[i])))
#see_banmen()
 
 
 
#queue = [start]
next_list = [] #次の歩数で探すものを格納しておく
step = 1
#mode = 0
#answer_mode = 0
status = True #ゴール判定でゴールについていたらFalseにする
#answer = -1
 
queue = []
for i in range(H+2):
    for j in range(W+2):
        if(c[i][j] == '#'):
            queue.append([i, j])
 
while status:
    if(len(queue) > 0):
        pivot = queue.pop(0) #軸足はqueueの先頭
        x = pivot[0]
        y = pivot[1]
        if(c[x+1][y] == '.'):
            c[x+1][y] = str(step)
            next_list.append([x+1, y])
        if(c[x-1][y] == '.'):
            c[x-1][y] = str(step)
            next_list.append([x-1, y])
        if(c[x][y+1] == '.'):
            c[x][y+1] = str(step)
            next_list.append([x, y+1])
        if(c[x][y-1] == '.'):
            c[x][y-1] = str(step)
            next_list.append([x, y-1])
    else:
        #queueの中身が空っぽになった
        #基本的にはstep += 1
        if(len(next_list) > 0):
            #next_listの中身がある場合（まだ探索が終了していない場合）
            #next_list -> queue にして next_listはからにする
            for i in range(len(next_list)):
                queue.append(next_list.pop())
            next_list = []
            #print()
            #print('step{}end'.format(step))
            #see_banmen()
            #次の探索に移る
            step += 1
        else:
            #初めてnext_listの中身がなくなった場合（探索は終了したい）
            #もう進めない
            #print()
            #print('もう進めない')
            #print('step{}end'.format(step))
            #see_banmen()
            status = False
 
print(step - 1)

Submission status: Time Limit Exceeded

Solution code:
## coding: UTF-8
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product
import math
#from math import gcd 旧環境でこれを有効化するとREを吐きます
 
s = input().split()
p = [int(w) for w in s] #これで勝手にNまで拾ってくれます
H = p[0]
W = p[1]
 
a = []
for i in range(H):
    a.append(input())
 
 
#白ベースで最寄りの黒を探す方針
#パディングは'.'でも'#'でもないもので埋める
'''
b = ''
for i in range(W+2):
    b += 'w'
'''
b = 'w' * (W+2)
#print(b)
#上と下と右と左に空きマスを挿入する
a.insert(0, b)
for i in range(1, 1+H):
    a[i] = 'w' + a[i] + 'w'
a.append(b)
 
 
header = ' '
for i in range(len(a[0])):
    header += ('{}'.format(i))
 
c=[]
for i in range(H+2):
    c.append([])
 
for i in range(H+2):
    for j in range(W+2):
        c[i].append(a[i][j])
 
 
def see_banmen():
    print(header)
    for i in range(len(c)):
        print('{}{}'.format(i,''.join(c[i])))
#see_banmen()
 
 
 
#queue = [start]
next_list = [] #次の歩数で探すものを格納しておく
step = 1
#mode = 0
#answer_mode = 0
status = True #ゴール判定でゴールについていたらFalseにする
#answer = -1
 
queue = []
for i in range(H+2):
    for j in range(W+2):
        if(c[i][j] == '#'):
            queue.append([i, j])
 
while status:
    if(len(queue) > 0):
        pivot = queue.pop() #軸足はqueueの先頭
        x = pivot[0]
        y = pivot[1]
        if(c[x+1][y] == '.'):
            c[x+1][y] = str(step)
            next_list.append([x+1, y])
        if(c[x-1][y] == '.'):
            c[x-1][y] = str(step)
            next_list.append([x-1, y])
        if(c[x][y+1] == '.'):
            c[x][y+1] = str(step)
            next_list.append([x, y+1])
        if(c[x][y-1] == '.'):
            c[x][y-1] = str(step)
            next_list.append([x, y-1])
    else:
        #queueの中身が空っぽになった
        #基本的にはstep += 1
        if(len(next_list) > 0):
            #next_listの中身がある場合（まだ探索が終了していない場合）
            #next_list -> queue にして next_listはからにする
            for i in range(len(next_list)):
                queue.append(next_list.pop(0))
            next_list = []
            #print()
            #print('step{}end'.format(step))
            #see_banmen()
            #次の探索に移る
            step += 1
        else:
            #初めてnext_listの中身がなくなった場合（探索は終了したい）
            #もう進めない
            #print()
            #print('もう進めない')
            #print('step{}end'.format(step))
            #see_banmen()
            status = False
 
print(step - 1)

Submission status: Time Limit Exceeded

Solution code:
## coding: UTF-8
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product
import math
#from math import gcd 旧環境でこれを有効化するとREを吐きます
 
s = input().split()
p = [int(w) for w in s] #これで勝手にNまで拾ってくれます
H = p[0]
W = p[1]
 
a = []
for i in range(H):
    a.append(input())
 
 
#白ベースで最寄りの黒を探す方針
#パディングは'.'でも'#'でもないもので埋める
b = 'w' * (W+2)


#print(b)
#上と下と右と左に空きマスを挿入する
a.insert(0, b)
for i in range(1, 1+H):
    a[i] = 'w' + a[i] + 'w'
a.append(b)
 
 
header = ' '
for i in range(len(a[0])):
    header += ('{}'.format(i))
 
c=[]
for i in range(H+2):
    c.append([])
 
for i in range(H+2):
    for j in range(W+2):
        c[i].append(a[i][j])
 
 
def see_banmen():
    print(header)
    for i in range(len(c)):
        print('{}{}'.format(i,''.join(c[i])))
#see_banmen()
 
 
 
#queue = [start]
next_list = [] #次の歩数で探すものを格納しておく
step = 1
#mode = 0
#answer_mode = 0
status = True #ゴール判定でゴールについていたらFalseにする
#answer = -1
 
queue = []
for i in range(H+2):
    for j in range(W+2):
        if(c[i][j] == '#'):
            queue.append([i, j])
 
while status:
    if(len(queue) > 0):
        pivot = queue.pop(0) #軸足はqueueの先頭
        x = pivot[0]
        y = pivot[1]
        if(c[x+1][y] == '.'):
            c[x+1][y] = str(step)
            next_list.append([x+1, y])
        if(c[x-1][y] == '.'):
            c[x-1][y] = str(step)
            next_list.append([x-1, y])
        if(c[x][y+1] == '.'):
            c[x][y+1] = str(step)
            next_list.append([x, y+1])
        if(c[x][y-1] == '.'):
            c[x][y-1] = str(step)
            next_list.append([x, y-1])
    else:
        #queueの中身が空っぽになった
        #基本的にはstep += 1
        if(len(next_list) > 0):
            #next_listの中身がある場合（まだ探索が終了していない場合）
            #next_list -> queue にして next_listはからにする
            for i in range(len(next_list)):
                queue.append(next_list.pop())
            next_list = []
            #print()
            #print('step{}end'.format(step))
            #see_banmen()
            #次の探索に移る
            step += 1
        else:
            #初めてnext_listの中身がなくなった場合（探索は終了したい）
            #もう進めない
            #print()
            #print('もう進めない')
            #print('step{}end'.format(step))
            #see_banmen()
            status = False
 
print(step - 1)

Submission status: Time Limit Exceeded

Solution code:
## coding: UTF-8
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product
import math
#from math import gcd 旧環境でこれを有効化するとREを吐きます
 
s = input().split()
p = [int(w) for w in s] #これで勝手にNまで拾ってくれます
H = p[0]
W = p[1]
 
a = []
for i in range(H):
    a.append(input())
 
 
#白ベースで最寄りの黒を探す方針
#パディングは'.'でも'#'でもないもので埋める
b = ''
for i in range(W+2):
    b += 'w'
#print(b)
#上と下と右と左に空きマスを挿入する
a.insert(0, b)
for i in range(1, 1+H):
    a[i] = 'w' + a[i] + 'w'
a.append(b)
 
 
header = ' '
for i in range(len(a[0])):
    header += ('{}'.format(i))
 
c=[]
for i in range(H+2):
    c.append([])
 
for i in range(H+2):
    for j in range(W+2):
        c[i].append(a[i][j])
 
 
def see_banmen():
    print(header)
    for i in range(len(c)):
        print('{}{}'.format(i,''.join(c[i])))
#see_banmen()
 
 
 
#queue = [start]
next_list = [] #次の歩数で探すものを格納しておく
step = 1
#mode = 0
#answer_mode = 0
status = True #ゴール判定でゴールについていたらFalseにする
#answer = -1
 
queue = []
for i in range(H+2):
    for j in range(W+2):
        if(c[i][j] == '#'):
            queue.append([i, j])
 
while status:
    if(len(queue) > 0):
        pivot = queue.pop() #軸足はqueueの先頭
        x = pivot[0]
        y = pivot[1]
        if(c[x+1][y] == '.'):
            c[x+1][y] = str(step)
            next_list.append([x+1, y])
        if(c[x-1][y] == '.'):
            c[x-1][y] = str(step)
            next_list.append([x-1, y])
        if(c[x][y+1] == '.'):
            c[x][y+1] = str(step)
            next_list.append([x, y+1])
        if(c[x][y-1] == '.'):
            c[x][y-1] = str(step)
            next_list.append([x, y-1])
    else:
        #queueの中身が空っぽになった
        #基本的にはstep += 1
        if(len(next_list) > 0):
            #next_listの中身がある場合（まだ探索が終了していない場合）
            #next_list -> queue にして next_listはからにする
            for i in range(len(next_list)):
                queue.append(next_list.pop(0))
            next_list = []
            #print()
            #print('step{}end'.format(step))
            #see_banmen()
            #次の探索に移る
            step += 1
        else:
            #初めてnext_listの中身がなくなった場合（探索は終了したい）
            #もう進めない
            #print()
            #print('もう進めない')
            #print('step{}end'.format(step))
            #see_banmen()
            status = False
 
print(step - 1)

Submission status: Time Limit Exceeded

Solution code:
## coding: UTF-8
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product
import math
#from math import gcd 旧環境でこれを有効化するとREを吐きます
 
s = input().split()
p = [int(w) for w in s] #これで勝手にNまで拾ってくれます
H = p[0]
W = p[1]
 
a = []
for i in range(H):
    a.append(input())
 
 
#白ベースで最寄りの黒を探す方針
#パディングは'.'でも'#'でもないもので埋める
b = ''
for i in range(W+2):
    b += 'w'
#print(b)
#上と下と右と左に空きマスを挿入する
a.insert(0, b)
for i in range(1, 1+H):
    a[i] = 'w' + a[i] + 'w'
a.append(b)
 
 
header = ' '
for i in range(len(a[0])):
    header += ('{}'.format(i))
 
c=[]
for i in range(H+2):
    c.append([])
 
for i in range(H+2):
    for j in range(W+2):
        c[i].append(a[i][j])
 
 
def see_banmen():
    print(header)
    for i in range(len(c)):
        print('{}{}'.format(i,''.join(c[i])))
#see_banmen()
 
 
 
#queue = [start]
next_list = [] #次の歩数で探すものを格納しておく
step = 1
#mode = 0
#answer_mode = 0
status = True #ゴール判定でゴールについていたらFalseにする
#answer = -1
 
queue = []
for i in range(H+2):
    for j in range(W+2):
        if(c[i][j] == '#'):
            queue.append([i, j])
 
while status:
    if(len(queue) > 0):
        pivot = queue.pop(0) #軸足はqueueの先頭
        x = pivot[0]
        y = pivot[1]
        if(c[x+1][y] == '.'):
            c[x+1][y] = str(step)
            next_list.append([x+1, y])
        if(c[x-1][y] == '.'):
            c[x-1][y] = str(step)
            next_list.append([x-1, y])
        if(c[x][y+1] == '.'):
            c[x][y+1] = str(step)
            next_list.append([x, y+1])
        if(c[x][y-1] == '.'):
            c[x][y-1] = str(step)
            next_list.append([x, y-1])
    else:
        #queueの中身が空っぽになった
        #基本的にはstep += 1
        if(len(next_list) > 0):
            #next_listの中身がある場合（まだ探索が終了していない場合）
            #next_list -> queue にして next_listはからにする
            for i in range(len(next_list)):
                queue.append(next_list.pop())
            next_list = []
            #print()
            #print('step{}end'.format(step))
            #see_banmen()
            #次の探索に移る
            step += 1
        else:
            #初めてnext_listの中身がなくなった場合（探索は終了したい）
            #もう進めない
            #print()
            #print('もう進めない')
            #print('step{}end'.format(step))
            #see_banmen()
            status = False
 
print(step - 1)

Submission status: Time Limit Exceeded

Solution code:
import queue
from collections import deque
h,w = map(int,input().split())

#aij = [input() for i in range(h)]

moji = [[0 for i in range(w)] for j in range(h)]

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

for i in range(h):
    aij = input()
    #print(aij)
    for j in range(w):
        moji[i][j] = aij[j]

#moji = aij
#print(moji,aij)
#exit()

#print(aij)
vx = [0,1,0,-1]
vy = [1,0,-1,0]

ans = 0
q = deque()

for i in range(h*w):
    y = i//w
    x = i%w
    #print(i)
    if moji[y][x] == '#':
        q.append(i)
        dist[y][x] = 0

#ans = -1

ans = 0

while q:
    #print(q.qsize())
    tmp = q.popleft()
    y = tmp//w
    x = tmp%w
    d = dist[y][x]
    #print(tmp,num)
    for j in range(4):
        nx = x+vx[j]
        ny = y+vy[j]
        #print(ny,nx)
        if nx < 0 or nx >= w or ny < 0 or ny >= h:
            continue
        if dist[ny][nx] == -1:
            dist[ny][nx] = d+1
            #moji[ny][nx] = '#'
            q.append(ny*w+nx)
    #ans += 1
    ans = max(d,ans)

print(ans)

Submission status: Time Limit Exceeded

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

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

# "#"の位置をキューに追加
black = deque()
for h in range(H):
    for w in range(W):
        if a[h][w] == "#":
            black.append((h,w))
            dist[h][w] = 0
def bfs(black, dist):
    d = 0
    while black: #blackに中身が入っている間
        #キューとして使うから左から出すpopleft()
        h, w = black.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.append((new_h, new_w))
    return d

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

Submission status: Time Limit Exceeded

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

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

# "#"の位置をキューに追加
black = deque()
for h in range(H):
    for w in range(W):
        if a[h][w] == "#":
            black.appendleft((h,w))
            dist[h][w] = 0
def bfs(black, dist):
    d = 0
    while black: #blackに中身が入っている間
        h, w = black.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.append((new_h, new_w))
    return d

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

Submission status: Time Limit Exceeded

Solution code:
## coding: UTF-8
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product
import math
#import collections
#from math import gcd 旧環境でこれを有効化するとREを吐きます
#import sys
#input = sys.stdin.readline


def main():
    s = input().split()
    p = [int(w) for w in s] #これで勝手にNまで拾ってくれます
    H = p[0]
    W = p[1]

    '''
    queue = []
    #input = sys.stdin.readline
    A = [list(input()) for _ in range(H)]
    #print('A:{}'.format(A))
    c = [['w'] * (W+2)]
    #print('c:{}'.format(c))
    for i in range(H):
        c.append(['w'])
        for j in range(W):
            if(A[i][j] == '#'):
                queue.append([i+1, j+1])
            c[-1].append(A[i][j])
        c[-1].append('w')
    c.append(['w'] * (W+2))
    #print('c:{}'.format(c))
    #print('queue:{}'.format(queue))
    '''
    
    a = []
    for i in range(H):
        a.append(input())


    #白ベースで最寄りの黒を探す方針
    #パディングは'.'でも'#'でもないもので埋める
    b = ''
    for i in range(W+2):
        b += 'w'
    #print(b)
    #上と下と右と左に空きマスを挿入する
    a.insert(0, b)
    for i in range(1, 1+H):
        a[i] = 'w' + a[i] + 'w'
    a.append(b)


    header = ' '
    for i in range(len(a[0])):
        header += ('{}'.format(i))

    c=[]
    for i in range(H+2):
        c.append([])
    queue = []
    for i in range(H+2):
        for j in range(W+2):
            if(a[i][j] == '#'):
                queue.append([i, j])
            c[i].append(a[i][j])


    def see_banmen():
        print(header)
        for i in range(len(c)):
            print('{}{}'.format(i,''.join(c[i])))
    #see_banmen()
    


    #queue = [start]
    next_list = [] #次の歩数で探すものを格納しておく
    step = 1
    #mode = 0
    #answer_mode = 0
    status = True #ゴール判定でゴールについていたらFalseにする
    #answer = -1




    '''
    for i in range(H+2):
        for j in range(W+2):
            if(c[i][j] == '#'):
                queue.append([i, j])
    '''
    while status:
        if(len(queue) > 0):
            pivot = queue.pop(0) #軸足はqueueの先頭
            x = pivot[0]
            y = pivot[1]
            if(c[x+1][y] == '.'):
                c[x+1][y] = 'd'
                next_list.append([x+1, y])
            if(c[x-1][y] == '.'):
                c[x-1][y] = 'd'
                next_list.append([x-1, y])
            if(c[x][y+1] == '.'):
                c[x][y+1] = 'd'
                next_list.append([x, y+1])
            if(c[x][y-1] == '.'):
                c[x][y-1] = 'd'
                next_list.append([x, y-1])
        else:
            #queueの中身が空っぽになった
            #基本的にはstep += 1
            if(len(next_list) > 0):
                #next_listの中身がある場合（まだ探索が終了していない場合）
                #next_list -> queue にして next_listはからにする
                '''
                for i in range(len(next_list)):
                    queue.append(next_list.pop(0))
                next_list = []
                '''
                queue = next_list
                next_list = []
                

                #print()
                #print('step{}end'.format(step))
                #see_banmen()
                #次の探索に移る
                step += 1
            else:
                #初めてnext_listの中身がなくなった場合（探索は終了したい）
                #もう進めない
                #print()
                #print('もう進めない')
                #print('step{}end'.format(step))
                #see_banmen()
                status = False

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

Submission status: Time Limit Exceeded

Solution code:
import queue
h,w = map(int,input().split())

#aij = [input() for i in range(h)]

moji = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    aij = input()
    #print(aij)
    for j in range(w):
        moji[i][j] = aij[j]

#moji = aij
#print(moji,aij)
#exit()

#print(aij)
vx = [0,1,0,-1]
vy = [1,0,-1,0]

ans = 0

for i in range(h*w):
    y = i//w
    x = i%w
    #print(i)
    if moji[y][x] == '#':
        continue
    else:
        q = queue.Queue()
        q.put([i,1])
        flag = False
        
        while flag == False:
            tmp,num = q.get()
            x = tmp//w
            y = tmp%w
            #print(tmp,num)
            for j in range(4):
                nx = x+vx[j]
                ny = y+vy[j]
                #print(ny,nx)
                if nx < 0 or nx >= w or ny < 0 or ny >= h:
                    continue
                if moji[ny][nx] == "#":
                    flag = True
                    break
                else:
                    q.put([ny*w+nx,num+1])
                    
        ans = max(ans,num)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
h,w = map(int,input().split())

#aij = [input() for i in range(h)]

moji = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    aij = input()
    #print(aij)
    for j in range(w):
        moji[i][j] = aij[j]

#moji = aij
#print(moji,aij)
#exit()

#print(aij)
vx = [0,1,0,-1]
vy = [1,0,-1,0]

ans = 0
flag = False

while flag == False:
    #print(moji)
    moji_old = copy.deepcopy(moji)
    for i in range(h*w):
        y = i//w
        x = i%w
        if moji_old[y][x] == '.':
            flag = False
            break
        else:
            flag = True
    
    for i in range(h*w):
        y = i//w
        x = i%w
        #print(i)
        if moji_old[y][x] == '#':
            for j in range(4):
                nx = x+vx[j]
                ny = y+vy[j]
                #print(ny,nx)
                if nx < 0 or nx >= w or ny < 0 or ny >= h:
                    continue
                if moji[ny][nx] == "#":
                    continue
                moji[ny][nx] = '#'
    
    if flag == True:
        break
                
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
h,w = map(int,input().split())

#aij = [input() for i in range(h)]

moji = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    aij = input()
    #print(aij)
    for j in range(w):
        moji[i][j] = aij[j]

#moji = aij
#print(moji,aij)
#exit()

#print(aij)
vx = [0,1,0,-1]
vy = [1,0,-1,0]

ans = 0
flag = False

while flag == False:
    #print(moji)
    moji_old = copy.deepcopy(moji)
    for i in range(h*w):
        y = i//w
        x = i%w
        if moji_old[y][x] == '.':
            flag = False
            break
        else:
            flag = True
    
    for i in range(h*w):
        y = i//w
        x = i%w
        #print(i)
        if moji_old[y][x] == '#':
            for j in range(4):
                nx = x+vx[j]
                ny = y+vy[j]
                #print(ny,nx)
                if nx < 0 or nx >= w or ny < 0 or ny >= h:
                    continue
                if moji[ny][nx] == ".":
                    continue
                moji[ny][nx] = '#'
    
    if flag == True:
        break
                
    ans += 1
    
print(ans)