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
h, w = map(int, input().split())
n = h*w


def to_v(i, j):
    return i*w+j


init_vs = []
for i in range(h):
    for j, x in enumerate(input()):
        if x == '#':
            init_vs.append(to_v(i, j))


INF = 10**18
dist = [INF]*n
for v in init_vs:
    dist[v] = 0


def generate_v2(v):
    i, j = divmod(v, w)
    if 0 < i:
        yield v-w
    if i < h-1:
        yield v+w
    if 0 < j:
        yield v-1
    if j < w-1:
        yield v+1


def bfs(init_vs):
    next_v = deque([*init_vs])
    while next_v:
        v = next_v.popleft()
        for v2 in generate_v2(v):
            if dist[v2] <= dist[v]+1:
                continue
            dist[v2] = dist[v]+1
            next_v.append(v2)


bfs(init_vs)

print(max(dist))

Submission status: Time Limit Exceeded

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


def to_v(i, j):
    return i*w+j


init_vs = []
for i in range(h):
    for j, x in enumerate(input()):
        if x == '#':
            init_vs.append(to_v(i, j))


INF = 10**18
dist = [INF]*n
for v in init_vs:
    dist[v] = 0


def generate_v2(v):
    i, j = divmod(v, w)
    if 0 < i:
        yield v-w
    if i < h-1:
        yield v+w
    if 0 < j:
        yield v-1
    if j < w-1:
        yield v+1


def bfs(init_v):
    next_v = deque([init_v])
    while next_v:
        v = next_v.popleft()
        for v2 in generate_v2(v):
            if dist[v2] <= dist[v]+1:
                continue
            dist[v2] = dist[v]+1
            next_v.append(v2)


for v in init_vs:
    bfs(v)

print(max(dist))

Submission status: Time Limit Exceeded

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

def bfs():
    H, W = map(int, input().split())
    ls = deque([])
    D = [[0] * (W+2)]
    D += ([[0] + [float("inf")]*W + [0] for i in range(H)])
    D.append([0]*(W+2))
    for i in range(H):
        line = input()
        for j in range(W):
            if line[j] == "#":
                ls.append([i+1, j+1, 0])
                D[i+1][j+1] = 0

    while len(ls) > 0:
        h, w, depth = ls.popleft()
        if depth + 1 < D[h+1][w]:
            ls.append([h+1, w, depth+1])
            D[h+1][w] = depth + 1
        if depth + 1 < D[h-1][w]:
            ls.append([h-1, w, depth+1])
            D[h-1][w] = depth + 1
        if depth + 1 < D[h][w+1]:
            ls.append([h, w+1, depth+1])
            D[h][w+1] = depth + 1
        if depth + 1 < D[h][w-1]:
            ls.append([h, w-1, depth+1])
            D[h][w-1] = depth + 1

    return depth
    
print(bfs())

Submission status: Time Limit Exceeded

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

def bfs():
    H, W = map(int, input().split())
    ls = deque([])
    D = [[0] * (W+2)]
    D += ([[0] + [float("inf")]*W + [0] for i in range(H)])
    D.append([0]*(W+2))
    for i in range(H):
        line = input()
        for j in range(W):
            if line[j] == "#":
                ls.append([i+1, j+1, 0])
                D[i+1][j+1] = 0

    while len(ls) > 0:
        h, w, depth = ls.popleft()
        if depth + 1 < D[h+1][w]:
            ls.append([h+1, w, depth+1])
            D[h+1][w] = depth + 1
        if depth + 1 < D[h-1][w]:
            ls.append([h-1, w, depth+1])
            D[h-1][w] = depth + 1
        if depth + 1 < D[h][w+1]:
            ls.append([h, w+1, depth+1])
            D[h][w+1] = depth + 1
        if depth + 1 < D[h][w-1]:
            ls.append([h, w-1, depth+1])
            D[h][w-1] = depth + 1

    ans = 0
    for h in range(1, H+1):
        ans = max(ans, max(D[h]))
        
    return ans
    
