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 queue

def bfs(s1,s2):
    queueX = queue.Queue()
    queueY = queue.Queue()
    queueX.put(s1)
    queueY.put(s2)
    #s[s1][s2] = 0
    #while queueX.empty() == False:
    x = queueX.get()
    y = queueY.get()

    for i in range(4):
        nextX = x + moveR[i]
        nextY = y + moveC[i]
        if 0 <= nextX and nextX < H\
            and 0 <= nextY and nextY < W\
            and s[nextX][nextY] != '#'\
            and s[nextX][nextY] == '.':
            s[nextX][nextY] = '#'
            queueX.put(nextX)
            queueY.put(nextY)

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
moveR = [0, 1, -1, 0]
moveC = [1, 0, 0, -1]

ans = 0
while True:
    cnt = 0
    cntlst = []
    for i in range(H):
        for j in range(W):
            if s[i][j] == '#':
                cntlst.append([i, j])
                cnt += 1
    if cnt == (H * W):
        break
    for i in cntlst:
        bfs(i[0], i[1])
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = []
q = []
for j in range(H):
    A.append(list(input()))
    for i in range(W):
        if A[-1][i] == "#":
            q.append([j, i])


def solve(q):
    nq = []
    while q:
        ty, tx = q.pop(0)
        for dy, dx in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            ny, nx = ty + dy, tx + dx
            if ny < 0 or ny >= H or nx < 0 or nx >= W:
                continue
            elif A[ny][nx] == ".":
                A[ny][nx] = "#"
                nq.append([ny, nx])
    return nq


temp = 0
while True:
    q = solve(q)
    if not q:
        break
    else:
        temp += 1

print(temp)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = []
nb = 0
q = []
for j in range(H):
    A.append(list(input()))
    nb += A[-1].count("#")
    for i in range(W):
        if A[-1][i] == "#":
            q.append([j, i])


def solve(q):
    nq = []
    while q:
        ty, tx = q.pop(0)
        for dy, dx in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            ny, nx = ty + dy, tx + dx
            if ny < 0 or ny >= H or nx < 0 or nx >= W:
                continue
            elif A[ny][nx] == "#":
                continue
            else:
                A[ny][nx] = "#"
                nq.append([ny, nx])
    return nq


temp = 0
while True:
    q = solve(q)
    if not q:
        break
    else: 
        temp += 1

print(temp)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


dir_y = [1, 0, -1, 0]
dir_x = [0, 1, 0, -1]
def paint():
    for _ in range(len(que)):
        y, x = que.popleft()
        for i in range(4):
            next_y = y + dir_y[i]
            next_x = x + dir_x[i]
            if 0 <= next_y < H and 0 <= next_x < W and not has_visited[next_y][next_x]:
                has_visited[next_y][next_x] = True
                que.append((next_y, next_x))


H, W = map(int, input().split())
canvas = []
has_visited = [[False]*W for _ in range(H)]
que = deque()
for y in range(H):
    canvas.append(input())
    for x in range(W):
        if canvas[y][x] == "#":
            que.append((y, x))
            has_visited[y][x] = True

count = 0
while len(que) > 0:
    paint()
    count += 1

