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
input = sys.stdin.readline
 
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
import queue
 
q = queue.Queue()
grid = []
h, w = getList()
black = [[4300 for i in range(w)] for j in range(h)]
for i in range(h):
    tmp = input()
    for j, c in enumerate(tmp):
        if c == "#":
            black[i][j] = 0
            q.put((i,j))
 
 
while(not q.empty()):
    x,y = q.get()
 
    if x>0:
        if black[x - 1][y] > black[x][y] + 1:
            black[x - 1][y] = black[x][y] + 1
            q.put((x - 1, y))
 
    if y > 0:
        if black[x][y - 1] > black[x][y] + 1:
            black[x][y - 1] = black[x][y] + 1
            q.put((x, y - 1))
 
    if x<h-1:
        if black[x + 1][y ] > black[x][y] + 1:
            black[x + 1][y] = black[x][y] + 1
            q.put((x + 1, y))
 
    if y < w - 1:
        if black[x][y + 1] > black[x][y] + 1:
            black[x][y + 1] = black[x][y] + 1
            q.put((x, y + 1))
 
print(max([max(col) for col in black]))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
maze = [input() for _ in range(H)]
seen = [[-1] * W for _ in range(H)]

from collections import deque


queue = deque()
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            queue.append([i, j, 0])
            seen[i][j] = 0

def bfs(maze, seen):
    while queue:
        y, x, c = queue.popleft()
        for i, j in [1, 0], [-1, 0], [0, 1], [0, -1]:
            dy = y + i
            dx = x + j
            if dy < 0 or H <= dy or dx < 0 or W <= dx:
                continue
            if seen[dy][dx] > -1:
                continue
            if maze[dy][dx] == '#':
                continue
            seen[dy][dx] = c + 1
            queue.append([dy, dx, c+1])

def check_max(seen):
    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(ans, seen[i][j])
    return ans
    
bfs(maze, seen)
print(check_max(seen))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

def main():
    B = []

    for i,a in enumerate(A):
        for j,b in enumerate(a):
            if b == "#":
                B.append((i,j))

    dxy = [[1,0],[-1,0],[0,1],[0,-1]]

    stack = deque(B)
    darked = len(stack)
    targetd = h*w
    count = 0

    while darked < targetd:
        nextd = deque([])

        while stack:
            x, y = stack.popleft()
            for dx,dy in dxy:
                X = x + dx
                Y = y + dy
                if not(0 <= X < h) or not(0 <= Y < w):
                    continue
                if A[X][Y]==".":
                    A[X][Y]="#"
                    nextd.append((X,Y))
        count += 1
        stack = nextd
        darked += len(stack)
    print(count)
    
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

B = []
for i,a in enumerate(A):
    for j,b in enumerate(a):
        if b == "#":
            B.append((i,j))
            
dxy = [[1,0],[-1,0],[0,1],[0,-1]]

stack = deque(B) # はじめの"#"の位置
darked = len(stack) # はじめの"#"の数
targetd = h*w
count = 0