print(bfs())

Submission status: Time Limit Exceeded

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

def bfs():
    H, W = map(int, input().split())
    ls = deque([])
    D = [[0] * (W+2)]
    D += ([[0] + [float("inf")]*W + [0] for i in range(H)])
    D.append([0]*(W+2))
    G = [["#"]*(W+2)]
    G += [["#"]+[i for i in input().strip()]+["#"] for i in range(H)]
    G.append(["#"]*(W+2))
    for i in range(1, H+1):
        for j in range(1, W+1):
            if G[i][j] == "#":
                ls.append([i, j, 0])
                D[i][j] = 0

    while len(ls) > 0:
        h, w, depth = ls.popleft()
        if depth + 1 < D[h+1][w]:
            ls.append([h+1, w, depth+1])
            D[h+1][w] = depth + 1
        if depth + 1 < D[h-1][w]:
            ls.append([h-1, w, depth+1])
            D[h-1][w] = depth + 1
        if depth + 1 < D[h][w+1]:
            ls.append([h, w+1, depth+1])
            D[h][w+1] = depth + 1
        if depth + 1 < D[h][w-1]:
            ls.append([h, w-1, depth+1])
            D[h][w-1] = depth + 1

    ans = 0
    for h in range(1, H+1):
        ans = max(ans, max(D[h]))
        
    return ans
    
print(bfs())

Submission status: Time Limit Exceeded

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

def bfs():
    H, W = map(int, input().split())
    ls = deque([])
    D = [[0] * (W+2)]
    D += ([[0] + [float("inf")]*W + [0] for i in range(H)])
    D.append([0]*(W+2))
    G = [["#"]*(W+2)]
    G += [["#"]+[i for i in input().strip()]+["#"] for i in range(H)]
    G.append(["#"]*(W+2))
    for i in range(1, H+1):
        for j in range(1, W+1):
            if G[i][j] == "#":
                ls.append([i, j, 0])
                D[i][j] = 0

    while len(ls) > 0:
        h, w, depth = ls.popleft()
        if depth + 1 < D[h+1][w] and G[h+1][w] != "#":
            ls.append([h+1, w, depth+1])
            D[h+1][w] = depth + 1
        if depth + 1 < D[h-1][w] and G[h-1][w] != "#":
            ls.append([h-1, w, depth+1])
            D[h-1][w] = depth + 1
        if depth + 1 < D[h][w+1] and G[h][w+1] != "#":
            ls.append([h, w+1, depth+1])
            D[h][w+1] = depth + 1
        if depth + 1 < D[h][w-1] and G[h][w-1] != "#":
            ls.append([h, w-1, depth+1])
            D[h][w-1] = depth + 1

    ans = 0
    for h in range(1, H+1):
        ans = max(ans, max(D[h]))
        
    return ans
    
print(bfs())

Submission status: Time Limit Exceeded

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

def bfs():
    H, W = map(int, input().split())
    ls = deque([])
    D = [[0] * (W+2)]
    D += ([[0] + [float("inf")]*W + [0] for i in range(H)])
    D.append([0]*(W+2))
    G = [["#"]*(W+2)]
    for i in range(H):
        line = [i for i in input().strip()]
        for j in range(W):
            if line[j] == "#":
                ls.append([i+1, j+1, 0])
                D[i+1][j+1] = 0
        G.append(["#"]+line+["#"])
    G.append([["#"]*(W+2)])

    while len(ls) > 0:
        h, w, depth = ls.popleft()
        if depth + 1 < D[h+1][w] and G[h+1][w] != "#":
            ls.append([h+1, w, depth+1])
            D[h+1][w] = depth + 1
        if depth + 1 < D[h-1][w] and G[h-1][w] != "#":
            ls.append([h-1, w, depth+1])
            D[h-1][w] = depth + 1
        if depth + 1 < D[h][w+1] and G[h][w+1] != "#":
            ls.append([h, w+1, depth+1])
            D[h][w+1] = depth + 1
        if depth + 1 < D[h][w-1] and G[h][w-1] != "#":
            ls.append([h, w-1, depth+1])
            D[h][w-1] = depth + 1

    ans = 0
    for h in range(H+2):
        ans = max(ans, max(D[h]))
        
    return ans
    