print(count-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


dir_y = [1, 0, -1, 0]
dir_x = [0, 1, 0, -1]
def paint():
    for _ in range(len(que)):
        y, x = que.popleft()
        for i in range(4):
            next_y = y + dir_y[i]
            next_x = x + dir_x[i]
            if 0 <= next_y < H and 0 <= next_x < W and not has_visited[next_y][next_x]:
                has_visited[next_y][next_x] = True
                que.append((next_y, next_x))


H, W = map(int, input().split())
canvas = []
has_visited = [[False]*W for _ in range(H)]
que = deque()
for y in range(H):
    canvas.append(list(input()))
    for x in range(W):
        if canvas[y][x] == "#":
            que.append((y, x))
            has_visited[y][x] = True

count = 0
while len(que) > 0:
    paint()
    count += 1

print(count-1)

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy

H,W = map(int,input().split())
c =[]
c.append(['×' for _ in range(W+2)])
ans = []
ans.append([0 for _ in range(W+2)])
q = queue.Queue()
for i in range(H):
    tmp = list('×'+input()+'×')
    ans_tmp = []
    for j in range(W+2):
        if tmp[j] == '#':
            ans_tmp.append(0)
            q.put([j,i+1])
        elif tmp[j] == '×':
            ans_tmp.append(0)
        else:
            ans_tmp.append(10**4)
    c.append(tmp)
    ans.append(ans_tmp)

c.append(['×' for _ in range(W+2)])
ans.append([0 for _ in range(W+2)])


def bfs(q):
    while not q.empty():
        x,y = q.get()
        if c[y][x-1] == '.':
            q.put([x-1,y])
            ans[y][x-1] = ans[y][x] + 1
            c[y][x-1] = '#'
        if c[y][x+1] == '.':
            q.put([x+1,y])
            ans[y][x+1] = ans[y][x] + 1
            c[y][x+1] = '#'
        if c[y-1][x] == '.':
            q.put([x,y-1])
            ans[y-1][x] = ans[y][x] + 1
            c[y-1][x] = '#'
        if c[y+1][x] == '.':
            q.put([x,y+1])
            ans[y+1][x] = ans[y][x] + 1
            c[y+1][x] = '#'

bfs(q)
max_ans = 0
for i in range(H+2):
    #print(ans[i])
    max_ans = max(max_ans,max(ans[i]))

print(max_ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

H,W = map(int,input().split())
c =[]
c.append(['×' for _ in range(W+2)])
ans = []
ans.append([0 for _ in range(W+2)])
q = deque()
for i in range(H):
    tmp = list('×'+input()+'×')
    ans_tmp = []
    for j in range(W+2):
        if tmp[j] == '#':
            ans_tmp.append(0)
            q.append([j,i+1])
        elif tmp[j] == '×':
            ans_tmp.append(0)
        else:
            ans_tmp.append(10**4)
    c.append(tmp)
    ans.append(ans_tmp)

c.append(['×' for _ in range(W+2)])
ans.append([0 for _ in range(W+2)])


def bfs(q):
    while q:
        x,y = q.popleft()
        if c[y][x-1] == '.':
            q.append([x-1,y])
            ans[y][x-1] = ans[y][x] + 1
            c[y][x-1] = '#'
        if c[y][x+1] == '.':
            q.append([x+1,y])
            ans[y][x+1] = ans[y][x] + 1
            c[y][x+1] = '#'
        if c[y-1][x] == '.':
            q.append([x,y-1])
            ans[y-1][x] = ans[y][x] + 1
            c[y-1][x] = '#'
        if c[y+1][x] == '.':
            q.append([x,y+1])
            ans[y+1][x] = ans[y][x] + 1
            c[y+1][x] = '#'

bfs(q)
max_ans = 0
for i in range(H+2):
    #print(ans[i])
    max_ans = max(max_ans,max(ans[i]))

print(max_ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy

H,W = map(int,input().split())
c =[]
c.append(['×' for _ in range(W+2)])
ans = []
ans.append([0 for _ in range(W+2)])
q = queue.Queue()
for i in range(H):
    tmp = list('×'+input()+'×')
    ans_tmp = []
    for j in range(W+2):
        if tmp[j] == '#':
            ans_tmp.append(0)
            q.put([j,i+1])
        elif tmp[j] == '×':
            ans_tmp.append(0)
        else:
            ans_tmp.append(10**4)
    c.append(tmp)
    ans.append(ans_tmp)

c.append(['×' for _ in range(W+2)])
ans.append([0 for _ in range(W+2)])


def bfs(q):
    while not q.empty():
        x,y = q.get()
        """
        if [x,y] == [gx,gy]:
            return ans[gy][gx]
        """
        if c[y][x-1] == '.':
            q.put([x-1,y])
            ans[y][x-1] = min(ans[y][x] + 1,ans[y][x-1])
            c[y][x-1] = '#'
        if c[y][x+1] == '.':
            q.put([x+1,y])
            ans[y][x+1] = min(ans[y][x] + 1,ans[y][x+1])
            c[y][x+1] = '#'
        if c[y-1][x] == '.':
            q.put([x,y-1])
            ans[y-1][x] = min(ans[y][x] + 1,ans[y-1][x])
            c[y-1][x] = '#'
        if c[y+1][x] == '.':
            q.put([x,y+1])
            ans[y+1][x] = min(ans[y][x] + 1,ans[y+1][x])
            c[y+1][x] = '#'

bfs(q)
max_ans = 0
for i in range(H+2):
    #print(ans[i])
    max_ans = max(max_ans,max(ans[i]))

print(max_ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy

H,W = map(int,input().split())
c =[]
c.append(['×' for _ in range(W+2)])
ans = [[0 for _ in range(W+2)]for i in range(H+2)]

for i in range(H):
    tmp = list('×'+input()+'×')
    c.append(tmp)

c.append(['×' for _ in range(W+2)])

def bfs(x,y):
    q.put([x,y])

    while not q.empty():
        x,y = q.get()

        if c[y][x-1] == '#':
            return ans[y][x] + 1
        if c[y][x+1] == '#':
            return ans[y][x] + 1
        if c[y-1][x] == '#':
            return ans[y][x] + 1
        if c[y+1][x] == '#':
            return ans[y][x] + 1

        if c[y][x-1] == '.':
            q.put([x-1,y])
            ans[y][x-1] = ans[y][x] + 1
            c[y][x-1] = '×'
        if c[y][x+1] == '.':
            q.put([x+1,y])
            ans[y][x+1] = ans[y][x] + 1
            c[y][x+1] = '×'
        if c[y-1][x] == '.':
            q.put([x,y-1])
            ans[y-1][x] = ans[y][x] + 1
            c[y-1][x] = '×'
        if c[y+1][x] == '.':
            q.put([x,y+1])
            ans[y+1][x] = ans[y][x] + 1
            c[y+1][x] = '×'

c_copy = copy.deepcopy(c)
ans_copy = copy.deepcopy(ans)
max_ans = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        if c[i][j] == '.':
            q = queue.Queue()
            max_ans = max(bfs(j,i),max_ans)
            c = copy.deepcopy(c_copy)
            ans = copy.deepcopy(ans_copy)

print(max_ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

h, w = map(int, input().split())
a = ''
for i in range(h):
    x = input()
    a += x
yet = queue.Queue()
dist = [0] * (h*w)
for i in range(h*w):
    if a[i] == '#':
        yet.put(i)
        dist[i] = 1
while not yet.empty():
    now = yet.get()
    if now >= w and a[now-w] == '.' and dist[now-w] == 0:
        yet.put(now-w)
        dist[now-w] = dist[now] + 1
    if now < w*(h-1) and a[now+w] == '.' and dist[now+w] == 0:
        yet.put(now+w)
        dist[now+w] = dist[now] + 1
    if now % w != 0 and a[now-1] == '.' and dist[now-1] == 0:
        yet.put(now-1)
        dist[now-1] = dist[now] + 1
    if now % w != w-1 and a[now+1] == '.' and dist[now+1] == 0:
        yet.put(now+1)
        dist[now+1] = dist[now] + 1
print(max(dist)-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def find_black():
    for y in range(H):
        for x in range(W):
            if canvas[y][x] == "#" and first_visit[y][x]:
                que.append((y, x))
                first_visit[y][x] = False


dir_y = [1, 0, -1, 0]
dir_x = [0, 1, 0, -1]
def paint_canvas_black():
    while len(que) > 0:
        y, x = que.popleft()
        for i in range(4):
            next_y = y + dir_y[i]
            next_x = x + dir_x[i]
            if 0 <= next_y < H and 0 <= next_x < W and canvas[next_y][next_x] == ".":
                canvas[next_y][next_x] = "#"


def has_painted():
    return canvas == BLACK_CANVAS


H, W = map(int, input().split())
sy, sx = -1, -1
canvas = []
BLACK_CANVAS = [["#"]*W for _ in range(H)]
first_visit = [[True]*W for _ in range(H)]
for y in range(H):
    canvas.append(list(input()))
    if sy == sx == -1:
        for x in range(W):
            if canvas[y][x] == "#":
                sy, sx = y, x
                break


que = deque()
count = 0
while not has_painted():
    find_black()
    paint_canvas_black()
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy

H,W = map(int,input().split())
c =[]
c.append(['#' for _ in range(W+2)])
ans = []
ans.append([0 for _ in range(W+2)])
for _ in range(H):
    tmp = list('#'+input()+'#')
    ans_tmp = []
    for i in range(W+2):
        if tmp[i] == '#':
            ans_tmp.append(0)
        else:
            ans_tmp.append(10**4)
    c.append(tmp)
    ans.append(ans_tmp)

c.append(['#' for _ in range(W+2)])
ans.append([0 for _ in range(W+2)])
q = queue.Queue()

def bfs(x,y):
    global q
    global c
    global ans
    q.put([x,y])

    while not q.empty():
        x,y = q.get()
        """
        if [x,y] == [gx,gy]:
            return ans[gy][gx]
        """
        if c[y][x-1] == '.':
            q.put([x-1,y])
            ans[y][x-1] = min(ans[y][x] + 1,ans[y][x-1])
            c[y][x-1] = '#'
        if c[y][x+1] == '.':
            q.put([x+1,y])
            ans[y][x+1] = min(ans[y][x] + 1,ans[y][x+1])
            c[y][x+1] = '#'
        if c[y-1][x] == '.':
            q.put([x,y-1])
            ans[y-1][x] = min(ans[y][x] + 1,ans[y-1][x])
            c[y-1][x] = '#'
        if c[y+1][x] == '.':
            q.put([x,y+1])
            ans[y+1][x] = min(ans[y][x] + 1,ans[y+1][x])
            c[y+1][x] = '#'

c_copy = copy.deepcopy(c)

for i in range(1,H+1):
    for j in range(1,W+1):
        if c[i][j] == '#':
            c = copy.deepcopy(c_copy)
            bfs(i,j)
max_ans = 0
for i in range(H+2):
    #print(ans[i])
    max_ans = max(max_ans,max(ans[i]))

print(max_ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
inf = 10**10
h,w = map(int,stdin.readline().rstrip().split())
li = [stdin.readline().rstrip() for _ in range(h)]
visited = [[0 for i in range(w)]for j in range(h)]
q = []
for i in range(h):
    for j in range(w):
        if li[i][j] == ".":
            continue
        q.append((i,j))
        visited[i][j] = 1
dx = [1,0,-1,0]
dy = [0,1,0,-1]
ans = -1
while q:
    qq = []
    ans += 1
    for y,x in q:
        for i,j in zip(dy,dx):
            ny,nx = i+y,j+x
            if ny < 0 or ny >= h or nx < 0 or nx >= w:
                continue
            elif li[ny][nx] == "#":
                continue
            elif visited[ny][nx] == 0:
                visited[ny][nx] = 1
                qq.append((ny,nx))
    q = qq
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int,input().split())
grid = [['']*w for i in range(h)]
que = deque([])
d = [[float('inf')]*w for i in range(h)]
for i in range(h):
    temp = list(input())
    grid[i] = temp
    for j in range(w):
        if temp[j] == '#':
            d[i][j] = 0
            que.append([i,j])
dx = [0,-1,0,1]
dy = [-1,0,1,0]
ans = 0
while que:
    [px,py] = que.popleft()
    for i in range(4):
        nx = px + dx[i]
        ny = py + dy[i]
        if 0<=nx<h and 0<=ny<w and d[nx][ny] == float('inf') and grid[nx][ny] == '.':
            d[nx][ny] = d[px][py] + 1
            ans = d[nx][ny]
            que.append([nx,ny])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int,input().split())
grid = [list(input()) for i in range(h)]
que = deque([])
d = [[float('inf')]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if grid[i][j] == '#':
            d[i][j] = 0
            que.append([i,j])
dx = [0,-1,0,1]
dy = [-1,0,1,0]
ans = 0
while que:
    [px,py] = que.popleft()
    for i in range(4):
        nx = px + dx[i]
        ny = py + dy[i]
        if 0<=nx<h and 0<=ny<w and grid[nx][ny] == '.' and d[nx][ny] == float('inf'):
            d[nx][ny] = d[px][py] + 1
            ans = d[nx][ny]
            que.append([nx,ny])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int,input().split())
grid = [list(input()) for i in range(h)]
que = deque([])
d = [[float('inf')]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if grid[i][j] == '#':
            d[i][j] = 0
            que.append([i,j])
dx = [0,-1,0,1]
dy = [-1,0,1,0]
ans = 0
while que:
    [px,py] = que.popleft()
    for i in range(4):
        nx = px + dx[i]
        ny = py + dy[i]
        if 0<=nx<h and 0<=ny<w and grid[nx][ny] == '.' and d[nx][ny] == float('inf'):
            d[nx][ny] = d[px][py] + 1
            ans = max(d[nx][ny],ans)
            que.append([nx,ny])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    import sys
    # from time import time

    # start = time()

    H, W = map(int, sys.stdin.readline().split())
    field = [list(sys.stdin.readline().rstrip()) for i in range(H)]

    # print(time() - start)

    queue = deque([])

    for h in range(H):
        for w in range(W):
            if field[h][w] == "#":
                queue.append([h, w])

    dist_from_nearest_black = [[0] * W for i in range(H)]
    direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]

    def bfs():
        while len(queue) != 0:

            h, w = queue.popleft()

            for dh, dw in direction:
                next_h = h + dh
                next_w = w + dw

                if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                    continue
                elif field[next_h][next_w] == "#":
                    continue
                else:
                    dist_from_nearest_black[next_h][next_w] = dist_from_nearest_black[h][w] + 1
                    field[next_h][next_w] = "#"
                    queue.append([next_h, next_w])

    bfs()

    ans = 0

    for d in dist_from_nearest_black:
        ans = max(ans, max(d))

    print(ans)
    # print(time() - start)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
# from time import time

# start = time()

H, W = map(int, sys.stdin.readline().split())
field = [list(sys.stdin.readline().rstrip()) for i in range(H)]

# print(time() - start)

queue = deque([])

for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            queue.append([h, w])

dist_from_nearest_black = [[0] * W for i in range(H)]
direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]


def bfs():
    while len(queue) != 0:

        h, w = queue.popleft()

        for dh, dw in direction:
            next_h = h + dh
            next_w = w + dw

            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                continue
            elif field[next_h][next_w] == "#":
                continue
            else:
                dist_from_nearest_black[next_h][next_w] = dist_from_nearest_black[h][w] + 1
                field[next_h][next_w] = "#"
                queue.append([next_h, next_w])


bfs()

ans = 0

for d in dist_from_nearest_black:
    ans = max(ans, max(d))

print(ans)
# print(time() - start)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

H, W = map(int, sys.stdin.readline().split())
field = [list(sys.stdin.readline().rstrip()) for i in range(H)]

queue = deque([])

for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            queue.append([h, w])

dist_from_nearest_black = [[0] * W for i in range(H)]
direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]


def bfs():
    while len(queue) != 0:

        h, w = queue.popleft()

        field[h][w] = "#"

        for dh, dw in direction:
            next_h = h + dh
            next_w = w + dw

            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                continue
            elif field[next_h][next_w] == "#":
                continue
            else:
                dist_from_nearest_black[next_h][next_w] = dist_from_nearest_black[h][w] + 1
                queue.append([next_h, next_w])


bfs()

ans = 0

for d in dist_from_nearest_black:
    ans = max(ans, max(d))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10 ** 9)

H, W = map(int, sys.stdin.readline().split())
field = [list(sys.stdin.readline().rstrip()) for i in range(H)]

dist_from_nearest_black = [[10 ** 9] * W for i in range(H)]
seen = [[0] * W for i in range(H)]
direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]


def bfs(h, w):
    if field[h][w] != "#":
        return

    queue = deque([])
    queue.append([h, w])
    dist_from_nearest_black[h][w] = 0

    while len(queue) != 0:

        h, w = queue.popleft()

        if seen[h][w] == 1:
            continue

        seen[h][w] = 1

        for dh, dw in direction:
            next_h = h + dh
            next_w = w + dw

            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                continue
            else:
                dist_from_nearest_black[next_h][next_w] = min(
                    dist_from_nearest_black[h][w] + 1, dist_from_nearest_black[next_h][next_w])
                queue.append([next_h, next_w])


for h in range(H):
    for w in range(W):
        seen = [[0] * W for i in range(H)]
        bfs(h, w)

ans = 0

for d in dist_from_nearest_black:
    # print(d)
    ans = max(ans, max(d))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from sys import setrecursionlimit

setrecursionlimit(10 ** 9)

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

dist_from_nearest_black = [[10 ** 9] * W for i in range(H)]
seen = [[0] * W for i in range(H)]
direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]


