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:
import sys
from collections import deque

input = sys.stdin.readline

h, w = map(int, input().split())
# 蛮兵
painted = [['#'] * (w + 2)]
painted += [['#'] + list(input().rstrip()) + ['#'] for _ in range(h)]
painted.append(['#'] * (w + 2))
que = deque()

for y in range(1, h + 1):
    for x in range(1, w + 1):
        if painted[y][x] == '#':
            painted[y][x] = 0
            que.append((y, x))
cnt = 0
while que:
    y, x = que.popleft()
    if painted[y - 1][x] == '.':
        painted[y - 1][x] = painted[y][x] + 1
        que.append((y - 1, x))
    if painted[y + 1][x] == '.':
        painted[y + 1][x] = painted[y][x] + 1
        que.append((y + 1, x))
    if painted[y][x + 1] == '.':
        painted[y][x + 1] = painted[y][x] + 1
        que.append((y, x + 1))
    if painted[y][x - 1] == '.':
        painted[y][x - 1] = painted[y][x] + 1
        que.append((y, x - 1))
print(painted[y][x])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

h, w = map(int, input().split())
# 蛮兵
painted = [['#'] * (w + 2)]
painted += [['#'] + list(input().rstrip()) + ['#'] for _ in range(h)]
painted.append(['#'] * (w + 2))

que = deque()

for y in range(1, h + 1):
    for x in range(1, w + 1):
        if painted[y][x] == '#':
            painted[y][x] = 0
            que.append((y, x))

cnt = 0
while que:
    y, x = que.popleft()
    for iy, ix in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        ny = y + iy
        nx = x + ix
        if painted[ny][nx] == '.':
            painted[ny][nx] = painted[y][x] + 1
            que.append((ny, nx))

print(painted[y][x])

Submission status: Time Limit Exceeded

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

h, w = map(int, input().split())
painted = [list(input()) for _ in range(h)]
starts = []
for y in range(h):
    for x in range(w):
        if painted[y][x] == '#':
            starts.append((y, x))


def paint_black(starts):
    que = deque()
    for start in starts:
        que.append(start)
    cnt = 0
    while not all([i == '#' for row in painted for i in row]):
        next_position = []
        cnt += 1
        while que:
            y, x = que.popleft()
            for iy, ix in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                ny = y + iy
                nx = x + ix
                if (0 <= ny < h) and (0 <= nx < w):
                    if painted[ny][nx] != '#':
                        painted[ny][nx] = '#'
                        next_position.append((ny, nx))

        for start in next_position:
            que.append(start)
    return cnt

cnt = paint_black(starts)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
painted = [list(input()) for _ in range(h)]
starts = []
for y in range(h):
    for x in range(w):
        if painted[y][x] == '#':
            starts.append((y, x))


def paint_black(starts):
    que = deque()
    for start in starts:
        que.append(start)
    cnt = 0
    while not all([i == '#' for row in painted for i in row]):
        next_position = []
        cnt += 1
        while que:
            y, x = que.popleft()
            for iy, ix in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                ny = y + iy
                nx = x + ix
                if (0 <= ny < h) and (0 <= nx < w):
                    if painted[ny][nx] != '#':
                        painted[ny][nx] = '#'
                        next_position.append((ny, nx))

        for start in next_position:
            que.append(start)
    return cnt

cnt = paint_black(starts)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

l = [input() for i in range(h)]
memo = [[-1]*w for i in range(h)]

black_cells = deque()
for i in range(h):
    for j in range(w):
        if l[i][j] == "#":
            black_cells.append((i, j))
            memo[i][j] = 0

while black_cells:
    nh, nw = black_cells.popleft()
    count = memo[nh][nw]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_nh = nh + dy
        new_nw = nw + dx
        if new_nh < 0 or h <= new_nh or new_nw < 0 or w <= new_nw:
            continue
        if memo[new_nh][new_nw] == -1:
            memo[new_nh][new_nw] = count + 1
            black_cells.append((new_nh, new_nw))
print(count)

Submission status: Time Limit Exceeded

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

l = [input() for i in range(h)]
memo = [[False]*w for i in range(h)]

queue = []
sa = queue.append
for i in range(h):
    for j in range(w):
        if l[i][j] == "#":
            sa((i, j))
            memo[i][j] = True

