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 main():
    H,W = map(int, input().split())

    A = [["" for _ in range(W)] for _ in range(H)]

    stack = deque()
    for i in range(H):
        tmp = list(input())
        for j in range(W):
            A[i][j] = tmp[j]
            if tmp[j] == "#":
                stack.append((i,j))

    ans = 0
    flag = False
    if stack:
        flag = True
    while flag:
        ans += 1
        #print(ans, stack)
        flag = False
        new_stack = deque()
        for a,b in stack:
            #a,b = stack.pop() # 取り出す
            # A[a][b]の隣接マスについて調べる
            if a != 0: # 上
                if A[a-1][b] == ".": # 白の場合
                    A[a-1][b] = "#"
                    new_stack.append((a-1,b))
            if a != H-1: # 下
                if A[a+1][b] == ".": # 白の場合
                    A[a+1][b] = "#"
                    new_stack.append((a+1,b))
            if b != 0: # 左
                if A[a][b-1] == ".": # 白の場合
                    A[a][b-1] = "#"
                    new_stack.append((a,b-1))
            if b != W-1: # 右
                if A[a][b+1] == ".": # 白の場合
                    A[a][b+1] = "#"
                    new_stack.append((a,b+1))
        stack = new_stack
        if stack:
            flag = True
        else:
            ans -= 1 

    print(ans)
            


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

A = [["" for _ in range(W)] for _ in range(H)]

stack = deque()
for i in range(H):
    tmp = list(input())
    for j in range(W):
        A[i][j] = tmp[j]
        if tmp[j] == "#":
            stack.append((i,j))

ans = 0
flag = False
if stack:
    flag = True
while flag:
    ans += 1
    #print(ans, stack)
    flag = False
    new_stack = deque()
    for a,b in stack:
        #a,b = stack.pop() # 取り出す
        # A[a][b]の隣接マスについて調べる
        if a != 0: # 上
            if A[a-1][b] == ".": # 白の場合
                A[a-1][b] = "#"
                new_stack.append((a-1,b))
        if a != H-1: # 下
            if A[a+1][b] == ".": # 白の場合
                A[a+1][b] = "#"
                new_stack.append((a+1,b))
        if b != 0: # 左
            if A[a][b-1] == ".": # 白の場合
                A[a][b-1] = "#"
                new_stack.append((a,b-1))
        if b != W-1: # 右
            if A[a][b+1] == ".": # 白の場合
                A[a][b+1] = "#"
                new_stack.append((a,b+1))
    stack = new_stack
    if stack:
        flag = True
    else:
        ans -= 1 

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

A = [["" for _ in range(W)] for _ in range(H)]

stack = deque()
for i in range(H):
    tmp = list(input())
    for j in range(W):
        A[i][j] = tmp[j]
        if tmp[j] == "#":
            stack.append((i,j))

ans = 0
flag = False
if stack:
    flag = True
while flag:
    ans += 1
    #print(ans, stack)
    flag = False
    new_stack = deque()
    while stack:
        a,b = stack.pop() # 取り出す
        # A[a][b]の隣接マスについて調べる
        if a != 0: # 上
            if A[a-1][b] == ".": # 白の場合
                A[a-1][b] = "#"
                new_stack.append((a-1,b))
        if a != H-1: # 下
            if A[a+1][b] == ".": # 白の場合
                A[a+1][b] = "#"
                new_stack.append((a+1,b))
        if b != 0: # 左
            if A[a][b-1] == ".": # 白の場合
                A[a][b-1] = "#"
                new_stack.append((a,b-1))
        if b != W-1: # 右
            if A[a][b+1] == ".": # 白の場合
                A[a][b+1] = "#"
                new_stack.append((a,b+1))
    stack = new_stack
    if stack:
        flag = True
    else:
        ans -= 1 

print(ans)

Submission status: Time Limit Exceeded

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

A = [["" for _ in range(W)] for _ in range(H)]

stack = []
for i in range(H):
    tmp = list(input())
    for j in range(W):
        A[i][j] = tmp[j]
        if tmp[j] == "#":
            stack.append((i,j))

ans = 0
flag = False
if stack:
    flag = True