while darked < targetd:
    nextd = deque([])
    
    while stack:
        x, y = stack.popleft()
        for dx,dy in dxy:
            X = x + dx
            Y = y + dy
            if not(0 <= X < h) or not(0 <= Y < w):
                continue
            if A[X][Y]==".":
                A[X][Y]="#"
                nextd.append((X,Y))
    count += 1
    stack = nextd
    darked += len(stack)
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [-1] * (w * h)  # 前処理
    que = deque()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[j + (w * i)] = 0
                que.append((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if 0 <= i < h and 0 <= j < w and dist[j + (w * i)] < 0:
                dist[j + (w * i)] = dist[y + (w * x)] + 1
                que.append((i, j))
    return max(dist)


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    que, frag = deque(), set()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                que.append((i, j, 0)), frag.add((i, j))

    while len(que) > 0:
        (x, y, d) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if (i, j) in frag:  # 処理済みか否か
                continue
            if 0 <= i < h and 0 <= j < w:
                que.append((i, j, d + 1)), frag.add((i, j))
    return d


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [-1] * (w * h)
    que, frag = deque(), set()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i * w + j] = 0
                que.append((i, j)), frag.add((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if (i, j) in frag:  # 処理済みか否か
                continue
            if 0 <= i < h and 0 <= j < w:
                dist[i * w + j] = dist[x * w + y] + 1
                que.append((i, j)), frag.add((i, j))
    return max(dist)


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [-1] * (w * h)
    que, frag = deque(), set()
    quead, fragad = que.append, frag.add
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[j + (w * i)] = 0
                quead((i, j)), fragad((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if (i, j) in frag:  # 処理済みか否か
                continue
            if 0 <= i < h and 0 <= j < w:
                dist[j + (w * i)] = dist[y + (w * x)] + 1
                quead((i, j)), fragad((i, j))
    return max(dist)


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [-1] * (w * h)
    que, frag = deque(), set()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[j + (w * i)] = 0
                que.append((i, j)), frag.add((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if (i, j) in frag:  # 処理済みか否か
                continue
            if 0 <= i < h and 0 <= j < w:
                dist[j + (w * i)] = dist[y + (w * x)] + 1
                que.append((i, j)), frag.add((i, j))
    return max(dist)


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [-1] * (w * h)
    que, frag = deque(), set()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[j + (w * i)] = 0
                que.append((i, j)), frag.add((i, j))
    
    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if (i, j) in frag:  # 処理済みか否か
                continue
            if 0 <= i < h and 0 <= j < w:
                dist[j + (w * i)] = dist[y + (w * x)] + 1
                que.append((i, j)), frag.add((i, j))
    return dist


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

Submission status: Time Limit Exceeded

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


def bfs(S):  # 幅優先探索  # キュー
    dist = [[-1] * w for _ in range(h)]  # 前処理
    que, frag = deque(), set()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i][j] = 0
                que.append((i, j)), frag.add((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if (i, j) in frag:  # 処理済みか否か
                continue
            if 0 <= i < h and 0 <= j < w:
                dist[i][j] = dist[x][y] + 1
                que.append((i, j)), frag.add((i, j))
    return dist


h, w = map(int, input().split())
a = [input() for _ in range(h)]
ans = bfs(a)
print(max(max(ansi) for ansi in ans))

Submission status: Time Limit Exceeded

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


def bfs(S):  # 幅優先探索  # キュー
    dist = [[-1] * w for _ in range(h)]  # 前処理
    que, frag = deque(), set()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i][j] = 0
                que.append((i, j)), frag.add((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if (i, j) in frag:  # 処理済みか否か
                continue
            if 0 <= i < h and 0 <= j < w:
                dist[i][j] = dist[x][y] + 1
                que.append((i, j)), frag.add((i, j))
    return dist


if __name__ == '__main__':
    h, w = map(int, input().split())
    a = [input() for _ in range(h)]
    ans = bfs(a)
    print(max(max(ansi) for ansi in ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [[-1] * w for _ in range(h)]  # 前処理
    que, frag = deque(), set()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i][j] = 0
                que.append((i, j)), frag.add((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if (i, j) in frag:  # 処理済みか否か
                continue
            if 0 <= i < h and 0 <= j < w:
                dist[i][j] = dist[x][y] + 1
                que.append((i, j)), frag.add((i, j))
    return dist


if __name__ == '__main__':
    h, w = map(int, input().split())
    a = [input() for _ in range(h)]
    ans = bfs(a)
    print(max(max(ansi) for ansi in ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def bfs(S,H,W):  # 幅優先探索  # キュー
    dist = [[-1] * W for _ in range(H)]  # 前処理
    que, frag = deque(), set()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i][j] = 0
                que.append((i, j)), frag.add((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if (i, j) in frag:  # 処理済みか否か
                continue
            if 0 <= i < H and 0 <= j < W:
                dist[i][j] = dist[x][y] + 1
                que.append((i, j)), frag.add((i, j))
    return dist

def main():
    h, w = map(int, input().split())
    a = [input() for _ in range(h)]
    ans = bfs(a, h, w)
    print(max(max(ansi) for ansi in ans))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [[-1] * w for _ in range(h)]  # 前処理
    que, frag = deque(), set()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i][j] = 0
                que.append((i, j)), frag.add((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if (i, j) in frag:  # 処理済みか否か
                continue
            if 0 <= i < h and 0 <= j < w:
                dist[i][j] = dist[x][y] + 1
                que.append((i, j)), frag.add((i, j))
    return dist


h, w = map(int, input().split())
a = [input() for _ in range(h)]
ans = bfs(a)
print(max(max(ansi) for ansi in ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [[-1] * w for _ in range(h)]  # 前処理
    que, frag = deque(), set()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i][j] = 0
                que.append((i, j)), frag.add((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if ((i, j) in frag):  # 処理済みか否か
                continue
            if 0 <= i < h and 0 <= j < w:
                dist[i][j] = dist[x][y] + 1
                que.append((i, j)), frag.add((i, j))
    return dist


h, w = map(int, input().split())
a = [input() for _ in range(h)]
ans = bfs(a)
print(max(max(ansi) for ansi in ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [[-1] * w for _ in range(h)]  # 前処理
    que, frag = deque(), set()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i][j] = 0
                que.append((i, j)), frag.add((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if (i, j) in frag:  # 処理済みか否か
                continue
            if 0 <= i < h and 0 <= j < w:
                dist[i][j] = dist[x][y] + 1
                que.append((i, j)), frag.add((i, j))
    return dist


h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(max(max(ans) for ans in bfs(a)))

Submission status: Time Limit Exceeded

Solution code:
import queue
h,w=map(int,input().split())
a=[input() for _ in range(h)]
q=[]
dist=[[-1 for _ in range(w)]for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append([i,j])
            dist[i][j]=0
q=queue.deque(q)
d=[[1,0],[0,1],[-1,0],[0,-1]]
while q:
    y,x=q.popleft()
    for dy,dx in d:
        ny,nx=y+dy,x+dx
        if 0<=ny and ny<h and 0<=nx and nx<w and dist[ny][nx]==-1:
            dist[ny][nx]=dist[y][x]+1
            q.append([ny,nx])
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans,dist[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
town = [list(input()) for _ in range(h)]

from collections import deque

seen = [[float("inf")] * w for _ in range(h)]
que = deque([])
direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]

for i in range(w):
    for j in range(h):
        if town[j][i] == "#":
            seen[j][i] = 0
            x = i
            y = j
            que.append((x, y))
while que:
    for i in seen:
        if not "inf" in i:
            break
    p, q = que.popleft()
    for dx, dy in direction:
            nx = p + dx
            ny = q + dy
            if 0 <= nx < w and 0 <= ny < h and town[ny][nx] != "#" and seen[ny][nx] == float("inf"):
                que.append((nx, ny))
                seen[ny][nx] = seen[q][p] + 1

ans = max(list(map(lambda x: max(x), seen)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
town = [list(input()) for _ in range(h)]

from collections import deque

seen = [[float("inf")] * w for _ in range(h)]
que = deque([])
direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]

for i in range(w):
    for j in range(h):
        if town[j][i] == "#":
            seen[j][i] = 0
            x = i
            y = j
            que.append((x, y))
while que:
    p, q = que.popleft()
    for dx, dy in direction:
            nx = p + dx
            ny = q + dy
            if 0 <= nx < w and 0 <= ny < h and town[ny][nx] != "#" and seen[ny][nx] == float('inf'):
                que.append((nx, ny))
                seen[ny][nx] = seen[q][p] + 1

ans = max(list(map(lambda x: max(x), seen)))
print(ans)

Submission status: Time Limit Exceeded

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

def get_start_idx(area):
    start_idx = []
    for h in range(H):
        for w in range(W):
            if area[h][w] == "#":
                start_idx.append([h, w])
    return start_idx

que = get_start_idx(area)
memo = [[-1 for _ in range(W)] for _ in range(H)]
patterns = [[0, -1], [0, 1], [1, 0], [-1, 0]]
ans = 0

for idx in que:
    memo[idx[0]][idx[1]] = 0
    
while len(que) != 0:
    idx = que.pop(0)
    for p in patterns:
        if 0 <= idx[0]+p[0] < H and 0 <= idx[1]+p[1] < W:
            if memo[idx[0]+p[0]][idx[1]+p[1]] == -1:
                memo[idx[0]+p[0]][idx[1]+p[1]] = memo[idx[0]][idx[1]]+1
                que.append([idx[0]+p[0], idx[1]+p[1]])
                if ans < memo[idx[0]+p[0]][idx[1]+p[1]]:
                    ans = memo[idx[0]+p[0]][idx[1]+p[1]]
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def input():
    return sys.stdin.readline().strip()

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

    def bfs(x,y,A):
        que = deque()
        que.append((x,y))

        while que:
            x,y = que.popleft()
            if A[y][x] == '#':
                A[y][x] = 0
            for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
                sx = x + dx
                sy = y + dy
                if sx < 0 or sx >= W or sy < 0 or sy >= H or A[sy][sx] == '#':
                    continue
                cnt = A[y][x] + 1
                if A[sy][sx] == '.':
                    que.append((sx,sy))
                    A[sy][sx] = cnt
                elif A[sy][sx] > cnt:
                    que.append((sx,sy))
                    A[sy][sx] = cnt

    for x in range(W):
        for y in range(H):
            if A[y][x] == '#':
                bfs(x,y,A)
    ans = 0
    for a in A:
        ans = max(ans,max(a))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def input():
    return sys.stdin.readline().strip()

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

    def bfs(x,y,A):
        que = deque()
        que.append((x,y))

        while que:
            x,y = que.popleft()
 
            for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
                sx = x + dx
                sy = y + dy
                if sx < 0 or sx >= W or sy < 0 or sy >= H or A[sy][sx] == '#':
                    continue
                cnt = 1 if A[y][x] == '#' else A[y][x] + 1
                if A[sy][sx] == '.':
                    que.append((sx,sy))
                    A[sy][sx] = cnt
                elif A[sy][sx] > cnt:
                    que.append((sx,sy))
                    A[sy][sx] = cnt

    for x in range(W):
        for y in range(H):
            if A[y][x] == '#':
                bfs(x,y,A)
    ans = 0
    for a in A:
        a = [i if i != '#' else 0 for i in a]
        ans = max(ans,max(a))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
a = [input() for i in range(h)]

cnt = [[-1]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            cnt[i][j] = 0

ans = 0
f = True
while f:
    f = False
    for i in range(h):
        for j in range(w):
            if cnt[i][j] != ans:
                if cnt[i][j]==-1 or cnt[i][j]>ans:
                    f = True
                continue
            for k,l in [[-1,0],[1,0],[0,-1],[0,1]]:
                if 0<=i+k<h and 0<=j+l<w and cnt[i+k][j+l]==-1:
                    cnt[i+k][j+l] = ans+1
    if f:ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W = LI()
    A = [SS() for _ in range(H)]

    d = ((1, 0), (0, 1), (-1, 0), (0, -1))

    dist = [[INF] * W for i in range(H)]
    que = collections.deque()

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

    while que:
        cy, cx = que.popleft()
        for dy, dx in d:
            ny = cy + dy
            nx = cx + dx
            if 0 <= ny < H and 0 <= nx < W and dist[cy][cx] + 1 < dist[ny][nx]:
                dist[ny][nx] = dist[cy][cx] + 1
                que.append((ny, nx))

    # for i in dist:
    #     print(i)

    ans = max([max(i) for i in dist])
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
A = [[] for _ in range(h)]
for i in range(h):
    A[i] = list(input())

from collections import deque

d = deque()
count_black = 0
for i in range(h):
    for j in range(w):
        if A[i][j] == '#':
            d.append((i, j))
            count_black += 1

count_while = h * w - count_black

cnt = 0
while count_while:
    while d:
        y, x = d.popleft()
        for dy, dx in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            ny, nx = y + dy, x + dx
            if ny < 0 or ny >= h or nx < 0 or nx >= w: continue
            if A[ny][nx] == '#': continue
            A[ny][nx] = '#'

    # 再構築
    d = deque()
    count_black = 0
    for i in range(h):
        for j in range(w):
            if A[i][j] == '#':
                d.append((i, j))
                count_black += 1

    count_while = h * w - count_black
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
INF = 1 << 60

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

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

ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            continue
        cnt = INF
        for k in b:
            cnt = min(cnt, abs(i - k[0]) + abs(j - k[1]))
        ans = max(ans, cnt) 

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

def bfs1():
  global count
  mx=[1, -1, 0, 0]
  my=[0, 0, 1, -1]
  while not q1.empty():
    y, x = q1.get()
    for i in range(4):
      nx = x+mx[i]
      ny = y+my[i]
      if 0<=nx<w and 0<=ny<h and s[ny][nx]==".":
        s[ny][nx]="#"
        q2.put([ny, nx])
        count+=1
  return

def bfs2():
  global count
  mx=[1, -1, 0, 0]
  my=[0, 0, 1, -1]
  while not q2.empty():
    y, x = q2.get()
    for i in range(4):
      nx = x+mx[i]
      ny = y+my[i]
      if 0<=nx<w and 0<=ny<h and s[ny][nx]==".":
        s[ny][nx]="#"
        q1.put([ny, nx])
        count+=1
  return

h, w = map(int, input().split())
t = [input() for i in range(h)]
vis = [[0]*w for i in range(h)]
s = [["#"]*w for i in range(h)]
a = 0
q1 = queue.Queue()
q2 = queue.Queue()

for i in range(h):
  for j in range(w):
    if t[i][j]==".":
      s[i][j]="."
      a+=1
    else:
      q1.put([i,j])

ans = 0
count=0

while count<a:
  if ans%2==0:
    bfs1()
  else:
    bfs2()
  ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import chain

INF = 10**18

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

q = deque([])
dist = [[INF for _ in range(W)]for _ in range(H)]
for y, A_line in enumerate(A):
    for x, a in enumerate(A_line):
        if a == "#":
            dist[y][x] = 0
            q.append((x, y))

while q:
    t_pos = tx, ty = q.popleft()
    dist_t = dist[ty][tx]

    for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        pos = x, y = tx+dx, ty+dy
        if not (0 <= x < W and 0 <= y < H):
            continue
        elif A[y][x] == "#":
            continue
        elif dist[y][x] <= dist_t + 1:
            continue
        dist[y][x] = dist_t + 1
        q.append(pos)
# print(dist)

r = max(chain(*dist))
print(r)

Submission status: Time Limit Exceeded

Solution code:
def bfs(i, j):
  global count
  x = j
  y = i
  mx=[1, -1, 0, 0]
  my=[0, 0, 1, -1]
  for i in range(4):
    nx = x+mx[i]
    ny = y+my[i]
    if 0<=nx<w and 0<=ny<h and s[ny][nx]==".":
      s[ny][nx]="#"
      vis[ny][nx]=ans+1
      count+=1
  return

h, w = map(int, input().split())
t = [input() for i in range(h)]
vis = [[0]*w for i in range(h)]
s = [["#"]*w for i in range(h)]
a = 0

for i in range(h):
  for j in range(w):
    if t[i][j]==".":
      s[i][j]="."
      a+=1

ans = 0
count = 0

while count<a:
  for i in range(h):
    for j in range(w):
      if s[i][j]=="#" and vis[i][j]==ans:
        bfs(i, j)
  ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

def bfs(i, j):
  global count
  x = j
  y = i
  mx=[1, -1, 0, 0]
  my=[0, 0, 1, -1]
  for i in range(4):
    nx = x+mx[i]
    ny = y+my[i]
    if 0<=nx<w and 0<=ny<h and s[ny][nx]==".":
      s[ny][nx]="#"
      vis[ny][nx]=ans+1
      count+=1
  return

h, w = map(int, input().split())
t = [input() for i in range(h)]
vis = [[0]*w for i in range(h)]
s = [["#"]*w for i in range(h)]
a = 0

for i in range(h):
  for j in range(w):
    if t[i][j]==".":
      s[i][j]="."
      a+=1

ans = 0
count = 0
c = 0

while count<a:
  for i in range(h):
    for j in range(w):
      if s[i][j]=="#" and vis[i][j]==ans:
        bfs(i, j)
  ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

def bfs(i, j):
  x = j
  y = i
  mx=[1, -1, 0, 0]
  my=[0, 0, 1, -1]
  for i in range(4):
    nx = x+mx[i]
    ny = y+my[i]
    if 0<=nx<w and 0<=ny<h and s[ny][nx]=="#" and vis[ny][nx]==0:
      s[y][x]="#"
      vis[y][x]=1
      break
  return

h, w = map(int, input().split())
t = [input() for i in range(h)]
s = [["."]*w for i in range(h)]
for i in range(h):
  for j in range(w):
    if t[i][j]=="#":
      s[i][j]="#"
  
ans = 0
flg = True

while flg:
  flg = False
  vis = [[0]*w for i in range(h)]
  for i in range(h):
    for j in range(w):
      if s[i][j]==".":
        if not flg:
          flg=True
          ans+=1
        bfs(i, j)
  #for i in range(h):
  #  print(s[i])
  #print(" ")
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    H, W = list(map(int, input().split()))
    A = [['!'] * (W + 2)] + [['!', ] + list(input()) + ['!', ] for _ in range(H)] + [['!'] * (W + 2)]
    printl = lambda A:[print(''.join(a)) for a in A]
    INF = 100000
    ans = 0
    dxy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    for h in range(1, H + 1):
        for w in range(1, W + 1):
            if A[h][w] == '#': continue
            stack = deque([[h, w], ])
            count = 0
            visited = [[0] * (W + 2) for _ in range(H + 2)]
            score = [[INF] * (W + 2) for _ in range(H + 2)]
            score[h][w] = 0
            f = False
            while stack:
                x, y = stack.popleft()
                if visited[x][y]:
                    continue
                else:
                    visited[x][y] = 1
                for dx, dy in dxy:
                    X, Y = x + dx, y + dy
                    if A[X][Y] == '#':
                        f = True
                        count = score[x][y] + 1
                        break
                    elif A[X][Y] == '.' and visited[X][Y] == 0:
                        stack.append([X, Y])
                        score[X][Y] = min(score[X][Y], score[x][y] + 1)
                if f:
                    break
            ans = max(ans, count)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
H, W = map(int, input().split())
map = [list(input()) for i in range(H)]
checked = list()
queue = deque()
for x in range(H):
    checked.append(list())
    for y in range(W):
        if map[x][y]=="#":
            checked[x].append(True)
            queue.append((x, y, 0))
        else:
            checked[x].append(False)
neighbors = [(1,0), (0,1), (-1,0), (0,-1)]
while queue:
    x, y, res = queue.popleft()
    for dx, dy in neighbors:
        nx, ny = x+dx, y+dy
        if 0<=nx<H and 0<=ny<W:
            if not checked[nx][ny]:
                queue.append((nx, ny, res+1))
                checked[nx][ny] = True
print(res)