cl = [[True]*w for i in range(h)]

ql = []
qa = ql.append
count = 0
while 1:
    if memo == cl:
        print(count)
        break
    for i in queue:
        qa(i)
    queue = []
    sa = queue.append
    
    for nh, nw in ql:
        if nh > 0:
            if l[nh-1][nw] != "#":
                if memo[nh-1][nw] == False:
                    sa((nh-1, nw))
                    memo[nh-1][nw] = True
        if nw > 0:
            if l[nh][nw-1] != "#":
                if memo[nh][nw-1] == False:
                    sa((nh, nw-1))
                    memo[nh][nw-1] = True
        if nh < h-1:
            if l[nh+1][nw] != "#":
                if memo[nh+1][nw] == False:
                    sa((nh+1, nw))
                    memo[nh+1][nw] = True
        if nw < w-1:
            if l[nh][nw+1] != "#":
                if memo[nh][nw+1] == False:
                    sa((nh, nw+1))
                    memo[nh][nw+1] = True

    count += 1

Submission status: Time Limit Exceeded

Solution code:
H, W = list(map(int, input().split()))
 
start = []
c = []
for y in range(H):
    c.append(input())
    for x in range(W):
        if c[-1][x]=='#':
            start.append([y,x])
            
visited = [0 for _ in range(W*H)]
for one in start:
    visited[one[0]*W+one[1]] = 1
    
cnt = 0
while sum(visited)!=W*H:
    tmp_s = []
    for one in start:
        cy,cx = one
        for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            ny, nx = cy+dy, cx+dx
            if 0 <= nx < W and 0 <= ny < H and visited[ny*W+nx]==0:
                visited[ny*W+nx] = 1
                tmp_s.append([ny,nx])
    cnt+=1
    start = tmp_s
print(cnt)

Submission status: Time Limit Exceeded

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

start = []
c = []
for y in range(H):
    c.append(input())
    for x in range(W):
        if c[-1][x]=='#':
            start.append([y,x])
            
visited = [0 for _ in range(W*H)]
cnt = 0
while sum(visited)!=W*H:
    tmp_s = []
    for one in start:
        cy,cx = one
        for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            ny, nx = cy+dy, cx+dx
            if 0 <= nx < W and 0 <= ny < H and visited[ny*W+nx]==0:
                visited[ny*W+nx] = 1
                tmp_s.append([ny,nx])
    cnt+=1
    start = tmp_s
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().split())
area = [list(input()) for i in range(H)]

def searchBlackIdx(area):
    blackIdx = []
    
    for i in range(H):
        for j in range(W):
            if area[i][j] == '#':
                blackIdx.append([i, j])
    
    return blackIdx

def calcDist(startIdxes, area):
    dist = [[-1 for i in range(W)] for i in range(H)]
    for startIdx in startIdxes:
        dist[startIdx[0]][startIdx[1]] = 0
    que = startIdxes
    maxDist = 0
    while len(que) != 0:
        idx = que.pop(0)
        
        if idx[0]-1 >= 0 and dist[idx[0]-1][idx[1]] == -1 and area[idx[0]-1][idx[1]] != '#':
            dist[idx[0]-1][idx[1]] = dist[idx[0]][idx[1]] + 1
            maxDist = max(maxDist, dist[idx[0]][idx[1]] + 1)
            area[idx[0]-1][idx[1]] = '#'
            que.append([idx[0]-1, idx[1]])
        
        if idx[0]+1 < H and dist[idx[0]+1][idx[1]] == -1 and area[idx[0]+1][idx[1]] != '#':
            dist[idx[0]+1][idx[1]] = dist[idx[0]][idx[1]] + 1
            maxDist = max(maxDist, dist[idx[0]][idx[1]] + 1)
            area[idx[0]+1][idx[1]] = '#'
            que.append([idx[0]+1, idx[1]])
        
        if idx[1]-1 >= 0 and dist[idx[0]][idx[1]-1] == -1 and area[idx[0]][idx[1]-1] != '#':
            dist[idx[0]][idx[1]-1] = dist[idx[0]][idx[1]] + 1
            maxDist = max(maxDist, dist[idx[0]][idx[1]] + 1)
            area[idx[0]][idx[1]-1] = '#'
            que.append([idx[0], idx[1]-1])
        
        if idx[1]+1 < W and dist[idx[0]][idx[1]+1] == -1 and area[idx[0]][idx[1]+1] != '#':
            dist[idx[0]][idx[1]+1] = dist[idx[0]][idx[1]] + 1
            maxDist = max(maxDist, dist[idx[0]][idx[1]] + 1)
            area[idx[0]][idx[1]+1] = '#'
            que.append([idx[0], idx[1]+1])
    
    return dist, maxDist

