Problem:


Score : 300 points

Problem Statement

You are given a grid of squares with H horizontal rows and W vertical columns, where each square is painted white or black.
HW characters from A_{11} to A_{HW} represent the colors of the squares.
A_{ij} is # if the square at the i-th row from the top and the j-th column from the left is black, and A_{ij} is . if that square is white.

We will repeatedly perform the following operation until all the squares are black:

Every white square that shares a side with a black square, becomes black.

Find the number of operations that will be performed.
The initial grid has at least one black square.

Constraints

1 \leq H,W \leq 1000

A_{ij} is # or ..

The given grid has at least one black square.

Input

Input is given from Standard Input in the following format:

H W
A_{11}A_{12}...A_{1W}
:
A_{H1}A_{H2}...A_{HW}

Output

Print the number of operations that will be performed.

Sample Input 1

3 3
...
.#.
...

Sample Output 1

2

After one operation, all but the corners of the grid will be black. After one more operation, all the squares will be black.

Sample Input 2

6 6
..#..#
......
#..#..
......
.#....
....#.

Sample Output 2

3



Sample input:
3 3
...
.#.
...


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
graph = [[2000 for i in range(w)] for j in range(h)]
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False

#graph => そこまでの距離を保存した二次元配列　grid=>与えられた迷路
def bfs(que):
    finished = set()
    while que:
        x , y, cost = que.popleft()
        if (x,y) not in finished and graph[y][x] > cost:
            finished.add((x,y))
            graph[y][x] = cost
            if check(y,x+1):
                que.append([x+1,y,cost+1])
            if check(y+1,x):
                que.append([x, y+1, cost+1])
            if check(y,x-1):
                que.append([x-1,y,cost+1])
            if check(y-1,x):
                que.append([x,y-1,cost+1])
for i in range(h):
    grid.append(list(input()))
que = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            que.append((j,i,0))
bfs(que)
ans = 0
for i in range(h):
    ans = max(ans, max(graph[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
graph = [[2000 for i in range(w)] for j in range(h)]
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False

#graph => そこまでの距離を保存した二次元配列　grid=>与えられた迷路
def bfs(que):
    finished = set()
    while que:
        x , y, cost = que.popleft()
        if (grid[y][x] == '#' and cost != 0):
            continue
        if (x,y) not in finished and graph[y][x] > cost:
            finished.add((x,y))
            graph[y][x] = cost
            if check(y,x+1):
                que.append([x+1,y,cost+1])
            if check(y+1,x):
                que.append([x, y+1, cost+1])
            if check(y,x-1):
                que.append([x-1,y,cost+1])
            if check(y-1,x):
                que.append([x,y-1,cost+1])
for i in range(h):
    grid.append(list(input()))
que = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            que.append((j,i,0))
bfs(que)
ans = 0
for i in range(h):
    ans = max(ans, max(graph[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
graph = [[2000 for i in range(w)] for j in range(h)]
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False

#graph => そこまでの距離を保存した二次元配列　grid=>与えられた迷路
def bfs(que):
    finished = set()
    while que:
        x , y, cost = que.popleft()
        if (grid[y][x] == '#' and cost != 0):
            continue
        if (x,y) not in finished and graph[y][x] > cost:
            finished.add((x,y))
            graph[y][x] = cost
            if check(y,x+1):
                que.append([x+1,y,cost+1])
            if check(y+1,x):
                que.append([x, y+1, cost+1])
            if check(y,x-1):
                que.append([x-1,y,cost+1])
            if check(y-1,x):
                que.append([x,y-1,cost+1])
for i in range(h):
    grid.append(list(input()))
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            que = deque([(j,i,0)])
            bfs(que)
ans = 0
for i in range(h):
    ans = max(ans, max(graph[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
grid = []
graph = [[2000 for i in range(w)] for j in range(h)]
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False

#graph => そこまでの距離を保存した二次元配列　grid=>与えられた迷路
def bfs(que):
    finished = set()
    while que:
        x , y, cost = que.popleft()
        if (grid[y][x] == '#' and cost != 0):
            continue
        if (x,y) not in finished and graph[y][x] > cost:
            finished.add((x,y))
            graph[y][x] = cost
            if check(y,x+1):
                que.append([x+1,y,cost+1])
            if check(y+1,x):
                que.append([x, y+1, cost+1])
            if check(y,x-1):
                que.append([x-1,y,cost+1])
            if check(y-1,x):
                que.append([x,y-1,cost+1])
for i in range(h):
    grid.append(list(input()))
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            que = deque([(j,i,0)])
            bfs(que)
ans = 0
for i in range(h):
    ans = max(ans, max(graph[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
grid = []
graph = [[10000 for i in range(w)] for j in range(h)]
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False

#graph => そこまでの距離を保存した二次元配列　grid=>与えられた迷路
def bfs(que):
    finished = set()
    while que:
        x , y, cost = que.popleft()
        if not check(y,x):
            continue
        if (grid[y][x] == '#' and cost != 0):
            continue
        if (x,y) not in finished and graph[y][x] > cost:
            finished.add((x,y))
            graph[y][x] = cost
            que.append([x+1,y,cost+1])
            que.append([x, y+1, cost+1])
            que.append([x-1,y,cost+1])
            que.append([x,y-1,cost+1])
for i in range(h):
    grid.append(list(input()))
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            que = deque([(j,i,0)])
            bfs(que)
ans = 0
for i in range(h):
    ans = max(ans, max(graph[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

if __name__ == '__main__':
    h, w = map(int, input().split())
    field = [list(input()) for i in range(h)]
    queue = []
    for y in range(h):
        for x in range(w):
            if field[y][x] == "#":
                queue.append((x, y))

    queue_cand = []
    d = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    cnt = 0
    while True:
        cnt += 1
        queue_cand = []
        for (x, y) in queue:
            for (dx, dy) in d:
                if 0 <= (x + dx) < w and 0 <= (y + dy) < h:
                    if field[y + dy][x + dx] == ".":
                        field[y + dy][x + dx] = cnt
                        queue_cand.append((x + dx, y + dy))

                    elif field[y + dy][x + dx] != "#":
                        if field[y + dy][x + dx] > cnt:
                            field[y + dy][x + dx] = min(field[y + dy][x + dx], cnt)
                            queue_cand.append((x + dx, y + dy))
        if len(queue_cand) == 0:
            break
        queue = copy.deepcopy(queue_cand)

    ans = 0
    for y in range(h):
        for x in range(w):
            if field[y][x] != "#":
                ans = max(ans, field[y][x])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

#初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

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

black_cells = deque()
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            black_cells.append((i,j))
            dist[i][j] = 0
            
d = bfs(black_cells,dist)
print(d)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from sys import stdin


def main():
    height, width = map(int, stdin.readline().split())
    q = deque([])
    grid = []
    for i in range(height):
        now = list(stdin.readline())
        for j in range(width):
            if now[j] == "#":
                q.append([i, j, 0])
        grid.append(now)
    answer = 0

    def is_next_cell_white(ny, nx):
        return 0 <= ny < height and 0 <= nx < width and grid[ny][nx] == "."

    while q:
        y, x, time = q.popleft()
        answer = max(answer, time)
        if is_next_cell_white(y - 1, x):
            grid[y - 1][x] = "#"
            q.append([y - 1, x, time + 1])

        if is_next_cell_white(y + 1, x):
            grid[y + 1][x] = "#"
            q.append([y + 1, x, time + 1])

        if is_next_cell_white(y, x - 1):
            grid[y][x - 1] = "#"
            q.append([y, x - 1, time + 1])

        if is_next_cell_white(y, x + 1):
            grid[y][x + 1] = "#"
            q.append([y, x + 1, time + 1])

    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from sys import stdin


def main():
    height, width = map(int, stdin.readline().split())
    q = deque([])
    grid = []
    for i in range(height):
        now = list(stdin.readline())
        for j in range(width):
            if now[j] == "#":
                q.append([i, j, 0])
        grid.append(now)
    d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    answer = 0
    while q:
        y, x, time = q.popleft()
        answer = max(answer, time)
        for dy, dx in d:
            new_y = y + dy
            new_x = x + dx
            if 0 <= new_y < height and 0 <= new_x < width and grid[new_y][new_x] == ".":
                grid[new_y][new_x] = "#"
                q.append([new_y, new_x, time + 1])
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    height, width = map(int, input().split())
    q = deque([])
    grid = []
    change_time = [[-1 for _ in range(width)] for _ in range(height)]
    for i in range(height):
        now = list(input())
        for j in range(width):
            if now[j] == "#":
                q.append([i, j])
                change_time[i][j] = 0
        grid.append(now)
    d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    answer = 0
    while q:
        y, x = q.popleft()
        answer = change_time[y][x]
        for dy, dx in d:
            new_y = y + dy
            new_x = x + dx
            if 0 <= new_y < height and 0 <= new_x < width and grid[new_y][new_x] == ".":
                grid[new_y][new_x] = "#"
                change_time[new_y][new_x] = change_time[y][x] + 1
                q.append([new_y, new_x])
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    height, width = map(int, input().split())
    q = deque([])
    grid = []
    change_time = [[-1 for _ in range(width)] for _ in range(height)]
    for i in range(height):
        now = list(input())
        for j in range(width):
            if now[j] == "#":
                q.append([i, j])
                change_time[i][j] = 0
        grid.append(now)
    d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    answer = 0
    while q:
        y, x = q.popleft()
        grid[y][x] = "#"
        answer = change_time[y][x]
        for dy, dx in d:
            new_y = y + dy
            new_x = x + dx
            if 0 <= new_y < height and 0 <= new_x < width and grid[new_y][new_x] == ".":
                change_time[new_y][new_x] = change_time[y][x] + 1
                q.append([new_y, new_x])
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    height, width = map(int, input().split())
    grid = [list(input()) for _ in range(height)]
    q = deque([])
    change_time = [[float("inf") for _ in range(width)] for _ in range(height)]
    for i in range(height):
        for j in range(width):
            if grid[i][j] == "#":
                q.append([i, j, 0])
                change_time[i][j] = 0
    d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    answer = 0
    while q:
        y, x, time = q.popleft()
        grid[y][x] = "#"
        for dy, dx in d:
            new_y = y + dy
            new_x = x + dx
            if 0 <= new_y < height and 0 <= new_x < width and grid[new_y][new_x] == ".":
                change_time[new_y][new_x] = min(change_time[new_y][new_x], change_time[y][x] + 1)
                q.append([new_y, new_x, change_time[new_y][new_x]])
                answer = max(answer, change_time[new_y][new_x])
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import deque

h, w = map(int, readline().split())
a = [input() for i in range(h)]
q = []
dist = [[True] * 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] = False
cnt = -1
while q:
    cnt += 1
    qq = deque()
    for y, x in q:
        if x + 1 < w and dist[y][x + 1]:
            dist[y][x + 1] = False
            qq.append((y, x + 1))
        if x - 1 >= 0 and dist[y][x - 1]:
            dist[y][x - 1] = False
            qq.append((y, x - 1))
        if y + 1 < h and dist[y + 1][x]:
            dist[y + 1][x] = False
            qq.append((y + 1, x))
        if y - 1 >= 0 and dist[y - 1][x]:
            dist[y - 1][x] = False
            qq.append((y - 1, x))
    q = qq
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

h, w = map(int, readline().split())
a = [input() for i in range(h)]
q = []
dist = [[True] * 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] = False
cnt = -1
while q:
    cnt += 1
    qq = []
    for y, x in q:
        if x + 1 < w and dist[y][x + 1]:
            dist[y][x + 1] = False
            qq.append((y, x + 1))
        if x - 1 >= 0 and dist[y][x - 1]:
            dist[y][x - 1] = False
            qq.append((y, x - 1))
        if y + 1 < h and dist[y + 1][x]:
            dist[y + 1][x] = False
            qq.append((y + 1, x))
        if y - 1 >= 0 and dist[y - 1][x]:
            dist[y - 1][x] = False
            qq.append((y - 1, x))
    q = qq
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

h, w = map(int, readline().split())
a = [input() for i in range(h)]
s = []
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            s.append([i, j])
test = [(0, 1), (0, -1), (1, 0), (-1, 0)]
inf = float('inf')
dist = [[inf] * w for _ in range(h)]
cnt = 0
while s:
    q = [s.pop(0)]
    dist[q[0][0]][q[0][1]] = 0
    q[0] = tuple(q[0])
    cnt = 0
    while q:
        if cnt == (h + w - 2):
            break
        qq = []
        cnt += 1
        for y, x in q:
            for dy, dx in test:
                yy, xx = y + dy, x + dx
                if xx < 0 or yy < 0 or xx > w - 1 or yy > h - 1:
                    continue
                if a[yy][xx] == '#':
                    continue
                if dist[yy][xx] < cnt:
                    continue
                dist[yy][xx] = cnt
                qq.append((yy, xx))
        q = qq
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:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from collections import deque

def main():
    h,w = map(int,input().split())
    grid = [input() for _ in range(h)]
    dist = [[-1] * w for _ in range(h)]
    
    q = deque()
    for i in range(h):
        for j in range(w):
            if grid[i][j] == '#':
                q.append((i,j))
                dist[i][j] = 0
    
    ans = 0
    while q:
        i,j = q.popleft()
        for k in range(4):
            y = i + dy[k]
            x = j + dx[k]
            if 0 <= y < h and 0 <= x < w and dist[y][x] == -1:
                dist[y][x] = dist[i][j] + 1
                ans = max(ans,dist[y][x])
                q.append((y,x))
    
    print(ans)

if __name__ =='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

def main():
    h,w = (int(x) for x in input().split())
    field = [[j=='#' for j in input()] for _ in range(h)]

    que = deque([(i,j) for i in range(h) for j in range(w) if field[i][j]])

    dy, dx = [0,1,0,-1], [1,0,-1,0]
    cnt = 0
    while True:
        tque = deque()
        cnt += 1
        while que:
            y,x = que.popleft()
            for i in range(4):
                ny, nx = y+dy[i], x+dx[i]
                if ny < 0 or h <= ny: continue
                if nx < 0 or w <= nx: continue
                if field[ny][nx]: continue
                field[ny][nx] = True
                tque.append((ny,nx))

        if tque:
            que = copy.copy(tque)
        else:
            break
    print(cnt-1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

def main():
    h,w = (int(x) for x in input().split())
    field = [[j=='#' for j in input()] for _ in range(h)]

    que = deque([(i,j) for i in range(h) for j in range(w) if field[i][j]])

    dy, dx = [0,1,0,-1], [1,0,-1,0]
    cnt = 0
    while True:
        tque = deque()
        while que:
            y,x = que.popleft()
            for i in range(4):
                ny, nx = y+dy[i], x+dx[i]
                if ny < 0 or h <= ny: continue
                if nx < 0 or w <= nx: continue
                if field[ny][nx]: continue
                field[ny][nx] = True
                tque.append((ny,nx))

        if tque:
            que = copy.copy(tque)
            cnt += 1
        else:
            break
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def solve():
    H, W = map(int, input().split())
    m = [[-1]*W for _ in range(H)]
    l = [list(input()) for _ in range(H)]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    q = deque([])

    for i in range(H):
        for j in range(W):
            if l[i][j]=="#":
                q.append((i, j, 0))
                m[i][j] = 0
    
    while q:
        y, x, cost = q.popleft()
        m[y][x] = cost

        for px, py in zip(dx, dy):
            x1, y1 = x + px, y + py
            if not (0<=x1<W and 0<=y1<H):
                continue
            if m[y1][x1] == -1:
                q.append((y1, x1, cost+1))

    print(max(map(max, m)))


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def solve():
    H, W = map(int, input().split())
    m = [[-1]*W for _ in range(H)]
    q = deque([])
    l = [input() for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if l[i][j]=="#":
                q.append((i, j, 0))
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    while q:
        y, x, cost = q.popleft()
        m[y][x] = cost

        for px, py in zip(dx, dy):
            x1, y1 = x + px, y + py
            if not (0<=x1<W and 0<=y1<H):
                continue
            if m[y1][x1] == -1:
                q.append((y1, x1, cost+1))

    print(max(map(max, m)))


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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


def solve():
    H, W = map(int, input().split())
    m = [[-1]*W for _ in range(H)]
    q = deque([])
    l = [input() for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if l[i][j]=="#":
                q.append((i, j, 0))
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    while q:
        y, x, cost = q.popleft()
        m[y][x] = cost

        for px, py in zip(dx, dy):
            x1, y1 = x + px, y + py
            if not (0<=x1<W and 0<=y1<H):
                continue
            if m[y1][x1] == -1:
                q.append((y1, x1, cost+1))

    print(max(map(max, m)))


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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


def solve():
    H, W = map(int, input().split())
    m = [[-1]*W for _ in range(H)]
    candidate = [(i, j, 0) for i in range(H) for j, s in enumerate(input()) if s=="#"]
    q = deque(candidate)
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    while q:
        y, x, cost = q.popleft()
        m[y][x] = cost

        for i in range(4):
            x1, y1 = x + dx[i], y + dy[i]
            if not (0<=x1<W and 0<=y1<H):
                continue
            if m[y1][x1] == -1:
                q.append((y1, x1, cost+1))

    print(max(map(max, m)))


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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


def solve():
    H, W = map(int, input().split())
    m = [[-1]*W for _ in range(H)]
    candidate = [(i, j, 0) for i in range(H) for j, s in enumerate(input()) if s=="#"]
    q = deque(candidate)

    while q:
        y, x, cost = q.popleft()
        m[y][x] = cost

        for y1, x1 in [(y-1, x), (y+1, x), (y, x-1), (y, x+1)]:
            if not (0<=x1<W and 0<=y1<H):
                continue
            if m[y1][x1] == -1:
                q.append((y1, x1, cost+1))

    print(max(map(max, m)))


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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


def solve():
    H, W = map(int, input().split())
    m = [[H*W]*W for _ in range(H)]
    candidate = [(i, j, 0) for i in range(H) for j, s in enumerate(input()) if s=="#"]
    q = deque(candidate)

    while q:
        y, x, cost = q.popleft()
        m[y][x] = cost

        for y1, x1 in [(y-1, x), (y+1, x), (y, x-1), (y, x+1)]:
            if not (0<=x1<W and 0<=y1<H):
                continue
            if m[y1][x1] > cost+1:
                q.append((y1, x1, cost+1))

    print(max(map(max, m)))


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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


def solve():
    H, W = map(int, input().split())
    used = [[0]*W for _ in range(H)]
    candidate = [(i, j, 0) for i in range(H) for j, s in enumerate(input()) if s=="#"]
    q = deque(candidate)

    while q:
        y, x, cost = q.popleft()
        used[y][x] = 1

        for y1, x1 in [(y-1, x), (y+1, x), (y, x-1), (y, x+1)]:
            if not (0<=x1<W and 0<=y1<H):
                continue
            if used[y1][x1]:
                continue
            q.append((y1, x1, cost+1))

    print(cost)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    
    H,W = LMIIS()
    A = []
    for _ in range(H):
        A.append(input())
    from copy import deepcopy
    blacks = []
    max_d = 0
    for w in range(W):
        for h in range(H):
            if A[h][w] == '#':
                blacks.append((h,w))
    for w in range(W):
        for h in range(H):
            if A[h][w] == '.':
                d = 10**7
                for i,j in blacks:
                    d = min(d,abs(i-h)+abs(j-w))
                max_d = max(max_d,d)
    print(max_d)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections

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

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

def f(y,x):
    for i in range(4):
        newy = y + dy[i]
        newx = x + dx[i]
        if 0 <= newy and newy < h and 0 <= newx and newx < w:
            if tizu[newy][newx] == ".":
                q.append((newy,newx))
                tizu[newy][newx] = "#"
            
q = collections.deque()
for i in range(h): 
    for k in range(w):
        if tizu[i][k] == "#":
            q.append((i,k))
ans = 0
while True:
    l = len(q)
    if l == 0:
        print(ans-1)
        exit()
    for i in range(l):
        yx = q.popleft()
        f(yx[0],yx[1])
    ans += 1

Submission status: Time Limit Exceeded

Solution code:
import collections

h,w = map(int,input().split())

tizu = []
for i in range(h):
    s = list(input())
    tizu.append(s)

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

def f(y,x):
    for i in range(4):
        newy = y + dy[i]
        newx = x + dx[i]
        if 0 <= newy and newy < h and 0 <= newx and newx < w:
            if tizu[newy][newx] == ".":
                q.append((newy,newx))
                tizu[newy][newx] = "#"
            
q = collections.deque()
for i in range(h): 
    for k in range(w):
        if tizu[i][k] == "#":
            q.append((i,k))
ans = 0
while True:
    flag = False
    l = len(q)
    for i in range(l):
        yx = q.popleft()
        f(yx[0],yx[1])
        #tizu[yx[0]][yx[1]] = "#"
        flag = True
    if flag == False:
        print(ans-1)
        exit()
    ans += 1

Submission status: Time Limit Exceeded

Solution code:
import collections

h,w = map(int,input().split())

tizu = []
for i in range(h):
    s = list(input())
    tizu.append(s)

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

def f(y,x):
    for i in range(4):
        newy = y + dy[i]
        newx = x + dx[i]
        if 0 <= newy and newy < h and 0 <= newx and newx < w:
            if tizu[newy][newx] == ".":
                q.append((newy,newx))
            
q = collections.deque()
ans = 0
while True:
    flag = False
    for i in range(h): 
        for k in range(w):
            if tizu[i][k] == "#":
                f(i,k)

    while q:
        yx = q.popleft()
        tizu[yx[0]][yx[1]] = "#"
        flag = True
   
    if flag == False:
        print(ans)
        exit()
    ans += 1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = list(map(int,input().split()))
m = [[x for x in input()] for _ in range(h)]
next_que = deque([])
for i in range(h):
  for j in range(w):
    if m[i][j] == '#':
      next_que.append([i,j])


dh = [1,0,-1,0]
dw = [0,1,0,-1]

def bfs(next_que):
  cnt = -1
  while next_que:
    cnt += 1
    que = list(next_que)
    next_que = deque([])
    for cur in que:
      #cur = que.popleft()
      for i in range(4):
        nh = cur[0] + dh[i]
        nw = cur[1] + dw[i]
        
        if nh >= 0 and nh < h and nw >= 0 and nw < w and m[nh][nw] == '.':
          m[nh][nw] = '#'
          next_que.append([nh,nw])
  
  return cnt



cnt = bfs(next_que) 

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = list(map(int,input().split()))
par = [[x for x in input()] for _ in range(h)]
que = deque([])
for i in range(h):
  for j in range(w):
    if par[i][j] == '#':
      que.append([i,j])

m = par.copy()

dh = [1,0,-1,0]
dw = [0,1,0,-1]

def bfs(que):
  next_que = deque([])
  while que:
    cur = que.popleft()
    
    for i in range(4):
      nh = cur[0] + dh[i]
      nw = cur[1] + dw[i]
      
      if nh >= 0 and nh < h and nw >= 0 and nw < w and m[nh][nw] == '.':
        m[nh][nw] = '#'
        next_que.append([nh,nw])
        
  return next_que


cnt = 0
while que:
  cnt += 1
  que = bfs(que)

print(cnt-1)