while flag:
    ans += 1
    #print(ans, stack)
    flag = False
    new_stack = []
    while stack:
        a,b = stack.pop() # 取り出す
        # A[a][b]の隣接マスについて調べる
        if a != 0: # 上
            if A[a-1][b] == ".": # 白の場合
                A[a-1][b] = "#"
                new_stack.append((a-1,b))
        if a != H-1: # 下
            if A[a+1][b] == ".": # 白の場合
                A[a+1][b] = "#"
                new_stack.append((a+1,b))
        if b != 0: # 左
            if A[a][b-1] == ".": # 白の場合
                A[a][b-1] = "#"
                new_stack.append((a,b-1))
        if b != W-1: # 右
            if A[a][b+1] == ".": # 白の場合
                A[a][b+1] = "#"
                new_stack.append((a,b+1))
    stack = new_stack
    if stack:
        flag = True
    else:
        ans -= 1 

print(ans)

Submission status: Time Limit Exceeded

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

A = [[False for _ in range(W)] for _ in range(H)]

Q = []
for y in range(H):
    S = input()
    for x, s in enumerate(S):
        if s == "#":
            Q.append((y, x))
            A[y][x] = True

ans = 0
while Q:
    ans += 1
    NQ = []
    for y, x in Q:
        if x > 0 and A[y][x-1] == False:
            A[y][x-1] = True
            NQ.append((y,x-1))
        if x < W-1 and A[y][x+1] == False:
            A[y][x+1] = True
            NQ.append((y,x+1))
        if y > 0 and A[y-1][x] == False:
            A[y-1][x] = True
            NQ.append((y-1, x))
        if y < H-1 and A[y+1][x] == False:
            A[y+1][x] = True
            NQ.append((y+1,x))
    if NQ:
        Q = NQ
    else:
        break

print(ans-1)

Submission status: Time Limit Exceeded

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

A = [[False for _ in range(W)] for _ in range(H)]

Q = deque()
for y in range(H):
    S = input()
    for x, s in enumerate(S):
        if s == "#":
            Q.append((y, x))
            A[y][x] = True

ans = 0
while Q:
    ans += 1
    NQ = deque()
    for y, x in Q:
        if x > 0 and A[y][x-1] == False:
            A[y][x-1] = True
            NQ.append((y,x-1))
        if x < W-1 and A[y][x+1] == False:
            A[y][x+1] = True
            NQ.append((y,x+1))
        if y > 0 and A[y-1][x] == False:
            A[y-1][x] = True
            NQ.append((y-1, x))
        if y < H-1 and A[y+1][x] == False:
            A[y+1][x] = True
            NQ.append((y+1,x))
    if NQ:
        Q = NQ
    else:
        break

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