startIdx = searchBlackIdx(area)

dist, maxDist = calcDist(startIdx, area)
print(maxDist)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
grid=[list(input()) for _ in range(h)]
q=[]
for i in range(h):
  for j in range(w):
    if grid[i][j]=='#':
      q.append((i,j,0))
dx=[-1,0,1,0]
dy=[0,1,0,-1]
ans=0
while q:
  ny,nx,cnt=q.pop(0)
  for i in range(4):
    cy=ny+dy[i]
    cx=nx+dx[i]
    if 0<=cy<h and 0<=cx<w and grid[cy][cx]=='.':
      grid[cy][cx]='#'
      q.append((cy,cx,cnt+1))
      ans=max(ans,cnt+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
grid=[list(input()) for _ in range(h)]
q=deque()
for i in range(h):
  for j in range(w):
    if grid[i][j]=='#':
      q.append((i,j,0))
dx=[-1,0,1,0]
dy=[0,1,0,-1]
ans=0
while q:
  ny,nx,cnt=q.popleft()
  for i in range(4):
    cy=ny+dy[i]
    cx=nx+dx[i]
    if 0<=cy<h and 0<=cx<w and grid[cy][cx]=='.':
      grid[cy][cx]='#'
      q.append((cy,cx,cnt+1))
      ans=max(ans,cnt+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import deepcopy


# 幅優先探索
def bfs(field, field_info, number_of_rows, number_of_columns, starting_y, starting_x):
    queue = deque([[starting_y, starting_x]])
    field_info[starting_y][starting_x] = 0

    max_distance = 0
    while queue:
        y, x = queue.popleft()
        for dy, dx in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + dy, x + dx
            if 0 <= new_y <= number_of_rows - 1 and \
                    0 <= new_x <= number_of_columns - 1 and \
                    field[new_y][new_x] == "." and \
                    field_info[new_y][new_x] == -1:
                field_info[new_y][new_x] = field_info[y][x] + 1
                queue.append([new_y, new_x])


# テーブル各要素の最小値を採用する
def update_field_info_master(field_info_master, field_info, number_of_rows, number_of_columns):
    for row_i in range(number_of_rows):
        for column_i in range(number_of_columns):
            field_info_master[row_i][column_i] = min(field_info_master[row_i][column_i], field_info[row_i][column_i])


def solve():
    number_of_rows, number_of_columns = list(map(int, input().split()))  # Row, Column数
    field = [input() for _ in range(number_of_rows)]
    field_info_template = [[-1] * number_of_columns for _ in range(number_of_rows)]
    field_info_master = [[1000 * 1000] * number_of_columns for _ in range(number_of_rows)]

    for row_i in range(number_of_rows):
        for column_i in range(number_of_columns):
            if field[row_i][column_i] == "#":  # 各々の黒マスからBFSを行う
                starting_y, starting_x = row_i, column_i
                field_info_copy = deepcopy(field_info_template)
                bfs(field, field_info_copy, number_of_rows, number_of_columns, starting_y, starting_x)
                update_field_info_master(field_info_master, field_info_copy, number_of_rows, number_of_columns)

    # 結果をチェック
    # print("***********")
    # for update_field_info_master_line in field_info_master:
    #     print(update_field_info_master_line)

    number_of_operations = -1
    for row_i in range(number_of_rows):
        for column_i in range(number_of_columns):
            number_of_operations = max(number_of_operations, field_info_master[row_i][column_i])
    print(number_of_operations)

# ここで必要なチェックを行う
solve()

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().split())
area = [list(input()) for i in range(H)]

def searchBlackIdx(area):
    blackIdx = []
    
    for i in range(H):
        for j in range(W):
            if area[i][j] == '#':
                blackIdx.append([i, j])
    
    return blackIdx

def calcDist(startIdx, area):
    dist = [[-1 for i in range(W)] for i in range(H)]
    dist[startIdx[0]][startIdx[1]] = 0
    que = [startIdx]
    
    while len(que) != 0:
        idx = que.pop(0)
        
        if idx[0]-1 >= 0 and dist[idx[0]-1][idx[1]] == -1 and area[idx[0]-1][idx[1]] != '#':
            dist[idx[0]-1][idx[1]] = dist[idx[0]][idx[1]] + 1
            que.append([idx[0]-1, idx[1]])
            
        if idx[0]+1 < H and dist[idx[0]+1][idx[1]] == -1 and area[idx[0]+1][idx[1]] != '#':
            dist[idx[0]+1][idx[1]] = dist[idx[0]][idx[1]] + 1
            que.append([idx[0]+1, idx[1]])
        
        if idx[1]-1 >= 0 and dist[idx[0]][idx[1]-1] == -1 and area[idx[0]][idx[1]-1] != '#':
            dist[idx[0]][idx[1]-1] = dist[idx[0]][idx[1]] + 1
            que.append([idx[0], idx[1]-1])
        
        if idx[1]+1 < W and dist[idx[0]][idx[1]+1] == -1 and area[idx[0]][idx[1]+1] != '#':
            dist[idx[0]][idx[1]+1] = dist[idx[0]][idx[1]] + 1
            que.append([idx[0], idx[1]+1])
    
    return dist

startIdx = searchBlackIdx(area)
ans = [[1000 for i in range(H)] for i in range(W)]
while len(startIdx) != 0:
    idx = startIdx.pop()
    dist = calcDist(idx, area)
    ans = [[min(l) for l in zip(x,y)] for x,y in zip(ans, dist)]

print(max([x for i in ans for x in i]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(1000000)
h, w = map(int, input().split())
field = []
for _ in range(h):
    field.append(list(input()))

dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
distance = [[-1] * w for i in range(h)]

que = deque([])
for y in range(h):
    for x in range(w):
        if field[y][x] == '.':
            continue
        que.append([y, x])
        distance[y][x] = 0

while que:
    q = que.popleft()
    for i in range(4):
        now_y = q[0] + dy[i]
        now_x = q[1] + dx[i]
        if now_y < 0 or now_y >= h or now_x < 0 or now_x >= w or field[now_y][now_x] == '#':
            continue
        if distance[now_y][now_x] != -1:
            continue
        que.append([now_y, now_x])
        distance[now_y][now_x] = distance[q[0]][q[1]] + 1

draw_count = 0
for y in range(h):
    for x in range(w):
        draw_count = max(draw_count, distance[y][x])
print(draw_count)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import numpy as np
input = sys.stdin.readline
h, w = [int(x) for x in input().strip().split()]
g = np.ones([h+2, w+2])
for i in range(h):
    g[i+1] = [1] + [int(x == '#') for x in input().strip()] + [1]

ans = -1
q = deque([])
for i in range(1, h+1):
    for j in range(1, w+1):
        if g[i, j]:
            q.append((i, j))
vec = [(0, 1), (1, 0), (0, -1), (-1, 0)]

while q:
    q_ = q
    q = deque([])
    ans += 1
    while q_:
        i, j = q_.pop()
        for x, y in vec:
            ti, tj = i+x, j+y
            if g[ti, tj] == 0:
                g[ti, tj] = 1
                q.append((ti, tj))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import numpy as np
input = sys.stdin.readline
h, w = [int(x) for x in input().strip().split()]
g = np.array([[int(x == '#') for x in input().strip()] for _ in range(h)])

ans = -1
q = deque([])
for i in range(h):
    for j in range(w):
        if g[i, j]:
            q.append((i, j))
vec = [(0, 1), (1, 0), (0, -1), (-1, 0)]

while q:
    q_ = q
    q = deque([])
    ans += 1
    while q_:
        i, j = q_.pop()
        for x, y in vec:
            ti, tj = i+x, j+y
            if 0 <= ti < h and 0 <= tj < w:
                if g[ti, tj] == 0:
                    g[ti, tj] = 1
                    q.append((ti, tj))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
h, w = [int(x) for x in input().strip().split()]
g = [[x for x in input().strip()] for _ in range(h)]

ans = -1
q = deque([])
for i in range(h):
    for j in range(w):
        if g[i][j] == '#':
            q.append((i, j))
vec = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while q:
    q_ = q
    q = deque([])
    ans += 1
    while q_:
        i, j = q_.pop()
        for x, y in vec:
            ti, tj = i+x, j+y
            if 0 <= ti < h and 0 <= tj < w:
                if g[ti][tj] == '.':
                    g[ti][tj] = '#'
                    q.append((ti, tj))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
h, w = [int(x) for x in input().strip().split()]
g = [[x for x in list(input().strip())] for _ in range(h)]

ans = -1
q = set()
for i in range(h):
    for j in range(w):
        if g[i][j] == '#':
            q.add((i, j))
vec = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while q:
    q_ = q
    q = set()
    ans += 1
    while q_:
        i, j = q_.pop()
        for x, y in vec:
            ti, tj = i+x, j+y
            if 0 <= ti < h and 0 <= tj < w:
                if g[ti][tj] == '.' and (ti, tj) not in q:
                    g[ti][tj] = '#'
                    q.add((ti, tj))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
h, w = [int(x) for x in input().strip().split()]
g = [[x for x in list(input().strip())] for _ in range(h)]

ans = -1
q = deque([])
for i in range(h):
    for j in range(w):
        if g[i][j] == '#':
            q.append((i, j))
vec = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while q:
    q_ = q
    q = deque([])
    ans += 1
    while q_:
        i, j = q_.pop()
        for x, y in vec:
            ti, tj = i+x, j+y
            if 0 <= ti < h and 0 <= tj < w:
                if g[ti][tj] == '.':
                    g[ti][tj] = '#'
                    q.append((ti, tj))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
h, w = [int(x) for x in input().strip().split()]
g = [[x for x in list(input().strip())] for _ in range(h)]

ans = -1
q = []
for i in range(h):
    for j in range(w):
        if g[i][j] == '#':
            q.append((i, j))
vec = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while q:
    q_ = deque(q)
    q = deque([])
    ans += 1
    while q_:
        i, j = q_.pop()
        for x, y in vec:
            ti, tj = i+x, j+y
            if 0 <= ti < h and 0 <= tj < w:
                if g[ti][tj] == '.':
                    g[ti][tj] = '#'
                    q.append((ti, tj))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
h, w = [int(x) for x in input().strip().split()]
g = [[x for x in list(input().strip())] for _ in range(h)]

ans = -1
q = []
for i in range(h):
    for j in range(w):
        if g[i][j] == '#':
            q.append((i, j))
vec = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while q:
    q_ = q[:]
    q = []
    ans += 1
    while q_:
        i, j = q_.pop()
        for x, y in vec:
            ti, tj = i+x, j+y
            if 0 <= ti < h and 0 <= tj < w:
                if g[ti][tj] == '.':
                    g[ti][tj] = '#'
                    q.append((ti, tj))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
def main():
    h, w = map(int, input().split())
    A = [list(input()) for _ in range(h)]
    d = [[10**9] * w for _ in range(h)]
    que = deque([])
    
    for i in range(h):
        for j in range(w):
           if A[i][j] == "#":
               que.append([i, j])
               d[i][j] = 0
           else:
               d[i][j] = 10 ** 9
            
    while que:
        x, y = que.popleft()
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and d[nx][ny] == 10**9:
                d[nx][ny] = d[x][y] + 1
                que.append([nx, ny])
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, d[i][j])
    print(ans)
    
    return
    
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
def main():
    h, w = map(int, input().split())
    maze= [list(input()) for i in range(h)]
    route = [[-1] * w for i in range(h)]
    que = deque([])
    
    for i in range(h):
        for j in range(w):
           if maze[i][j] == "#":
               que.append([i, j])
               route[i][j] = 0
            
    ans = 0
    while que:
        x, y = que.popleft()
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and route[nx][ny] == -1:
                route[nx][ny] = route[x][y] + 1
                que.append([nx, ny])
                ans = max(ans , route[nx][ny])

    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int, input().split())
maze = [input() for i in range(h)]
route = [[0] * w for i in range(h)]
 
class MyStack:
    def __init__(self):
        self.stack = []
    def push(self, item_1, item_2):
        self.stack.append([item_1,item_2])
    def pop(self):
        result = self.stack.pop(0)
        return result[0],result[1]

stack = MyStack()
black_list = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == '#':
            stack.push(i+1,j+1)
while stack.stack:
    y,x = stack.pop()
    route_num = route[y-1][x-1] + 1
    if y != h:
        if maze[y][x-1] == '.' and route[y][x-1] == 0:
            stack.push(y+1,x)
            route[y][x-1] = route_num
            
    if y != 1:
        if maze[y-2][x-1] == '.' and route[y-2][x-1] == 0:
            stack.push(y-1,x)
            route[y-2][x-1] = route_num
            
    if x != w:
        if maze[y-1][x] == '.' and route[y-1][x] == 0:
            stack.push(y,x+1)
            route[y-1][x] = route_num
 
    if x != 1:
        if maze[y-1][x-2] == '.' and route[y-1][x-2] == 0:
            stack.push(y,x-1)
            route[y-1][x-2] = route_num
            
print(route_num - 1)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int, input().split())
maze = [input() for i in range(h)]
route = [[0] * w for i in range(h)]
 