def bfs(h, w):
    if field[h][w] != "#":
        return

    queue = deque([])
    queue.append([h, w])
    dist_from_nearest_black[h][w] = 0

    while len(queue) != 0:

        h, w = queue.popleft()

        if seen[h][w] == 1:
            continue

        seen[h][w] = 1

        for dh, dw in direction:
            next_h = h + dh
            next_w = w + dw

            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                continue
            else:
                dist_from_nearest_black[next_h][next_w] = min(
                    dist_from_nearest_black[h][w] + 1, dist_from_nearest_black[next_h][next_w])
                queue.append([next_h, next_w])


for h in range(H):
    for w in range(W):
        seen = [[0] * W for i in range(H)]
        bfs(h, w)

ans = 0

for d in dist_from_nearest_black:
    # print(d)
    ans = max(ans, max(d))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs(A,H,W,D):
    que = deque(D)
    cnt = 0
    d = [-1,1]
    tmp = set()
    flag = 0
    while que:
        u = que.popleft()
        
        y,x = u
        for k in range(2):
            s = y + d[k]
            t = x + d[k]
            if 0 <= s < H:
                if A[s][x] == '.':
                    A[s][x] = '#'
                    tmp.add((s,x))
                    flag = 1
              
            if 0 <= t < W:
                if A[y][t] == '.':
                    A[y][t] = '#'
                    tmp.add((y,t))
                    flag = 1

            
        if not que:
            que = deque(tmp) 
            tmp = set()
            if flag:
                cnt += 1
            flag = 0
    return cnt