print(bfs())

Submission status: Time Limit Exceeded

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

def bfs():
    H, W = map(int, input().split())
    ls = deque([])
    D = [[0] * (W+2)]
    D += ([[0] + [float("inf")]*W + [0] for i in range(H)])
    D.append([0]*(W+2))
    G = [["#"]*(W+2)]
    for i in range(H):
        line = [i for i in input().strip()]
        for j in range(W):
            if line[j] == "#":
                ls.append([i+1, j+1, 0])
                D[i+1][j+1] = 0
        G.append(["#"]+line+["#"])
    G.append([["#"]*(W+2)])

    direction = [[1,0], [-1,0], [0,1], [0,-1]]
    while len(ls) > 0:
        h, w, depth = ls.popleft()
        for dh, dw in direction:
            if depth + 1 < D[h+dh][w+dw] and G[h+dh][w+dw] != "#":
                ls.append([h+dh, w+dw, depth+1])
                D[h+dh][w+dw] = depth + 1

    ans = 0
    for h in range(H):
        ans = max(ans, max(D[h]))
        
    return ans
    
print(bfs())

Submission status: Time Limit Exceeded

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

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

def bfs(h, w):
    ls = deque([[h, w, 0]])
    direction = [[1,0], [-1,0], [0,1], [0,-1]]
    while len(ls) > 0:
        h, w, depth = ls.popleft()
        
        for dh, dw in direction:
            if h + dh < 0 or H-1 < h + dh: continue
            if w + dw < 0 or W-1 < w + dw: continue
            if depth + 1 < D[h+dh][w+dw] and G[h+dh][w+dw] != "#":
                ls.append([h+dh, w+dw, depth+1])
                D[h+dh][w+dw] = depth + 1

G = [[i for i in input()] for j in range(H)]
D = [[float("inf")] * W for i in range(H)]
for h in range(H):
    for w in range(W):
        if G[h][w] == "#":
            bfs(h, w)
            
ans = 0
for h in range(H):
    for w in range(W):
        if D[h][w] == float("inf"):
            continue
        ans = max(ans, D[h][w])
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

def bfs(h, w):
    ls = deque([[h, w, 0]])
    direction = [[1,0], [-1,0], [0,1], [0,-1]]
    while len(ls) > 0:
        h, w, depth = ls.popleft()
        
        for dh, dw in direction:
            if h + dh < 0 or H-1 < h + dh: continue
            if w + dw < 0 or W-1 < w + dw: continue
            if depth + 1 < D[h+dh][w+dw] and G[h+dh][w+dw] != "#":
                ls.append([h+dh, w+dw, depth+1])
                D[h+dh][w+dw] = depth + 1

G = [[i for i in input()] for j in range(H)]
D = [[float("inf")] * W for i in range(H)]
for h in range(H):
    for w in range(W):
        if G[h][w] == "#":
            bfs(h, w)
            
ans = 0
for h in range(H):
    for w in range(W):
        if D[h][w] == float("inf"):
            continue
        ans = max(ans, D[h][w])
        
print(ans)

Submission status: Time Limit Exceeded

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

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

def bfs(black_cells,dist):

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

flag = [[True] * w for _ in range(h)]

q = deque()

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