class MyStack:
    def __init__(self):
        self.stack = []
    def push(self, item_1, item_2):
        self.stack.append([item_1,item_2])
    def pop(self):
        result = self.stack.pop(0)
        return result[0],result[1]

 
ans = 0
stack = MyStack()
black_list = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == '#':
            stack.push(i+1,j+1)
while stack.stack:
    y,x = stack.pop()
    route_num = route[y-1][x-1] + 1
    if y != h:
        if maze[y][x-1] == '.' and route[y][x-1] == 0:
            stack.push(y+1,x)
            route[y][x-1] = route_num
            ans = max(ans,route[y][x-1])
            
    if y != 1:
        if maze[y-2][x-1] == '.' and route[y-2][x-1] == 0:
            stack.push(y-1,x)
            route[y-2][x-1] = route_num
            ans = max(ans,route[y-2][x-1])
            
    if x != w:
        if maze[y-1][x] == '.' and route[y-1][x] == 0:
            stack.push(y,x+1)
            route[y-1][x] = route_num
            ans = max(ans,route[y-1][x])

    if x != 1:
        if maze[y-1][x-2] == '.' and route[y-1][x-2] == 0:
            stack.push(y,x-1)
            route[y-1][x-2] = route_num
            ans = max(ans,route[y-1][x-2])
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int, input().split())
maze = [input() for i in range(h)]
route = [[0] * w for i in range(h)]
 