def main():
    H,W = map(int,input().split(" "))
    A = []
    D = []
    D_append = D.append
    for i in range(H):
        tmp = []
        for j,s in enumerate(input()):
            tmp.append(s)
            if s == '#':
                D_append((i,j))
        A.append(tmp)

    ans = bfs(A,H,W,D)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs(A,H,W,D):
    que = deque(D)
    cnt = 0
    d = [-1,1]
    tmp = deque([])
    flag = 0
    while que:
        u = que.popleft()
        y,x = u
        for k in range(2):
            s = y + d[k]
            t = x + d[k]
            if 0 <= s < H:
                if A[s][x] == '.':
                    A[s][x] = '#'
                    tmp.append((s,x))
                    flag = 1
            if 0 <= t < W:
                if A[y][t] == '.':
                    A[y][t] = '#'
                    tmp.append((y,t))
                    flag = 1
            
        if not que:
            que = tmp 
            tmp = deque([])
            if flag:
                cnt += 1
            flag = 0

    return cnt

def main():
    H,W = map(int,input().split(" "))
    A = []
    D = []
    D_append = D.append
    for i in range(H):
        tmp = []
        for j,s in enumerate(input()):
            tmp.append(s)
            if s == '#':
                D_append((i,j))
        A.append(tmp)

    ans = bfs(A,H,W,D)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs(A,H,W):
    que = deque([])
    cnt = 0
    for i in range(H):
        for j,a in enumerate(A[i]):
            if a == '#':
                que.append((i,j))

    d = [-1,1]
    tmp = deque([])
    flag = 0
    while que:
        u = que.popleft()
        y,x = u
        for k in range(2):
            s = y + d[k]
            t = x + d[k]
            if 0 <= s < H:
                if A[s][x] == '.':
                    A[s][x] = '#'
                    tmp.append((s,x))
                    flag = 1
            if 0 <= t < W:
                if A[y][t] == '.':
                    A[y][t] = '#'
                    tmp.append((y,t))
                    flag = 1
            
        if not que:
            que = tmp 
            tmp = deque([])
            if flag:
                cnt += 1
            flag = 0

    return cnt

