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:
def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    h, w = read_int(2)
    a = []
    for y in range(h):
        a.append(list(read_line(w)))
    return a


def read_int(n):
    return list(map(int, read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    white_tile = '.'
    black_tile = '#'

    w, h = get_area(a)
    invalid = w * h
    memo = [[invalid for x in range(w)] for y in range(h)]
    black_tiles = collect_tiles(a, w, h, black_tile)
    queue = []

    next_steps = [[1, 0], [-1, 0], [0, 1], [0, -1]]

    for bx, by in black_tiles:
        queue.append([bx, by, 0])

    while queue:
        x, y, d = queue.pop(0)
        if not (0 <= x < w and 0 <= y < h and memo[y][x] > d):
            continue

        memo[y][x] = d
        for dx, dy in next_steps:
            queue.append([x + dx, y + dy, d + 1])

    maximum_count = 0
    for y in range(h):
        maximum_count = max(maximum_count, max(memo[y]))

    return maximum_count


def get_area(a):
    w = len(a[0])
    h = len(a)
    return w, h


def collect_tiles(a, w, h, mark):
    tiles = []
    for y in range(h):
        for x in range(w):
            if a[y][x] == mark:
                tiles.append([x, y])
    return tiles


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


H, W = map(int, input().split())
m = [[0 if c == '#' else 3000 for c in input()] for _ in range(H)]
queue = deque()
for i, r in enumerate(m):
    for j, n in enumerate(r):
        if n == 0:
            queue.append((i, j))
while queue:
    p, q = queue.popleft()
    if 0 < p and m[p - 1][q] > m[p][q] + 1:
        m[p - 1][q] = m[p][q] + 1
        queue.append((p - 1, q))
    if 0 < q and m[p][q - 1] > m[p][q] + 1:
        m[p][q - 1] = m[p][q] + 1
        queue.append((p, q - 1))
    if p < H - 1 and m[p + 1][q] > m[p][q] + 1:
        m[p + 1][q] = m[p][q] + 1
        queue.append((p + 1, q))
    if q < W - 1 and m[p][q + 1] > m[p][q] + 1:
        m[p][q + 1] = m[p][q] + 1
        queue.append((p, q + 1))
_max = 0
for r in m:
    _max = max(_max, max(r))
print(_max)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


H, W = map(int, input().split())
A = [input() for _ in range(H)]
m = [[3000] * W for _ in range(H)]
for i, s in enumerate(A):
    for j, c in enumerate(s):
        if c == '#':
            m[i][j] = 0


def bfs(i, j):
    queue = deque()
    queue.append((i, j))
    while queue:
        p, q = queue.popleft()
        if 0 < p and m[p - 1][q] > m[p][q] + 1:
            m[p - 1][q] = m[p][q] + 1
            queue.append((p - 1, q))
        if 0 < q and m[p][q - 1] > m[p][q] + 1:
            m[p][q - 1] = m[p][q] + 1
            queue.append((p, q - 1))
        if p < H - 1 and m[p + 1][q] > m[p][q] + 1:
            m[p + 1][q] = m[p][q] + 1
            queue.append((p + 1, q))
        if q < W - 1 and m[p][q + 1] > m[p][q] + 1:
            m[p][q + 1] = m[p][q] + 1
            queue.append((p, q + 1))


for i, r in enumerate(m):
    for j, n in enumerate(r):
        if n == 0:
            bfs(i, j)
_max = 0
for r in m:
    _max = max(_max, max(r))
print(_max)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


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


def bfs(i, j):
    queue = deque()
    queue.append((i, j))
    while queue:
        p, q = queue.popleft()
        if 0 < p and A[p - 1][q] == '.' and m[p - 1][q] > m[p][q] + 1:
            m[p - 1][q] = m[p][q] + 1
            queue.append((p - 1, q))
        if 0 < q and A[p][q - 1] == '.' and m[p][q - 1] > m[p][q] + 1:
            m[p][q - 1] = m[p][q] + 1
            queue.append((p, q - 1))
        if p < H - 1 and A[p + 1][q] == '.' and m[p + 1][q] > m[p][q] + 1:
            m[p + 1][q] = m[p][q] + 1
            queue.append((p + 1, q))
        if q < W - 1 and A[p][q + 1] == '.' and m[p][q + 1] > m[p][q] + 1:
            m[p][q + 1] = m[p][q] + 1
            queue.append((p, q + 1))


for i, s in enumerate(A):
    for j, c in enumerate(s):
        if c == '#':
            m[i][j] = 0
            bfs(i, j)
_max = 0
for r in m:
    _max = max(_max, max(r))
print(_max)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


H, W = map(int, input().split())
A = [input() for _ in range(H)]
m = [[float('inf')] * W for _ in range(H)]


def bfs(i, j):
    queue = deque()
    queue.append((i, j))
    while queue:
        p, q = queue.popleft()
        if 0 < p and A[p - 1][q] == '.' and m[p - 1][q] > m[p][q] + 1:
            m[p - 1][q] = m[p][q] + 1
            queue.append((p - 1, q))
        if 0 < q and A[p][q - 1] == '.' and m[p][q - 1] > m[p][q] + 1:
            m[p][q - 1] = m[p][q] + 1
            queue.append((p, q - 1))
        if p < H - 1 and A[p + 1][q] == '.' and m[p + 1][q] > m[p][q] + 1:
            m[p + 1][q] = m[p][q] + 1
            queue.append((p + 1, q))
        if q < W - 1 and A[p][q + 1] == '.' and m[p][q + 1] > m[p][q] + 1:
            m[p][q + 1] = m[p][q] + 1
            queue.append((p, q + 1))


for i, s in enumerate(A):
    for j, c in enumerate(s):
        if c == '#':
            m[i][j] = 0
            bfs(i, j)
_max = 0
for r in m:
    _max = max(_max, max(r))
print(_max)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(grid, costs, queue, wall, res):
    ans = 0
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    while res:
        y,x = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if grid[y_][x_] == wall:
                continue
            queue.append([y_,x_])
            grid[y_][x_] = wall
            costs[y_][x_] = costs[y][x] + 1
            ans = max(ans, costs[y_][x_])
            res -= 1
    return ans

import sys
input = sys.stdin.readline
H,W = map(int, input().split())
wall = '#'
queue = deque([])
edges = [wall for _ in range(W+2)]
grid = [edges]
costs = [[0] * (W+2)]

for i in range(1,H+1):
    S = [wall]+list(input().strip())+[wall]
    for j in range(1,W+1):
        if S[j] == wall:
            queue.append([i,j])
    grid.append(S)
    costs.append([0] * (W+2))
grid.append(edges)
print(bfs(grid, costs, queue, wall, H*W - len(queue)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(grid, costs, queue, wall, res):
    ans = 0
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    while res:
        y,x = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if grid[y_][x_] == wall:
                continue
            queue.append([y_,x_])
            grid[y_][x_] = wall
            costs[y_][x_] = costs[y][x] + 1
            ans = max(ans, costs[y_][x_])
            res -= 1
    return ans

import sys
input = sys.stdin.readline
H,W = map(int, input().split())
wall = '#'
queue = deque([])
edges = [wall for _ in range(W+2)]
grid = [edges]
costs = [[0 for _ in range(W+2)]]

for i in range(1,H+1):
    S = [wall]+list(input().strip())+[wall]
    for j in range(1,W+1):
        if S[j] == wall:
            queue.append([i,j])
    grid.append(S)
    costs.append([0 for _ in range(W+2)])
grid.append(edges)
print(bfs(grid, costs, queue, wall, H*W - len(queue)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(grid, costs, queue, wall):
    ans = 0
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    while queue:
        y,x = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if grid[y_][x_] == wall:
                continue
            queue.append([y_,x_])
            grid[y_][x_] = wall
            costs[y_][x_] = costs[y][x] + 1
            ans = max(ans, costs[y_][x_])
    return ans

import sys
input = sys.stdin.readline
H,W = map(int, input().split())
wall = '#'
queue = deque([])
edges = [wall for _ in range(W+2)]
grid = [edges]
costs = [[0 for _ in range(W+2)]]

for i in range(1,H+1):
    S = [wall]+list(input().strip())+[wall]
    for j in range(1,W+1):
        if S[j] == wall:
            queue.append([i,j])
    grid.append(S)
    costs.append([0 for _ in range(W+2)])
grid.append(edges)
print(bfs(grid, costs, queue, wall))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(grid, costs, queue, wall):
    ans = 0
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    while queue:
        y,x = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if grid[y_][x_] == wall:
                continue
            queue.append([y_,x_])
            grid[y_][x_] = wall
            costs[y_][x_] = costs[y][x] + 1
            ans = max(ans, costs[y_][x_])
    return ans

H,W = map(int, input().split())
wall = '#'
queue = deque([])
edges = [wall for _ in range(W+2)]
grid = [edges]
costs = [[0 for _ in range(W+2)]]

for i in range(1,H+1):
    S = [wall]+list(input().strip())+[wall]
    for j in range(1,W+1):
        if S[j] == wall:
            queue.append([i,j])
    grid.append(S)
    costs.append([0 for _ in range(W+2)])
grid.append(edges)
print(bfs(grid, costs, queue, wall))

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)]

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

ans = 0
while q:
    nq = deque()
    while q:
        h, w = q.popleft()
        if h > 0 and A[h - 1][w] == '.':
            A[h - 1][w] = '#'
            nq.append((h - 1, w))
        if h < H - 1 and A[h + 1][w] == '.':
            A[h + 1][w] = '#'
            nq.append((h + 1, w))
        if w > 0 and A[h][w - 1] == '.':
            A[h][w - 1] = '#'
            nq.append((h, w - 1))
        if w < W - 1 and A[h][w + 1] == '.':
            A[h][w + 1] = '#'
            nq.append((h, w + 1))
    if not nq:
        break
    q = nq
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
grid=[]
for _ in range(h):
    grid.append(list(input()))
flag=True
counter=0
while flag:
    flag=False
    new_grid=[["."]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if grid[i][j]==".":
                new_grid[i][j]=="."
                flag=True
            else:
                new_grid[i][j]="#"
                if i!=0:
                    new_grid[i-1][j]="#"
                if i!=h-1:
                    new_grid[i+1][j]="#"
                if j!=0:
                    new_grid[i][j-1]="#"
                if j!=w-1:
                    new_grid[i][j+1]="#"
    counter+=1
    grid=new_grid
print(counter-1)

Submission status: Time Limit Exceeded

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

def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]

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

    # スタート地点をqueueに追加
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    nque = deque()
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))

#            for j in range(4):
#                ny = y + dy[j]
#                nx = x + dx[j]
#                if nx < w and nx >= 0 and ny < h and ny >= 0 and not a[ny][nx]:
#                    a[ny][nx] = True
#                    nque.append((ny, nx))
        
        if nque:
            que = copy.copy(nque)
        else:
            break

    print(count - 1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]
    
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    
    # スタート地点をqueueに追加
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])
    
    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            for j in range(4):
                ny = y + dy[j]
                nx = x + dx[j]
                if nx < w and nx >= 0 and ny < h and ny >= 0 and not a[ny][nx]:
                    a[ny][nx] = True
                    nque.append((ny, nx))
        if nque:
            que = copy.copy(nque)
        else:
            break
    
    print(count - 1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

# スタート地点をqueueに追加
que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

count = 0
while True:
    count += 1
    nque = deque()
    while que:
        y, x = que.popleft()
        for j in range(4):
            ny = y + dy[j]
            nx = x + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and not a[ny][nx]:
                a[ny][nx] = True
                nque.append((ny, nx))
    if nque:
        que = copy.copy(nque)
    else:
        break

print(count - 1)

Submission status: Time Limit Exceeded

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

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

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

# スタート地点をqueueに追加
que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

loop = len(que)
count = 0
add = 0
while True:
    count += 1
    loop += add
    add = 0
    nque = deque()
    while que:
        y, x = que.popleft()
        add -= 1
        for j in range(4):
            ny = y + dy[j]
            nx = x + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and not a[ny][nx]:
                a[ny][nx] = True
                nque.append((ny, nx))
                add += 1
    if nque:
        que = copy.copy(nque)
    else:
        break

print(count - 1)

Submission status: Time Limit Exceeded

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

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

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

# スタート地点をqueueに追加
que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

loop = len(que)
count = 0
add = 0
while True:
    count += 1
    loop += add
    add = 0
    for i in range(loop):
        y, x = que.popleft()
        add -= 1
        for j in range(4):
            ny = y + dy[j]
            nx = x + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and not a[ny][nx]:
                a[ny][nx] = True
                que.append((ny, nx))
                add += 1
    if not que:
        break

print(count - 1)

Submission status: Time Limit Exceeded

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

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

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


# スタート地点をqueueに追加
que = deque([(i,j) for i in range(h) for j in range(w) if a[i][j]])

loop = len(que)
count = 0

add = 0
while True:
    count += 1
    loop += add
    add = 0
    for i in range(loop):
        p = que.popleft()
        add -= 1
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and not a[ny][nx]:
                a[ny][nx] = True
                que.append((ny, nx))
                add += 1
    if not que:
        break

print(count - 1)

Submission status: Time Limit Exceeded

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

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

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

que = deque()

white = h * w

loop = 0
# スタート地点をqueueに追加
for i in range(h):
    for j in range(w):
        if a[i][j]:
            que.append([i, j])
            loop += 1
            white -= 1

count = 0

add = 0
while 1:
    if white == 0:
        break
    count += 1
    loop += add
    add = 0
    for i in range(loop):
        p = que.popleft()
        add -= 1
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and not a[ny][nx]:
                a[ny][nx] = True
                white -= 1
                que.append([ny, nx])
                add += 1


print(count)

Submission status: Time Limit Exceeded

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

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

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

que = deque()

white = h * w

# スタート地点をqueueに追加
for i in range(h):
    for j in range(w):
        if a[i][j]:
            que.append([i, j])
            white -= 1

count = 0
loop = len(que)
add = 0
while 1:
    if white == 0:
        break
    count += 1
    loop += add
    add = 0
    for i in range(loop):
        p = que.popleft()
        add -= 1
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and not a[ny][nx]:
                a[ny][nx] = True
                white -= 1
                que.append([ny, nx])
                add += 1


print(count)

Submission status: Time Limit Exceeded

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

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

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

que = deque()

white = h * w

# スタート地点をqueueに追加
for i in range(h):
    for j in range(w):
        if a[i][j]:
            que.append([i, j])
            white -= 1

count = 0
while 1:
    if white == 0:
        break
    count += 1
    loop = len(que)
    for i in range(loop):
        p = que.popleft()
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and not a[ny][nx]:
                a[ny][nx] = True
                white -= 1
                que.append([ny, nx])


print(count)

Submission status: Time Limit Exceeded

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

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

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

que = deque()

white = h * w

# スタート地点をqueueに追加
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            que.append([i, j])
            white -= 1

count = 0
while 1:
    if white == 0:
        break
    count += 1
    loop = len(que)
    for i in range(loop):
        p = que.popleft()
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and a[ny][nx] == ".":
                a[ny][nx] = "#"
                white -= 1
                que.append([ny, nx])


print(count)

Submission status: Time Limit Exceeded

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

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

que = deque()

white = h * w

# スタート地点をqueueに追加
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            que.append([i, j])
            white -= 1

count = 0
while 1:
    if white == 0:
        break
    count += 1
    loop = len(que)
    for i in range(loop):
        p = que.popleft()
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and a[ny][nx] == ".":
                a[ny][nx] = "#"
                white -= 1
                que.append([ny, nx])


print(count)

Submission status: Time Limit Exceeded

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

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

que = queue.Queue()

# スタート地点をqueueに追加
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            que.put([i,j])

count = 0
while not que.empty():
    count += 1
    loop = que.qsize()
    for i in range(loop):
        p = que.get()
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and a[ny][nx] == ".":
                a[ny][nx] = "x"
                que.put([ny, nx])


print(count - 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = list(map(int, input().split()))
field = [input() for _ in range(H)]
dist = [[5000] * W for _ in range(H)]

def bfs():
  q = deque()
  for y in range(H):
    for x in range(W):
      if field[y][x] == '#':
        q.append((y, x))
        dist[y][x] = 0
  while len(q) > 0:
    y, x = q.popleft()
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
      ny, nx = y + dy, x + dx
      if ny < 0 or ny >= H or nx < 0 or nx >= W:
        continue
      if field[ny][nx] == '#':
        continue
      if dist[ny][nx] < dist[y][x] + 1:
        continue
      dist[ny][nx] = dist[y][x] + 1
      q.append((ny, nx))
      
bfs()
print(max([max(d) for d in dist]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

def main():
  H, W = list(map(int, input().split()))
  field = [[i=='#' for i in input()] for _ in range(H)]
  count = 0
  q = deque([(i, j) for i in range(H) for j in range(W) if field[i][j]])
  while True:
    nq = deque()
    while q:
      y, x = q.popleft()
      for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if 0<=ny<H and 0<=nx<W and not field[ny][nx]:
          field[ny][nx] = True
          nq.append((ny, nx))
    if nq:
      q = copy.copy(nq)
    else:
      break
    count += 1
  print(count)
      
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

def bfs():
  H, W = list(map(int, input().split()))
  field = [[i=='#' for i in input()] for _ in range(H)]
  count = 0
  q = deque([(i, j) for i in range(H) for j in range(W) if field[i][j]])
  while True:
    nq = deque()
    while q:
      y, x = q.popleft()
      for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if 0<=ny<H and 0<=nx<W and not field[ny][nx]:
          field[ny][nx] = True
          nq.append((ny, nx))
    if nq:
      q = copy.copy(nq)
    else:
      break
    count += 1
  print(count)
      
bfs()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs():
  H, W = list(map(int, input().split()))
  field = [[i=='#' for i in input()] for _ in range(H)]
  count = 0
  q = deque([(i, j) for i in range(H) for j in range(W) if field[i][j]])
  while True:
    nq = deque()
    while q:
      y, x = q.popleft()
      for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if 0<=ny<H and 0<=nx<W and not field[ny][nx]:
          field[ny][nx] = True
          nq.append((ny, nx))
    if nq:
      q = nq
    else:
      break
    count += 1
  print(count)
      
bfs()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

H, W = list(map(int, input().split()))
field = [[i=='#' for i in input()] for _ in range(H)]
count = 0

def bfs():
  global count
  q = deque([(i, j) for i in range(H) for j in range(W) if field[i][j]])
  while True:
    nq = deque()
    while len(q) > 0:
      y, x = q.popleft()
      for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if 0<=ny<H and 0<=nx<W and not field[ny][nx]:
          field[ny][nx] = True
          nq.append((ny, nx))
    if len(nq) > 0:
      q = nq
    else:
      break
    count += 1
      
bfs()
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

H, W = list(map(int, input().split()))
field = [[i=='#' for i in input()] for _ in range(H)]
count = 0

def bfs():
  global count
  q = deque([(i, j) for i in range(H) for j in range(W) if field[i][j]])
  while True:
    nq = deque()
    while len(q) > 0:
      y, x = q.popleft()
      for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
          continue
        if field[ny][nx]:
          continue
        field[ny][nx] = True
        nq.append((ny, nx))
    if len(nq) > 0:
      q = nq
    else:
      break
    count += 1
      
bfs()
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

H, W = list(map(int, input().split()))
field = [[i=='#' for i in input()] for _ in range(H)]
count = 0

def bfs():
  global count
  q = deque()
  for y in range(H):
    for x in range(W):
      if field[y][x]:
        q.append((y, x))
  while True:
    nq = deque()
    while len(q) > 0:
      y, x = q.popleft()
      for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
          continue
        if field[ny][nx]:
          continue
        field[ny][nx] = True
        nq.append((ny, nx))
    if len(nq) > 0:
      q = nq
    else:
      break
    count += 1
      
bfs()
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

H, W = list(map(int, input().split()))
field = [input() for _ in range(H)]
dist = [[5000] * W for _ in range(H)]

def bfs():
  q = deque()
  for y in range(H):
    for x in range(W):
      if field[y][x] == '#':
        q.append((y, x))
        dist[y][x] = 0
  while len(q) > 0:
    y, x = q.popleft()
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
      ny, nx = y + dy, x + dx
      if ny < 0 or ny >= H or nx < 0 or nx >= W:
        continue
      if field[ny][nx] == '#':
        continue
      if dist[ny][nx] <= dist[y][x] + 1:
        continue
      dist[ny][nx] = dist[y][x] + 1
      q.append((ny, nx))
      
bfs()
print(np.max(np.asarray(dist).flatten()))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

H, W = list(map(int, input().split()))
field = [input() for _ in range(H)]
dist = [[5000] * W for _ in range(H)]

def bfs():
  q = deque()
  for y in range(H):
    for x in range(W):
      if field[y][x] == '#':
        q.append((y, x))
        dist[y][x] = 0
  while len(q) > 0:
    y, x = q.popleft()
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
      ny, nx = y + dy, x + dx
      if ny < 0 or ny >= H or nx < 0 or nx >= W:
        continue
      if field[ny][nx] == '#':
        continue
      if dist[ny][nx] < dist[y][x] + 1:
        continue
      dist[ny][nx] = dist[y][x] + 1
      q.append((ny, nx))
      
bfs()
print(np.max(np.asarray(dist).flatten()))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

H, W = list(map(int, input().split()))
field = [input() for _ in range(H)]
dist = [[5000] * W for _ in range(H)]

def bfs(sy, sx):
  q = deque()
  q.append((sy, sx))
  dist[sy][sx] = 0
  while len(q) > 0:
    y, x = q.popleft()
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
      ny, nx = y + dy, x + dx
      if ny < 0 or ny >= H or nx < 0 or nx >= W:
        continue
      if field[ny][nx] == '#':
        continue
      if dist[ny][nx] < dist[y][x] + 1:
        continue
      dist[ny][nx] = dist[y][x] + 1
      q.append((ny, nx))
      
for y in range(H):
  for x in range(W):
    if field[y][x] == '#':
      bfs(y, x)
print(np.max(np.asarray(dist).flatten()))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(grid, queue, wall, vis, hw):
    ans = 0
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    while queue and vis < hw:
        cnt,y,x = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if grid[y_][x_] == wall:
                continue
            queue.append([cnt+1,y_,x_])
            grid[y_][x_] = wall
            ans = max(ans, cnt+1)
            vis += 1
    return ans

H,W = map(int, input().split())
wall = '#'
queue = deque([])
edges = [wall for i in range(W+2)]
grid = [edges]
cnt = 0

for i in range(1,H+1):
    S = [wall]+list(input().strip())+[wall]
    for j in range(1,W+1):
        if S[j] == wall:
            queue.append([0,i,j])
            cnt += 1
    grid.append(S)
grid.append(edges)
print(bfs(grid, queue, wall, cnt, H*W))