black_list = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == '#':
            black_list.append([i+1,j+1])
 
class MyStack:
    def __init__(self):
        self.stack = []
    def push(self, item_1, item_2):
        self.stack.append([item_1,item_2])
    def pop(self):
        result = self.stack.pop(0)
        return result[0],result[1]

 
ans = 0
stack = MyStack()
for black in black_list:
        stack.push(black[0],black[1])
while stack.stack:
    y,x = stack.pop()
    route_num = route[y-1][x-1] + 1
    if y != h:
        if maze[y][x-1] == '.' and route[y][x-1] == 0:
            stack.push(y+1,x)
            route[y][x-1] = route_num
            ans = max(ans,route[y][x-1])
            
    if y != 1:
        if maze[y-2][x-1] == '.' and route[y-2][x-1] == 0:
            stack.push(y-1,x)
            route[y-2][x-1] = route_num
            ans = max(ans,route[y-2][x-1])
            
    if x != w:
        if maze[y-1][x] == '.' and route[y-1][x] == 0:
            stack.push(y,x+1)
            route[y-1][x] = route_num
            ans = max(ans,route[y-1][x])

    if x != 1:
        if maze[y-1][x-2] == '.' and route[y-1][x-2] == 0:
            stack.push(y,x-1)
            route[y-1][x-2] = route_num
            ans = max(ans,route[y-1][x-2])
            

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int, input().split())
maze = [input() for i in range(h)]
route_total = [[h*w] * w for i in range(h)]
 