ans = 0
while q:
    (i, j, n) = q.pop()
    ans = n
    for dx, dy in zip([1,0, -1, 0], [0, 1, 0, -1]):
        ni = i + dx
        nj = j + dy
        if (0 <= ni < h and 0 <= nj < w and flag[ni][nj]):
            flag[ni][nj] = False
            q.appendleft((ni, nj, n + 1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from numba import jit


@jit
def BFS():
    point=0
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[0 for _ in range(w)] for _ in range(h)]

    queue=deque([])
    for i in range(h):
        for j in range(w):
            if A[i][j]=="#":
                color[i][j]="gray"
                queue.append([i,j])
                D[i][j]=0

    while len(queue)>0:
        x,y=queue.popleft()
        for a,b in [[1,0],[-1,0],[0,1],[0,-1]]:
            X,Y=x+a,y+b
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]=="white":
                    color[X][Y]="gray"
                    D[X][Y]=D[x][y]+1
                    point=max(point,D[X][Y])
                    queue.append([X,Y])
        color[x][y]="black"

    return point


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

Submission status: Time Limit Exceeded

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


def BFS():
    point=0
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[0 for _ in range(w)] for _ in range(h)]

    queue=deque([])
    for i in range(h):
        for j in range(w):
            if A[i][j]=="#":
                color[i][j]="gray"
                queue.append([i,j])
                D[i][j]=0

    while len(queue)>0:
        x,y=queue.popleft()
        for a,b in [[1,0],[-1,0],[0,1],[0,-1]]:
            X,Y=x+a,y+b
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]=="white":
                    color[X][Y]="gray"
                    D[X][Y]=D[x][y]+1
                    point=max(point,D[X][Y])
                    queue.append([X,Y])
        color[x][y]="black"

    return point


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def BFS():
    point=0
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[0 for _ in range(w)] for _ in range(h)]

    queue=deque([])
    for i in range(h):
        for j in range(w):
            if A[i][j]=="#":
                color[i][j]="gray"
                queue.append([i,j])
                D[i][j]=0

    while len(queue)>0:
        x,y=queue.popleft()
        for a,b in [[1,0],[-1,0],[0,1],[0,-1]]:
            X,Y=x+a,y+b
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]!="black":
                    color[X][Y]="gray"
                    D[X][Y]=D[x][y]+1
                    point=max(point,D[X][Y])
                    queue.append([X,Y])
        color[x][y]="black"

    return point


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def BFS():
    point=0
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[0 for _ in range(w)] for _ in range(h)]

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

    while len(queue)>0:
        x,y=queue.popleft()
        for a,b in [[1,0],[-1,0],[0,1],[0,-1]]:
            X,Y=x+a,y+b
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]!="black":
                    color[X][Y]="gray"
                    D[X][Y]=D[x][y]+1
                    point=max(point,D[X][Y])
                    queue.append([X,Y])
        color[x][y]="black"

    return point


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

Submission status: Time Limit Exceeded

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


def BFS():
    point=0
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[0 for _ in range(w)] for _ in range(h)]

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

    while len(queue)>0:
        x,y=queue.popleft()
        for a,b in [[1,0],[-1,0],[0,1],[0,-1]]:
            X,Y=x+a,y+b
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]!="black":
                    color[X][Y]="gray"
                    D[X][Y]=D[x][y]+1
                    point=max(point,D[X][Y])
                    queue.append([X,Y])
        color[x][y]="black"

    return point


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
inf=10**9


def BFS():
    point=0
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[inf for _ in range(w)] for _ in range(h)]

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

    while len(queue)>0:
        x,y=queue.popleft()
        for a,b in [[1,0],[-1,0],[0,1],[0,-1]]:
            X,Y=x+a,y+b
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]!="black" and D[X][Y]>D[x][y]+1:
                    color[X][Y]="gray"
                    D[X][Y]=D[x][y]+1
                    point=max(point,D[X][Y])
                    queue.append([X,Y])
        color[x][y]="black"

    return point


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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

ans = 0
for i in range(h):
    for j in range(w):
        if m[i][j] == ".":
            tmp = 1000000000
            for (b_h, b_w) in black_loc:
                tmp = min(tmp, abs(i - b_h) + abs(j - b_w))
            ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

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

H ,W = map(int, input().split())#↓H行数 →W列数
#List = [list(str(input())) for i in range(H)]
#H=3
#W=3
#List=[['.', '.', '.'], ['.', '#', '.'], ['.', '.', '.']]
cheak=[['0' for i in range(W)] for j in range(H)]