def main():
    H,W = map(int,input().split(" "))
    A = [[s for s in input()] for _ in range(H)]
    ans = bfs(A,H,W)
    print(ans)


if __name__ == "__main__":
    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)]
move = [(1,0), (0,1), (-1,0), (0,-1)]

queue = deque([(row, col, 0) for row in range(h) for col in range(w) if a[row][col] == "#"])
visited = [[-1]*w for _ in range(h)]

max_dist = 0
while queue:
    row, col, dist = queue.popleft()
    if visited[row][col] == -1:
        visited[row][col] = 0
    if max_dist < dist:
        max_dist = dist
    for drow, dcol in move:
        if row+drow>=0 and row+drow<h and col+dcol>=0 and col+dcol<w and visited[row+drow][col+dcol] == -1:
            visited[row+drow][col+dcol] == dist + 1
            queue.append((row+drow, col+dcol, dist+1))


print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

queue = deque([(row, col, 0) for row in range(h) for col in range(w) if a[row][col] == "#"])
visited = [[-1]*w for _ in range(h)]

max_dist = 0
while queue:
    row, col, dist = queue.popleft()
    if visited[row][col] == -1:
        visited[row][col] = 0
    if max_dist < dist:
        max_dist = dist
    for drow, dcol in move:
        if a[row+drow:row+drow+1] and a[row+drow][col+dcol:col+dcol+1] and visited[row+drow][col+dcol] == -1 and a[row+drow][col+dcol] == ".":
            visited[row+drow][col+dcol] == dist + 1
            queue.append((row+drow, col+dcol, dist+1))