def main():
    H, W = map(int,input().split())

    A = [[s == "#" for s in input()] for _ in range(H)]
    Q = deque([(y, x) for y in range(H) for x in range(W) if A[y][x]])

    ans = 0
    while True:
        ans += 1
        NQ = deque()
        while Q:
            y, x = Q.popleft()
            if x > 0 and A[y][x-1] == False:
                A[y][x-1] = True
                NQ.append((y,x-1))
            if x < W-1 and A[y][x+1] == False:
                A[y][x+1] = True
                NQ.append((y,x+1))
            if y > 0 and A[y-1][x] == False:
                A[y-1][x] = True
                NQ.append((y-1, x))
            if y < H-1 and A[y+1][x] == False:
                A[y+1][x] = True
                NQ.append((y+1,x))
        if NQ:
            Q = copy.copy(NQ)
        else:
            break

    print(ans-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

A = [[s == "#" for s in input()] for _ in range(H)]
Q = deque([(y, x) for y in range(H) for x in range(W) if A[y][x]])

ans = 0
while True:
    ans += 1
    NQ = deque()
    while Q:
        y, x = Q.popleft()
        if x > 0 and A[y][x-1] == False:
            A[y][x-1] = True
            NQ.append((y,x-1))
        if x < W-1 and A[y][x+1] == False:
            A[y][x+1] = True
            NQ.append((y,x+1))
        if y > 0 and A[y-1][x] == False:
            A[y-1][x] = True
            NQ.append((y-1, x))
        if y < H-1 and A[y+1][x] == False:
            A[y+1][x] = True
            NQ.append((y+1,x))
    if NQ:
        Q = copy.copy(NQ)
    else:
        break

print(ans-1)

Submission status: Time Limit Exceeded

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

A = [[False for _ in range(W)] for _ in range(H)]

Start = []
for y in range(H):
    S = input()
    for x, s in enumerate(S):
        if s == "#":
            Start.append((y, x))
            A[y][x] = True
Q = deque(Start)

ans = 0
while True:
    ans += 1
    NQ = deque()
    while Q:
        y, x = Q.popleft()
        if x > 0 and A[y][x-1] == False:
            A[y][x-1] = True
            NQ.append((y,x-1))
        if x < W-1 and A[y][x+1] == False:
            A[y][x+1] = True
            NQ.append((y,x+1))
        if y > 0 and A[y-1][x] == False:
            A[y-1][x] = True
            NQ.append((y-1, x))
        if y < H-1 and A[y+1][x] == False:
            A[y+1][x] = True
            NQ.append((y+1,x))
    if NQ:
        Q = copy.copy(NQ)
    else:
        break

print(ans-1)

Submission status: Time Limit Exceeded

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

A = [[False for _ in range(W)] for _ in range(H)]

Q = deque()
for y in range(H):
    S = input()
    for x, s in enumerate(S):
        if s == "#":
            Q.append((y, x))
            A[y][x] = True

ans = 0
while True:
    ans += 1
    NQ = deque()
    while Q:
        y, x = Q.popleft()
        if x > 0 and A[y][x-1] == False:
            A[y][x-1] = True
            NQ.append((y,x-1))
        if x < W-1 and A[y][x+1] == False:
            A[y][x+1] = True
            NQ.append((y,x+1))
        if y > 0 and A[y-1][x] == False:
            A[y-1][x] = True
            NQ.append((y-1, x))
        if y < H-1 and A[y+1][x] == False:
            A[y+1][x] = True
            NQ.append((y+1,x))
    if NQ:
        Q = NQ
    else:
        break

print(ans-1)

Submission status: Time Limit Exceeded

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

A = [[False for _ in range(W)] for _ in range(H)]

Q = deque()
for y in range(H):
    S = input()
    for x, s in enumerate(S):
        if s == "#":
            Q.append((y, x))
            A[y][x] = True

ans = 0
while True:
    ans += 1
    NQ = deque()
    while Q:
        y, x = Q.pop()
        if x > 0 and A[y][x-1] == False:
            A[y][x-1] = True
            NQ.append((y,x-1))
        if x < W-1 and A[y][x+1] == False:
            A[y][x+1] = True
            NQ.append((y,x+1))
        if y > 0 and A[y-1][x] == False:
            A[y-1][x] = True
            NQ.append((y-1, x))
        if y < H-1 and A[y+1][x] == False:
            A[y+1][x] = True
            NQ.append((y+1,x))
    if NQ:
        Q = copy.copy(NQ)
    else:
        break

print(ans-1)

Submission status: Time Limit Exceeded

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

A = [[False for _ in range(W)] for _ in range(H)]

Q = deque()
for y in range(H):
    S = input()
    for x, s in enumerate(S):
        if s == "#":
            Q.append((y, x))
            A[y][x] = True

ans = 0
while True:
    ans += 1
    NQ = deque()
    while Q:
        y, x = Q.pop()
        if x > 0 and A[y][x-1] == False:
            A[y][x-1] = True
            NQ.append((y,x-1))
        if x < W-1 and A[y][x+1] == False:
            A[y][x+1] = True
            NQ.append((y,x+1))
        if y > 0 and A[y-1][x] == False:
            A[y-1][x] = True
            NQ.append((y-1, x))
        if y < H-1 and A[y+1][x] == False:
            A[y+1][x] = True
            NQ.append((y+1,x))
    if NQ:
        Q = NQ
    else:
        break

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

B = int(1E8)

def main():

    H, W = map(int, input().split())
    
    l = 0
    q = []
    checked = []
    for h in range(H):
        S = input()
        L = []
        for w in range(W):
            if S[w] == '#':
                l += 1
                L.append(True)
                q.append(B*h+w)
            else:
                L.append(False)
        checked.append(L)

    Next = [[[] for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if h != 0:
                Next[h][w].append(B*(h-1) + w)
            if h != H-1:
                Next[h][w].append(B*(h+1) + w)
            if w != 0:
                Next[h][w].append(B*h + w-1)
            if w != W-1:
                Next[h][w].append(B*h + w+1)

    c = -1
    for _ in range(H+W+2):
        qq = []
        if l == 0:
            break
        nl = 0
        for hw in q:
            h, w = hw//B, hw%B
            for nhw in Next[h][w]:
                nh, nw = nhw//B, nhw%B
                if not checked[nh][nw]:
                    qq.append(B*nh + nw)
                    checked[nh][nw] = True
                    nl += 1
        q = qq
        l = nl
        c += 1

    print(c)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
import sys
input = sys.stdin.readline

B = int(1E8)

def main():

    H, W = map(int, input().split())
    
    l = 0
    q = Queue()
    checked = []
    for h in range(H):
        S = input()
        L = []
        for w in range(W):
            if S[w] == '#':
                l += 1
                L.append(True)
                q.put(B*h+w)
            else:
                L.append(False)
        checked.append(L)

    Next = [[[] for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if h != 0:
                Next[h][w].append(B*(h-1) + w)
            if h != H-1:
                Next[h][w].append(B*(h+1) + w)
            if w != 0:
                Next[h][w].append(B*h + w-1)
            if w != W-1:
                Next[h][w].append(B*h + w+1)

    c = -1
    for _ in range(H+W+2):
        if l == 0:
            break
        nl = 0
        for _ in range(l):
            hw = q.get()
            h, w = hw//B, hw%B
            for nhw in Next[h][w]:
                nh, nw = nhw//B, nhw%B
                if not checked[nh][nw]:
                    q.put(B*nh + nw)
                    checked[nh][nw] = True
                    nl += 1
        l = nl
        c += 1

    print(c)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = list(map(int, input().split()))
grid = [list(input()) for i in range(h)]
black = set()
ans = 0

q = deque([])
for i in range(h):
  for j in range(w):
    if grid[i][j]=='#':
      q.append((j, i))
      black.add((j, i))
q.append((-1, -1))

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
while q:
  x, y = q.popleft()
  if (x, y) == (-1, -1):
    ans += 1
    if q:
      q.append((-1, -1))
    continue
  for dxt, dyt in zip(dx, dy):
    nx, ny = x+dxt, y+dyt
    if 0<=nx<=w-1 and 0<=ny<=h-1:
      if (nx, ny) not in black:
        flag = True
        black.add((nx, ny))
        q.append((nx, ny))
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
import sys
input = sys.stdin.readline


def main():
    H, W = map(int, input().split())

    l = 0
    q = Queue()
    checked = []
    for h in range(H):
        S = input()
        L = []
        for w in range(W):
            if S[w] == '#':
                l += 1
                L.append(True)
                q.put((h, w))
            else:
                L.append(False)
        checked.append(L)

    Next = [[[] for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if h != 0:
                Next[h][w].append((h-1, w))
            if h != H-1:
                Next[h][w].append((h+1, w))
            if w != 0:
                Next[h][w].append((h, w-1))
            if w != W-1:
                Next[h][w].append((h, w+1))

    c = -1
    for _ in range(H+W+2):
        if l == 0:
            break
        nl = 0
        for _ in range(l):
            (h, w) = q.get()
            for nh, nw in Next[h][w]:
                if not checked[nh][nw]:
                    q.put((nh, nw))
                    checked[nh][nw] = True
                    nl += 1
        l = nl
        c += 1
    print(c)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
import sys
input = sys.stdin.readline


def main():
    H, W = map(int, input().split())

    l = 0
    q = Queue()
    checked = []
    for h in range(H):
        S = input()
        L = []
        for w in range(W):
            if S[w] == '#':
                l += 1
                L.append(True)
                q.put((h, w))
            else:
                L.append(False)
        checked.append(L)

    Next = [[[] for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if h != 0:
                Next[h][w].append((h-1, w))
            if h != H-1:
                Next[h][w].append((h+1, w))
            if w != 0:
                Next[h][w].append((h, w-1))
            if w != W-1:
                Next[h][w].append((h, w+1))

    c = -1
    while True:
        nl = 0
        if q.empty():
            break
        for _ in range(l):
            (h, w) = q.get()
            for nh, nw in Next[h][w]:
                if not checked[nh][nw]:
                    q.put((nh, nw))
                    checked[nh][nw] = True
                    nl += 1
        l = nl
        c += 1
    print(c)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue


def main():
    H, W = map(int, input().split())

    l = 0
    q = Queue()
    checked = []
    for h in range(H):
        S = input()
        L = []
        for w in range(W):
            if S[w] == '#':
                l += 1
                L.append(True)
                q.put((h, w))
            else:
                L.append(False)
        checked.append(L)

    Next = [[[] for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if h != 0:
                Next[h][w].append((h-1, w))
            if h != H-1:
                Next[h][w].append((h+1, w))
            if w != 0:
                Next[h][w].append((h, w-1))
            if w != W-1:
                Next[h][w].append((h, w+1))

    c = -1
    while True:
        nl = 0
        if q.empty():
            break
        for _ in range(l):
            (h, w) = q.get()
            for nh, nw in Next[h][w]:
                if not checked[nh][nw]:
                    q.put((nh, nw))
                    checked[nh][nw] = True
                    nl += 1
        l = nl
        c += 1
    print(c)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

H, W = map(int, input().split())
state = [[0 if a == '.' else 1 for a in list(input())] for _ in range(H)]

checked = [[False for _ in range(W)] for _ in range(H)]
l = 0
q = Queue()
for h in range(H):
    for w in range(W):
        if state[h][w] == 1:
            checked[h][w] = True
            q.put((h, w))
            l += 1

Next = [[[] for _ in range(W)] for _ in range(H)]
for h in range(H):
    for w in range(W):
        if h != 0:
            Next[h][w].append((h-1, w))
        if h != H-1:
            Next[h][w].append((h+1, w))
        if w != 0:
            Next[h][w].append((h, w-1))
        if w != W-1:
            Next[h][w].append((h, w+1))

c = -1
while True:
    nl = 0
    if q.empty():
        break
    for _ in range(l):
        (h, w) = q.get()
        for nh, nw in Next[h][w]:
            if not checked[nh][nw]:
                q.put((nh, nw))
                checked[nh][nw] = True
                nl += 1
    l = nl
    c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
state = [[0 if a == '.' else 1 for a in list(input())] for _ in range(H)]

checked = [[False for _ in range(W)] for _ in range(H)]
qs = []
for h in range(H):
    for w in range(W):
        if state[h][w] == 1:
            checked[h][w] = True
            qs.append((h, w))

Next = [[[] for _ in range(W)] for _ in range(H)]
for h in range(H):
    for w in range(W):
        if h != 0:
            Next[h][w].append((h-1, w))
        if h != H-1:
            Next[h][w].append((h+1, w))
        if w != 0:
            Next[h][w].append((h, w-1))
        if w != W-1:
            Next[h][w].append((h, w+1))

c = -1
while qs:
    qqs = []
    for h, w in qs:
        for nh, nw in Next[h][w]:
            if not checked[nh][nw]:
                qqs.append((nh, nw))
                checked[nh][nw] = True
    qs = qqs
    c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
state = [[0 if a == '.' else 1 for a in list(input())] for _ in range(H)]

checked = [[False for _ in range(W)] for _ in range(H)]
qs = []
for h in range(H):
    for w in range(W):
        if state[h][w] == 1:
            checked[h][w] = True
            qs.append((h, w))

c = -1
while qs:
    qqs = []
    for h, w in qs:
        nexts = [(h+1, w), (h-1, w), (h, w+1), (h, w-1)]
        for nh, nw in nexts:
            if 0 <= nh <= H-1 and 0 <= nw <= W-1:
                if not checked[nh][nw]:
                    qqs.append((nh, nw))
                    checked[nh][nw] = True
    qs = qqs
    c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
b = [[i == "#" for i in list(input())]+[True] for _ in range(h)]+[[True]*(w+1)]
check = []
for i in range(h):
  for j in range(w):
    if b[i][j]:
      check.append((i,j))
ans = 0
while check:
  new = []
  k = 0
  for i,j in check:
    if not b[i-1][j]:
      new.append((i-1,j))
      b[i-1][j] = True
      k = 1
    if not b[i+1][j]:
      new.append((i+1,j))
      b[i+1][j] = True
      k = 1
    if not b[i][j-1]:
      new.append((i,j-1))
      b[i][j-1] = True
      k = 1
    if not b[i][j+1]:
      new.append((i,j+1))
      b[i][j+1] = True
      k = 1
  check = new
  if k:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
b = [[i == "#" for i in list(input())]+[True] for _ in range(h)]+[[True]*(w+1)]
#print(b)
check = []
for i in range(h):
  for j in range(w):
    if b[i][j]:
      check.append((i,j))
ans = 0
while check:
  new = []
  k = 0
  for i,j in check:
    if not b[i-1][j]:
      new.append((i-1,j))
      b[i-1][j] = True
      k = 1
    if not b[i+1][j]:
      new.append((i+1,j))
      b[i+1][j] = True
      k = 1
    if not b[i][j-1]:
      new.append((i,j-1))
      b[i][j-1] = True
      k = 1
    if not b[i][j+1]:
      new.append((i,j+1))
      b[i][j+1] = True
      k = 1
  check = new
  if k:
    ans += 1
  #print(b)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
b = [[i == "#" for i in list(input())]+[True] for _ in range(h)]+[[True]*(w+1)]
#print(b)
check = []
for i in range(h):
  for j in range(w):
    if b[i][j]:
      check.append((i,j))
#print(b[-2][1])
ans = 0
while check:
  new = []
  k = 0
  for i,j in check:
    if not b[i-1][j]:
      new.append((i-1,j))
      b[i-1][j] = True
      k = 1
    if not b[i+1][j]:
      new.append((i+1,j))
      b[i+1][j] = True
      k = 1
    if not b[i][j-1]:
      new.append((i,j-1))
      b[i][j-1] = True
      k = 1
    if not b[i][j+1]:
      new.append((i,j+1))
      b[i][j+1] = True
      k = 1
  check = new
  if k:
    ans += 1
  #print(b)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h,w = map(int,input().split())
b = np.reshape(np.array([list(i) + [True] for i in np.reshape([i == "#" for i in list(np.reshape(np.array([list(input()) for i in range(h)]),(1,h*w)))],(h,w))]+[[True]*(w+1)]),(h+1,w+1))
#print(b)
check = []
for i in range(h):
  for j in range(w):
    if b[i][j]:
      check.append((i,j))
#print(b[-2][1])
ans = 0
while check:
  new = []
  k = 0
  for i,j in check:
    if not b[i-1][j]:
      new.append((i-1,j))
      b[i-1][j] = True
      k = 1
    if not b[i+1][j]:
      new.append((i+1,j))
      b[i+1][j] = True
      k = 1
    if not b[i][j-1]:
      new.append((i,j-1))
      b[i][j-1] = True
      k = 1
    if not b[i][j+1]:
      new.append((i,j+1))
      b[i][j+1] = True
      k = 1
  check = new
  if k:
    ans += 1
  #print(b)
print(ans)

Submission status: Time Limit Exceeded

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


D = [[-1] * W for i in range(H)]
queue = deque([])
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            queue.append([h, w])
            D[h][w] = 0


while queue:
    nh, nw = queue.pop()
    for dh, dw in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        if not ((0 <= nh + dh < H) and (0 <= nw + dw < W)):
            continue

        if D[nh + dh][nw + dw] >= 0:
            continue

        D[nh + dh][nw + dw] = D[nh][nw] + 1
        queue.appendleft([nh + dh, nw + dw])


ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, D[h][w])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

def run():
  H, W = map(int, input().split())
  fl_list = [['#']*(W+2)]
  q = Queue()
  for h in range(H):
    fl = list('#'+input()+'#')
    for i, x in enumerate(fl[1:-1]):
      if x == '#': q.put([h+1, i+1, 0])
    fl_list.append(fl)
  fl_list.append(['#']*(W+2))
  while True:
    if q.empty(): break
    y, x, t = q.get()
    for i, n in [(0,1),(0,-1),(1,0),(-1,0)]:
      if fl_list[y+i][x+n] == '.':
        q.put([y+i, x+n, t+1])
        fl_list[y+i][x+n] = '#'
  print(t)
  
run()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


H, W = map(int, input().split())
A = [list('#' * (W + 2))]
q = deque()
A_append = A.append
q_append = q.append
for _ in range(H):
    a = input()
    A_append(list('#' + a + '#'))
A.append(list('#' * (W + 2)))
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

for i in range(1, H + 1):
    for j in range(1, W + 1):
        if A[i][j] == '#':
            q_append([i, j, 0])

ans = 0

while len(q) != 0:
    p = q.popleft()
    for k in range(4):
        y = p[0] + dy[k]
        x = p[1] + dx[k]
        c = p[2]
        ans = max(ans, c)
        if A[y][x] == '.':
            A[y][x] = '#'
            q_append([y, x, c + 1])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
r,c=map(int,input().split())
grid=[input() for _ in [0]*r]
ans=sum([grid[i].count(".") for i in range(r)])
q=[]
[[q.append([i,j]) for j in range(c) if grid[i][j]=="#"] for i in range(r)]
visit=[[grid[i][j]=="#" for j in range(c)] for i in range(r)]
d=[(1,0),(-1,0),(0,1),(0,-1)]
cnt=0

while q:
    qq=[]
    while q:
        i,j=q.pop()
        for dx,dy in d:
            if 0<=i+dx<r and 0<=j+dy<c:
                if i+dx==r-1 and j+dy==c-1:
                    flag=True
                if visit[i+dx][j+dy]==False:
                    visit[i+dx][j+dy]=True
                    qq.append([i+dx,j+dy])
    q=qq
    cnt+=1
    
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
class Queue:
    def __init__(self, data=[]):
        self.data = data

    def enqueue(self, x):
        self.data.append(x)

    def dequeue(self):
        return self.data.pop(0)

    def is_Empty(self):
        if len(self.data) == 0:
            return True
        else:
            return False


H, W = map(int, input().split())  # H行W列

gridgraph = [list(input()) for _ in range(H)]  # H行W列のグリッドグラフ
visited = [[False]*W for _ in range(H)]
cnt = [[0]*W for _ in range(H)]

queue = Queue()

for i in range(H):
    for j in range(W):
        if gridgraph[i][j] == '#':
            queue.enqueue([i, j])  # 初期の時点で黒色のマスをqueueに追加する
            visited[i][j] = True

while not queue.is_Empty():
    cy, cx = queue.dequeue()

    for dy, dx in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        if cy+dy >= H or cy+dy < 0 or cx+dx >= W or cx+dx < 0:
            continue
        if visited[cy+dy][cx+dx]:  # すでに訪問済みであればcontinue
            continue
        visited[cy+dy][cx+dx] = True  # 訪問済みにする
        cnt[cy+dy][cx+dx] = cnt[cy][cx] + 1
        queue.enqueue([cy+dy, cx+dx])


ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, cnt[i][j])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

from collections import deque

H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
T=[[10000]*W for i in range(H)]


for i in range(H):
	for j in range(W):
		if A[i][j]=='#':
			seen=[[False]*H for i in range(W)]
			seen[i][j]=True
			
			ne=deque([(i,j,0)])
			
			while ne:
				y,x,d=ne.popleft()
				seen[y][x]=True
				T[y][x]=min(T[y][x], d)
				for ny,nx in [(y+1, x), (y-1,x), (y,x+1),(y,x-1)]:
					if 0<=ny<H and 0<=nx<W and seen[ny][nx]==False and A[ny][nx]=='.':
						ne.append((ny,nx,d+1))

print(max([max(t) for t in T]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)


H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
T=[[10000]*W for i in range(H)]


for i in range(H):
	for j in range(W):
		if A[i][j]=='#':
			seen=[[False]*H for i in range(W)]
			seen[i][j]=True
			
			ne=[(i,j,0)]
			while ne!=[]:
				y,x,d=ne[0]
				seen[y][x]=True
				ne.remove(ne[0])
				T[y][x]=min(T[y][x], d)
				for ny,nx in [(y+1, x), (y-1,x), (y,x+1),(y,x-1)]:
					if 0<=ny<H and 0<=nx<W and seen[ny][nx]==False and A[ny][nx]=='.':
						ne.append((ny,nx,d+1))

print(max([max(t) for t in T]))