q = deque([])
List=[]
for h in range(H):
    qwe=list(str(input()))
    List.append(qwe)
    for w in range(W):
        if qwe[w]=='#':
            cheak[h][w]='1'
            q.append([h,w])
#print(List)
#print(cheak)
move=[[1,0],[-1,0],[0,1],[0,-1]]
num=-1
#print(q)
while q:
    for rt in range(len(q)):
        i=q.popleft()
        for u in move:
            if 0<=i[0]+u[0]<=H-1 and 0<=i[1]+u[1]<=W-1 and cheak[i[0]+u[0]][i[1]+u[1]]=='0':
                q.append([i[0]+u[0],i[1]+u[1]])
                cheak[i[0]+u[0]][i[1]+u[1]]='1'
    #print(cheak)
    num+=1
print(num)

Submission status: Time Limit Exceeded

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

H ,W = map(int, input().split())#↓H行数 →W列数
#List = [list(str(input())) for i in range(H)]
#H=3
#W=3
#List=[['.', '.', '.'], ['.', '#', '.'], ['.', '.', '.']]
cheak=[['0' for i in range(W)] for j in range(H)]

q = deque([])
List=[]
for h in range(H):
    qwe=list(str(input()))
    List.append(qwe)
    for w in range(W):
        if qwe[w]=='#':
            cheak[h][w]='1'
            q.append([h,w])
#print(List)
#print(cheak)
move=[[1,0],[-1,0],[0,1],[0,-1]]
num=-1
#print(q)
while q:
    for rt in range(len(q)):
        i=q.popleft()
        for u in move:
            if 0<=i[0]+u[0]<=H-1 and 0<=i[1]+u[1]<=W-1 and cheak[i[0]+u[0]][i[1]+u[1]]=='0':
                q.append([i[0]+u[0],i[1]+u[1]])
                cheak[i[0]+u[0]][i[1]+u[1]]='1'
    #print(cheak)
    num+=1
print(num)

Submission status: Time Limit Exceeded

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

H ,W = map(int, input().split())#↓H行数 →W列数
List = [list(str(input())) for i in range(H)]
#H=3
#W=3
#List=[['.', '.', '.'], ['.', '#', '.'], ['.', '.', '.']]
cheak=[['0' for i in range(W)] for j in range(H)]

q = deque([])

for h in range(H):
    for w in range(W):
        if List[h][w]=='#':
            cheak[h][w]='1'
            q.append([h,w])
#print(List)
#print(cheak)
move=[[1,0],[-1,0],[0,1],[0,-1]]
num=-1
#print(q)
while q:
    for rt in range(len(q)):
        i=q.popleft()
        for u in move:
            if 0<=i[0]+u[0]<=H-1 and 0<=i[1]+u[1]<=W-1 and cheak[i[0]+u[0]][i[1]+u[1]]=='0':
                q.append([i[0]+u[0],i[1]+u[1]])
                cheak[i[0]+u[0]][i[1]+u[1]]='1'
    #print(cheak)
    num+=1