print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

queue = deque([(row, col, 0) for row in range(h) for col in range(w) if a[row][col] == "#"])
visited = [[-1] * w for _ in range(h)]

while queue:
    row, col, dist = queue.popleft()
    if visited[row][col] == -1:
        visited[row][col] = 0
    for drow, dcol in move:
        if a[row+drow:row+drow+1] and a[row+drow][col+dcol:col+dcol+1] and visited[row+drow][col+dcol] == -1 and a[row+drow][col+dcol] == ".":
            visited[row+drow][col+dcol] = dist + 1
            queue.append((row+drow, col+dcol, dist+1))

result = 0
for row in visited:
    row_max = max(row)
    if row_max > result:
        result = row_max

print(result)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

queue = deque()
visited = [[-1] * w for _ in range(h)]
for row in range(h):
    for col in range(w):
        if a[row][col] == "#":
            visited[row][col] = 0
            queue.append((row, col, 0))

while queue:
    row, col, dist = queue.popleft()
    for drow, dcol in move:
        if a[row+drow:row+drow+1] and a[row+drow][col+dcol:col+dcol+1] and visited[row+drow][col+dcol] == -1 and a[row+drow][col+dcol] == ".":
            visited[row+drow][col+dcol] = dist + 1
            queue.append((row+drow, col+dcol, dist+1))