black_list = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == '#':
            black_list.append([i+1,j+1])
 
 
class MyStack:
    def __init__(self):
        self.stack = []
    def push(self, item_1, item_2):
        self.stack.append([item_1,item_2])
    def pop(self):
        result = self.stack.pop(0)
        return result[0],result[1]
 
ans = 0
stack = MyStack()
for i,black in enumerate(black_list):
    route = [[0] * w for i in range(h)]
    stack.push(black[0],black[1])
    route[black[0]-1][black[1]-1] = 0
    while len(stack.stack) > 0:
        y,x = stack.pop()
        route_num = route[y-1][x-1] + 1
        if y != h:
            if maze[y][x-1] == '.' and route[y][x-1] == 0:
                stack.push(y+1,x)
                route[y][x-1] = route_num 
                route_total[y][x-1] = min(route_num,route_total[y][x-1])
                if i == len(black_list) - 1:
                    ans = max(ans, route_total[y][x-1]) 
        if y != 1:
            if maze[y-2][x-1] == '.' and route[y-2][x-1] == 0:
                stack.push(y-1,x)
                route[y-2][x-1] = route_num
                route_total[y-2][x-1] = min(route_num,route_total[y-2][x-1])
                if i == len(black_list) - 1:
                    ans = max(ans, route_total[y-2][x-1]) 
        if x != w:
            if maze[y-1][x] == '.' and route[y-1][x] == 0:
                stack.push(y,x+1)
                route[y-1][x] = route_num
                route_total[y-1][x] = min(route_num,route_total[y-1][x])
                if i == len(black_list) - 1:
                    ans = max(ans, route_total[y-1][x]) 
        if x != 1:
            if maze[y-1][x-2] == '.' and route[y-1][x-2] == 0:
                stack.push(y,x-1)
                route[y-1][x-2] = route_num
                route_total[y-1][x-2] = min(route_num,route_total[y-1][x-2])
                if i == len(black_list) - 1:
                    ans = max(ans, route_total[y-1][x-2]) 

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = [list(map(str, input())) for _ in range(H)]
q = []
for i in range(H):
	for j in range(W):
		if A[i][j] == '#':
			q.append([i,j,0])