print(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H ,W = map(int, input().split())#↓H行数 →W列数
List = [list(str(input())) for i in range(H)]
#H=3
#W=3
#List=[['.', '.', '.'], ['.', '#', '.'], ['.', '.', '.']]
cheak=[['0' for i in range(W)] for j in range(H)]

q = deque([])

for h in range(H):
    for w in range(W):
        if List[h][w]=='#':
            cheak[h][w]='1'
            q.append([h,w])
#print(List)
#print(cheak)
move=[[1,0],[-1,0],[0,1],[0,-1]]
num=-1
#print(q)
while q:
    for rt in range(len(q)):
        i=q.popleft()
        for u in move:
            if 0<=i[0]+u[0]<=H-1 and 0<=i[1]+u[1]<=W-1 and cheak[i[0]+u[0]][i[1]+u[1]]=='0':
                q.append([i[0]+u[0],i[1]+u[1]])
                cheak[i[0]+u[0]][i[1]+u[1]]='1'
    #print(cheak)
    num+=1
print(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H ,W = map(int, input().split())#↓H行数 →W列数
List = [list(input()) for i in range(H)]
#H=3
#W=3
#List=[['.', '.', '.'], ['.', '#', '.'], ['.', '.', '.']]
cheak=[['0' for i in range(W)] for j in range(H)]

q = deque([])

for h in range(H):
    for w in range(W):
        if List[h][w]=='#':
            cheak[h][w]='1'
            q.append([h,w])
#print(List)
#print(cheak)
move=[[1,0],[-1,0],[0,1],[0,-1]]
num=-1
#print(q)
while q:
    list=[]
    for i in range(len(q)):
        a=q.popleft()
        #print(a)
        list.append(a)
    #print(list)
    for i in list:
        for u in move:
            if 0<=i[0]+u[0]<=H-1 and 0<=i[1]+u[1]<=W-1 and cheak[i[0]+u[0]][i[1]+u[1]]=='0':
                q.append([i[0]+u[0],i[1]+u[1]])
                cheak[i[0]+u[0]][i[1]+u[1]]='1'
    #print(cheak)
    num+=1
print(num)

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque

h, w = map(int, input().split())
grid = [list(map(lambda x: x == "#", input().rstrip())) 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])

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

ans = 0
while q:
    curr = q.popleft()
    ans = max(ans, curr[2])
    for m in moves:
        nx, ny = curr[0] + m[0], curr[1] + m[1]
        if nx < 0 or ny < 0 or nx > h - 1 or ny > w - 1 or grid[nx][ny]:
            continue
        else:
            q.append([nx, ny, curr[2] + 1])
            grid[nx][ny] = True

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque

h, w = map(int, input().split())
grid = [list(map(lambda x: x == "#", input().rstrip())) for _ in range(h)]

nq = deque([])
for i in range(h):
    for j in range(w):
        if grid[i][j]:
            nq.append([i, j])

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

cnt = 0
while sum(sum(grid, [])) < h * w:
    cnt += 1
    q = copy.deepcopy(nq)
    while q:
        curr = q.popleft()
        for m in moves:
            nx, ny = curr[0] + m[0], curr[1] + m[1]
            if nx < 0 or ny < 0 or nx > h - 1 or ny > w - 1 or grid[nx][ny]:
                continue
            else:
                nq.append([nx, ny])
                grid[nx][ny] = True

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque

h, w = map(int, input().split())
grid = [list(map(lambda x: x == "#", input().rstrip())) for _ in range(h)]

nq = deque([])
for i in range(h):
    for j in range(w):
        if grid[i][j]:
            nq.append([i, j])

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

cnt = 0
while sum(sum(grid, [])) < h * w:
    cnt += 1
    q = copy.deepcopy(nq)
    while q:
        curr = q.popleft()
        for m in moves:
            nx, ny = curr[0] + m[0], curr[1] + m[1]
            if nx < 0 or ny < 0 or nx > h - 1 or ny > w - 1 or grid[nx][ny]:
                continue
            else:
                if not grid[nx][ny]:
                    nq.append([nx, ny])
                    grid[nx][ny] = True

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque

h, w = map(int, input().split())
grid = [list(map(lambda x: x == "#", input().rstrip())) for _ in range(h)]

nq = deque([])
for i in range(h):
    for j in range(w):
        if grid[i][j]:
            nq.append([i, j])

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

cnt = 0
while sum(sum(grid, [])) < h * w:
    cnt += 1
    q = copy.deepcopy(nq)
    while q:
        curr = q.popleft()
        for m in moves:
            nx, ny = curr[0] + m[0], curr[1] + m[1]
            if nx < 0 or ny < 0 or nx > h - 1 or ny > w - 1:
                continue
            else:
                if not grid[nx][ny]:
                    nq.append([nx, ny])
                    grid[nx][ny] = True

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys


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

queues = []


def f(x, i):
    for j in range(W):
        if x[j] == '#':
            queues.append(deque([[j, i, 0]]))
    return list(x)


M = [f(input(), i) for i in range(H)]


depth_now = 0
depth = 0
while True:
    for q in queues:
        while len(q) != 0 and q[0][2] == depth_now:
            p = q.popleft()
            x = p[0]
            y = p[1]
            depth = p[2]
            if x - 1 >= 0 and M[y][x-1] == '.':
                q.append([x-1, y, depth+1])
                M[y][x-1] = '#'
            if x + 1 < W and M[y][x+1] == '.':
                q.append([x+1, y, depth+1])
                M[y][x+1] = '#'
            if y - 1 >= 0 and M[y-1][x] == '.':
                q.append([x, y-1, depth+1])
                M[y-1][x] = '#'
            if y + 1 < H and M[y+1][x] == '.':
                q.append([x, y+1, depth+1])
                M[y+1][x] = '#'
    queues = [q for q in queues if len(q) != 0]
    if len(queues) == 0:
        print(depth_now)
        break
    depth_now += 1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys


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

M = []
queues = []
for i in range(H):
    A = input()
    M.append(list(A))
    for j in range(W):
        if A[j] == '#':
            queues.append(deque([[j, i, 0]]))

depth_now = 0
depth = 0
while True:
    for q in queues:
        while len(q) != 0 and q[0][2] == depth_now:
            p = q.popleft()
            x = p[0]
            y = p[1]
            depth = p[2]
            if x - 1 >= 0 and M[y][x-1] == '.':
                q.append([x-1, y, depth+1])
                M[y][x-1] = '#'
            if x + 1 < W and M[y][x+1] == '.':
                q.append([x+1, y, depth+1])
                M[y][x+1] = '#'
            if y - 1 >= 0 and M[y-1][x] == '.':
                q.append([x, y-1, depth+1])
                M[y-1][x] = '#'
            if y + 1 < H and M[y+1][x] == '.':
                q.append([x, y+1, depth+1])
                M[y+1][x] = '#'
    queues = [q for q in queues if len(q) != 0]
    if len(queues) == 0:
        print(depth_now)
        break
    depth_now += 1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys


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

M = []
queues = []
for i in range(H):
    A = input()
    M.append(list(A))
    for j in range(W):
        if A[j] == '#':
            queues.append(deque([[j, i, 0]]))

depth_now = 0
depth = 0
while True:
    for q in queues:
        while len(q) != 0 and q[0][2] == depth_now:
            p = q.popleft()
            x = p[0]
            y = p[1]
            depth = p[2]
            cands = []
            if x - 1 >= 0:
                cands.append([x-1, y])
            if x + 1 < W:
                cands.append([x+1, y])
            if y - 1 >= 0:
                cands.append([x, y-1])
            if y + 1 < H:
                cands.append([x, y+1])
            for cx, cy in cands:
                if M[cy][cx] == '.':
                    q.append([cx, cy, depth+1])
                    M[cy][cx] = '#'
    queues = [q for q in queues if len(q) != 0]
    if len(queues) == 0:
        print(depth_now)
        break
    depth_now += 1

Submission status: Time Limit Exceeded

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

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


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())

area = [input() for _ in range(H)]

distance = [ [float('inf') for _ in range(W)] for _ in range(H)]
to_search = deque()

for i in range(H):
    for j in range(W):
        if area[i][j] == "#":
            to_search.appendleft((i, j, 0))
            distance[i][j] = 0

didj = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans = 0

while len(to_search) > 0:
    nowi, nowj, nowd = to_search.pop()
    for di, dj in didj:
        nexti = nowi + di
        nextj = nowj + dj
        if 0 <= nexti < H and 0 <= nextj < W:
            if distance[nexti][nextj] > nowd + 1:
                to_search.appendleft((nexti, nextj, nowd + 1))
                distance[nexti][nextj] = nowd + 1
                ans = max(ans, nowd + 1)

print(ans)