result = 0
for row in visited:
    row_max = max(row)
    if row_max > result:
        result = row_max

print(result)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W = map(int, input().split())
G = [list(input()) for _ in range(H)]
que = []
visited = [[-1]*W for _ in range(H)]
direction = [[1,0], [-1,0], [0,1], [0,-1]]

for i in range(H):
  for j in range(W):
    item = G[i][j]
    if item == '#':
      que.append((i,j))
      visited[i][j] = 0
    else:
      continue
while que:
  h,w = que.pop(0)
  for dh, dw in direction:
    if h+dh<0 or H<=h+dh or w+dw<0 or W<=w+dw:
      continue
    elif visited[h+dh][w+dw] != -1:
      continue
    que.append((h+dh,w+dw))
    visited[h+dh][w+dw] = visited[h][w] +1
print(np.max(visited))

Submission status: Time Limit Exceeded

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

que = deque()
seen = [[-1]*W for _ in range(H)]
max = 0



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

while que:
    #print(que)
    y, x = que.popleft()
    for dy, dx in ([0,1],[0,-1],[1,0],[-1,0]):
        ny = y + dy
        nx = x + dx
        if 0<=ny<H and 0<=nx<W and seen[ny][nx]==-1:
            seen[ny][nx] = seen[y][x] + 1
            que.append([ny,nx])
            if max < seen[ny][nx]:
                max = seen[ny][nx]

print(max)