while q:
	cx,cy,cd = q.pop(0)
	for nx,ny in [[cx+1,cy],[cx-1,cy],[cx,cy+1],[cx,cy-1]]:
		if 0 <= nx < H and 0 <= ny < W:
			if A[nx][ny] == '.':
				q.append([nx,ny,cd+1])
				A[nx][ny] = '#'

print(cd)

Submission status: Time Limit Exceeded

Solution code:
height, width = map(int, input().split(" "))
target = []
queue = []
WHITE = "."
BLACK = "#"
for h in range(height):
    temp = [n for n in input()]
    for w in range(width):
        if temp[w] == BLACK:
            queue.append([w, h])
    target.append(temp)
all_move = [[0, 1], [0, -1], [1, 0], [-1, 0]]

answer = 0
while queue:
    next_queue = []
    for q in queue:
        here_x, here_y = q
        for x, y in all_move:
            next_x, next_y = here_x + x, here_y + y
            if 0 <= next_x < width and 0 <= next_y < height:
                if target[next_y][next_x] == WHITE:
                    next_queue.append([next_x, next_y])
                    target[next_y][next_x] = BLACK
    if not next_queue:
        print(answer)
        break
    queue = next_queue
    answer += 1

Submission status: Time Limit Exceeded

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

q = []
for i in range(H):
	for j in range(W):
		if A[i][j] == '#':
			q.append([i,j,0])

while q:
	cx,cy,cd = q.pop(0)
	for nx,ny in [[cx+1,cy],[cx-1,cy],[cx,cy+1],[cx,cy-1]]:
		if 0 <= nx < H and 0 <= ny < W:
			if A[nx][ny] == '.':
				q.append([nx,ny,cd+1])
				A[nx][ny] = '#'

print(cd)

Submission status: Time Limit Exceeded

Solution code:
import collections

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

visited = [[-float("inf")]*w for _ in range(h)]
q = collections.deque([])

for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            q.appendleft([i, j])
            visited[i][j] = 0

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

while len(q):
    cy, cx = q.pop()
    for i in range(4):
        x = cx + dx[i]
        y = cy + dy[i]

        if 0 <= x < w and 0 <= y < h and visited[y][x] == -float("inf"):
            visited[y][x] = visited[cy][cx] + 1
            q.appendleft([y, x])

ans = -1
for i in range(h):
    for j in range(w):
        ans = max(ans, visited[i][j])
print(ans)