Problem:


Score : 300 points

Problem Statement

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

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

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

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

Constraints

1 \leq H,W \leq 1000

A_{ij} is # or ..

The given grid has at least one black square.

Input

Input is given from Standard Input in the following format:

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

Output

Print the number of operations that will be performed.

Sample Input 1

3 3
...
.#.
...

Sample Output 1

2

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

Sample Input 2

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

Sample Output 2

3



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


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def grid_wall(grid, h, w, wall='#'):
    G = [[wall]*(w+2) for _ in range(h+2)]
    for hi in range(h):
        G[hi+1][1:w+1] = grid[hi]
    return G

def solve():
    H, W = MI()
    g = [[] for _ in range(H)]
    start = []
    white_cnt = 0
    for i in range(H):
        line = LS()
        for j, l in enumerate(line):
            if l == '.': white_cnt = white_cnt + 1
            else: start.append((i+1, j+1))
        g[i] = line

    if white_cnt == 0:
        print(0)
        return

    G = grid_wall(g, H, W, 'x')
    move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    ans = 0
    while start:
        next = []
        for x, y in start:
            for dx, dy in move:
                nx, ny = x+dx, y+dy
                if G[nx][ny] == 'x': continue
                elif G[nx][ny] == '#': continue
                elif G[nx][ny] == '.':
                    white_cnt -= 1
                    G[nx][ny] = '#'
                    next.append((nx, ny))
        ans += 1
        # print(G)
        if white_cnt <= 0:
            print(ans)
            return
        start = next



if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate
import copy

def grid_wall(grid, h, w, wall='#'):
    G = [[wall]*(w+2) for _ in range(h+2)]
    for hi in range(h):
        G[hi+1][1:w+1] = grid[hi]
    return G

def solve():
    H, W = MI()
    g = [[] for _ in range(H)]
    start = []
    white_cnt = 0
    for i in range(H):
        line = LS()
        for j, l in enumerate(line):
            if l == '.': white_cnt = white_cnt + 1
            else: start.append((i+1, j+1))
        g[i] = line

    if white_cnt == 0:
        print(0)
        return 

    G = grid_wall(g, H, W, 'x')
    move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    ans = 0
    while 1:
        next = []
        for x, y in start:
            for dx, dy in move:
                nx, ny = x+dx, y+dy
                if G[nx][ny] == 'x': continue
                elif G[nx][ny] == '#': continue
                elif G[nx][ny] == '.':
                    white_cnt -= 1
                    G[nx][ny] = '#'
                    next.append((nx, ny))
        ans += 1
        # print(G)
        if white_cnt <= 0:
            print(ans)
            return
        start = next[:]



if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin

    H, W = map(int, input().split())
    g = []
    q = []
    cnt = 0
    for h in range(H):
        A = stdin.readline()
        row = []
        for w in range(W):
            row.append(A[w])
            if A[w] == '#':
                cnt += 1
                q.append((h, w))
        g.append(row)
    ans = 0
    dh = [1, 0, 0, -1]
    dw = [0, -1, 1, 0]
    while cnt < H * W:
        ans += 1
        nextq = []
        while q:
            h, w = q.pop()
            for i in range(4):
                nh = h + dh[i]
                nw = w + dw[i]
                if 0 <= nh < H and 0 <= nw < W and g[nh][nw] == '.':
                    g[nh][nw] = '#'
                    nextq.append((nh, nw))
                    cnt += 1
        q = nextq
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin

    H, W = map(int, input().split())
    g = []
    q = []
    cnt = 0
    for h in range(H):
        A = stdin.readline()
        row = []
        for w in range(W):
            row.append(A[w])
            if A[w] == '#':
                cnt += 1
                q.append([h, w])
        g.append(row)
    ans = 0
    dh = [1, 0, 0, -1]
    dw = [0, -1, 1, 0]
    while cnt < H * W:
        ans += 1
        nextq = []
        while q:
            h, w = q.pop()
            for i in range(4):
                nh = h + dh[i]
                nw = w + dw[i]
                if 0 <= nh < H and 0 <= nw < W and g[nh][nw] == '.':
                    g[nh][nw] = '#'
                    nextq.append([nh, nw])
                    cnt += 1
        q = nextq
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
g = []
q = []
cnt = 0
for h in range(H):
    A = str(input())
    row = []
    for w in range(W):
        row.append(A[w])
        if A[w] == '#':
            cnt += 1
            q.append([h, w])
    g.append(row)
ans = 0
dh = [1, 0, 0, -1]
dw = [0, -1, 1, 0]
while cnt < H * W:
    ans += 1
    nextq = []
    while q:
        h, w = q.pop()
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            if 0 <= nh < H and 0 <= nw < W and g[nh][nw] == '.':
                g[nh][nw] = '#'
                nextq.append([nh, nw])
                cnt += 1
    q = nextq
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import copy

    H, W = map(int, input().split())
    g = []
    cnt = 0
    for _ in range(H):
        A = str(input())
        row = []
        for i in range(W):
            row.append(A[i])
            if A[i] == '#':
                cnt += 1
        g.append(row)
    ans = 0
    dh = [1, 0, 0, -1]
    dw = [0, -1, 1, 0]
    while cnt < H * W:
        ans += 1
        newg = copy.deepcopy(g)
        for h in range(H):
            for w in range(W):
                if g[h][w] == '#':
                    for i in range(4):
                        nh = h + dh[i]
                        nw = w + dw[i]
                        if 0 <= nh < H and 0 <= nw < W and g[nh][nw] == '.' and newg[nh][nw] != '#':
                            newg[nh][nw] = '#'
                            cnt += 1
        g = newg
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque

    H, W = map(int, input().split())
    g = [str(input()) for _ in range(H)]
    ans = 0
    dh = [1, 0, 0, -1]
    dw = [0, -1, 1, 0]
    for h in range(H):
        for w in range(W):
            if g[h][w] == '.':
                d = 0
                done = [[False] * W for _ in range(H)]
                done[h][w] = True
                q = deque([[h, w]])
                while q:
                    h, w = q.popleft()
                    d += 1
                    for i in range(4):
                        nh = h + dh[i]
                        nw = w + dw[i]
                        if 0 <= nh < H and 0 <= nw < W and done[nh][nw] == False:
                            if g[nh][nw] == '.':
                                done[nh][nw] = True
                                q.append([nh, nw])
                            else:
                                q.clear()
                                break
                ans = max(ans, d)
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
g = [str(input()) for _ in range(H)]
ans = 0
dh = [1, 0, 0, -1]
dw = [0, -1, 1, 0]
for h in range(H):
    for w in range(W):
        if g[h][w] == '.':
            d = 0
            done = [[False] * W for _ in range(H)]
            done[h][w] = True
            q = deque([[h, w]])
            while q:
                h, w = q.popleft()
                d += 1
                for i in range(4):
                    nh = h + dh[i]
                    nw = w + dw[i]
                    if 0 <= nh < H and 0 <= nw < W and done[nh][nw] == False:
                        if g[nh][nw] == '.':
                            done[nh][nw] = True
                            q.append([nh, nw])
                        else:
                            q.clear()
                            break
            ans = max(ans, d)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
a = [list(input()) for i in range(h)]
que = []
v = [[True] * (w + 2)]
v += [[True] + [j == "#" for j in a[i]] + [True] for i in range(h)]
v.append([True] * (w + 2))
m = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if v[i][j]:
            que.append((i, j))
ans = 0
while que:
    p = []
    ans += 1
    for x, y in que:
        if not v[x - 1][y]:
            v[x - 1][y] = True
            p.append((x - 1, y))
        if not v[x + 1][y]:
            v[x + 1][y] = True
            p.append((x + 1, y))
        if not v[x][y - 1]:
            v[x][y - 1] = True
            p.append((x, y - 1))
        if not v[x][y + 1]:
            v[x][y + 1] = True
            p.append((x, y + 1))
    que = p
print(ans - 1)

Submission status: Time Limit Exceeded

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

inf = 10**9
f = [[inf]*w for _ in range(h)]
q = deque()
for hi in range(h):
    for wi in range(w):
        if al[hi][wi]=="#":
            f[hi][wi] = 0
            q.append((hi,wi))

while len(q)>0:
    hi,wi = q.pop()
    c = f[hi][wi]

    for dh,dw in [[0,1],[1,0],[0,-1],[-1,0]]:
        nh = hi+dh
        nw = wi+dw
        if h>nh>=0 and w>nw>=0:
            if f[nh][nw]>c+1:
                f[nh][nw] = c+1
                q.append((nh,nw))

res = 0
for hi in range(h):
    for wi in range(w):
        res = max(res,f[hi][wi])
print(res)

Submission status: Time Limit Exceeded

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

inf = 10**9
f = [[inf]*w for _ in range(h)]
q = deque()
for hi in range(h):
    for wi in range(w):
        if al[hi][wi]=="#":
            f[hi][wi] = 0
            q.append((hi,wi))

while len(q)>0:
    hi,wi = q.popleft()
    c = f[hi][wi]

    for dh,dw in [[0,1],[1,0],[0,-1],[-1,0]]:
        nh = hi+dh
        nw = wi+dw
        if h>nh>=0 and w>nw>=0:
            if f[nh][nw]>c+1:
                f[nh][nw] = c+1
                q.append((nh,nw))

res = 0
for hi in range(h):
    for wi in range(w):
        res = max(res,f[hi][wi])
print(res)

Submission status: Time Limit Exceeded

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

h, w = map(int, input().split())
M = []
q = []
for i in range(h):
    line = input().strip()
    M.append(list(line))
    for j in range(w):
        if line[j] == "#":
            M[i][j] = 0
            q.append((j, i))

dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]
cnt = 0
while q:
    next_q = []
    cnt += 1
    for x, y in q:
        for dx,dy in dir:
            next_x, next_y = x + dx, y + dy
            if 0 <= next_y <= h - 1 and 0 <= next_x <= w - 1:
                if M[next_y][next_x] == ".":
                    M[next_y][next_x] = M[y][x] + 1
                    q.append((next_x, next_y))
    q = next_q

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, M[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/agc033/tasks/agc033_a

from pprint import pprint
from collections import deque

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

count = [[-1] * w for i in range(h)]

d = deque()

for i in range(w):
    for j in range(h):
        if maze[j][i] == "#":
            d.append((j, i))
            count[j][i] = 0

ans = 0

while d:
    x, y = d.popleft()
    ans = count[x][y]
    for i, j in ([1, 0], [0, 1], [-1, 0], [0, -1]):
        tx, ty = x + i, y + j
        if (
            not (0 <= tx < h)
            or not (0 <= ty < w)
            or maze[tx][ty] == "#"
            or count[tx][ty] != -1
        ):
            continue
        else:
            count[tx][ty] = count[x][y] + 1
            d.append((tx, ty))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/agc033/tasks/agc033_a

from pprint import pprint
from collections import deque

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

count = [[-1] * w for i in range(h)]

d = deque()

for i in range(w):
    for j in range(h):
        if maze[j][i] == "#":
            d.append([j, i])
            count[j][i] = 0

while d:
    x, y = d.popleft()
    for i, j in ([1, 0], [0, 1], [-1, 0], [0, -1]):
        tx, ty = x + i, y + j
        if (
            not (0 <= tx < h)
            or not (0 <= ty < w)
            or maze[tx][ty] == "#"
            or count[tx][ty] != -1
        ):
            continue
        else:
            count[tx][ty] = count[x][y] + 1
            d.append([tx, ty])

ans = 0
for i in range(w):
    for j in range(h):
        ans = max(ans, count[j][i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/agc033/tasks/agc033_a

from pprint import pprint
from collections import deque

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

count = [[0] * w for i in range(h)]
check = [[0] * w for i in range(h)]

d = deque()

for i in range(w):
    for j in range(h):
        if maze[j][i] == "#":
            d.append([j, i])
            check[j][i] = 1

while d:
    x, y = d.popleft()
    for i, j in ([1, 0], [0, 1], [-1, 0], [0, -1]):
        tx, ty = x + i, y + j
        if (
            not (0 <= tx < h)
            or not (0 <= ty < w)
            or maze[tx][ty] == "#"
            or check[tx][ty] == 1
        ):
            continue
        else:
            count[tx][ty] = count[x][y] + 1
            check[tx][ty] = 1
            d.append([tx, ty])

ans = 0
for i in range(w):
    for j in range(h):
        ans = max(ans, count[j][i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
from collections import deque
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

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

    start = []
    for h in range(H):
        for w in range(W):
            if mat[h][w] == '#':
                start.append((h, w))
    
    res = 0
    que = deque(start)
    while que:
        next_que = deque()
        for h, w in que:
            for dh, dw in directions:
                if not (0 <= h+dh < H and 0 <= w+dw < W):
                    continue
                if mat[h+dh][w+dw] == '#':
                    continue
                mat[h+dh][w+dw] = '#'
                next_que.append((h+dh, w+dw))

        res += 1
        que = next_que

    print(res - 1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
from collections import deque
directions = ((-1, 0), (1, 0), (0, -1), (0, 1))


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

    start = []
    for h in range(H):
        for w in range(W):
            if mat[h][w] == '#':
                start.append((h, w))
    
    res = 0
    que = deque(start)
    while que:
        flg = False
        next_que = deque()
        while que:
            h, w = que.popleft()
            for dh, dw in directions:
                if not (0 <= h+dh < H and 0 <= w+dw < W):
                    continue
                if mat[h+dh][w+dw] == '#':
                    continue
                flg = True
                mat[h+dh][w+dw] = '#'
                next_que.append((h+dh, w+dw))

        if flg:
            res += 1
        que = next_que

    print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque



readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

def bfs(start):
    tansaku = deque(start)
    visited = {i:set() for i in range(h)}
    res = 0
    black = len(start)
    while black != h*w:
        for _ in range(len(tansaku)):
            pre_y,pre_x = tansaku.popleft()
            if pre_x in visited[pre_y]:
                continue
            for i in range(pre_x-1,pre_x+2,2):
                if 0 <= i <= w-1 and tizu[pre_y][i] == '.':
                    tansaku.append([pre_y,i])
                    tizu[pre_y][i] = '#'
            for j in range(pre_y-1,pre_y+2,2):
                if 0 <= j <= h-1 and tizu[j][pre_x] == '.':
                    tansaku.append([j,pre_x])
                    tizu[j][pre_x] = '#'
            visited[pre_y].add(pre_x)
        black += len(tansaku)
        res += 1
    return res

h,w = nm()
tizu = []
sharp = []
for i in range(h):
    temp = list(input())
    s_temp = [[i,j] for j in range(w)  if temp[j] == '#' ]
    tizu.append(temp)
    sharp += s_temp
ans = bfs(sharp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    D = dict()
    #D = [[3000 for _ in range(W)] for h in range(H)]
    q = deque()
    move = ((-1, 0), (0, -1), (1, 0), (0, 1))
    for h in range(H):
        D[h] = dict()
        a = input().strip("\n")
        for w in range(W):
            D[h][w] = 3000
            if a[w] == "#": q.append((0, h, w))
    L = 0
    while q:
        d, h, w = q.popleft()
        if D[h][w] > d:
            D[h][w] = d
            L = d
            for dh, dw in move:
                if 0 <= h+dh < H and 0 <= w+dw < W and D[h+dh][w+dw] > d + 1:
                    q.append((d+1, h+dh, w+dw))
    print(L)


    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    D = [[3000 for _ in range(W)] for h in range(H)]
    q = deque()
    move = ((-1, 0), (0, -1), (1, 0), (0, 1))
    for h in range(H):
        a = input().strip("\n")
        for w in range(W):
            if a[w] == "#": q.append((0, h, w))
    L = 0
    while q:
        d, h, w = q.popleft()
        if D[h][w] > d:
            D[h][w] = d
            L = d
            for dh, dw in move:
                if 0 <= h+dh < H and 0 <= w+dw < W and D[h+dh][w+dw] > d + 1:
                    q.append((d+1, h+dh, w+dw))
    print(L)


    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    D = [[3000 for _ in range(W)] for h in range(H)]
    q = deque()
    move = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    for h in range(H):
        a = input().strip("\n")
        for w in range(W):
            if a[w] == "#": q.append((0, h, w))
    L = 0
    while q:
        d, h, w = q.popleft()
        if D[h][w] > d:
            D[h][w] = d
            L = d
            for dh, dw in move:
                if 0 <= h+dh < H and 0 <= w+dw < W:
                    q.append((d+1, h+dh, w+dw))
    print(L)


    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

x = []

for i in range(h):
    for j in range(w):
        if(s[i][j] == '#'):x.append([i,j])
m = 0

for i in range(h):
    for j in range(w):
        if(s[i][j] == '.'):
            m2 = h*w
            for z in x:m2 = min(m2,abs(z[0]-i) + abs(z[1]-j))
            m = max(m,m2)
print(m)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    D = [[3000 for _ in range(W)] for h in range(H)]
    q = deque()
    move = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    for h in range(H):
        a = input().strip("\n")
        for w in range(W):
            if a[w] == "#": q.append((0, h, w))
    L = 0
    while q:
        d, h, w = q.popleft()
        if D[h][w] > d:
            D[h][w] = d
            L = d
            for dh, dw in move:
                if 0 <= h+dh < H and 0 <= w+dw < W and D[h+dh][w+dw] > d + 1:
                    q.append((d+1, h+dh, w+dw))
    print(L)


    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

area = [input() for _ in range(H)]

distance = [ [float('inf') for _ in range(W)] for _ in range(H)]
to_search = deque()
for i in range(H):
    for j in range(W):
        if area[i][j] == "#":
            to_search.appendleft((i, j, 0))
            distance[i][j] = 0
dist = [[1,0], [0,1], [-1,0], [0,-1]]
ans = 0
while len(to_search) > 0:
    nowi, nowj , nowd = to_search.pop()
    for di, dj in dist:
        nexti = nowi+di
        nextj = nowj+dj
        if 0<= nexti< H and 0<= nextj< W:
            if distance[nexti][nextj] > nowd+1:
                to_search.appendleft((nexti, nextj, nowd+1))
                distance[nexti][nextj] = nowd+1
                ans = max(ans, nowd+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    D = [[3000 for _ in range(W)] for h in range(H)]
    q = deque()
    move = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    for h in range(H):
        a = input().strip("\n")
        for w in range(W):
            if a[w] == "#": q.append((0, h, w))
    L = 0
    while q:
        d, h, w = q.popleft()
        if D[h][w] > d:
            D[h][w] = d
            L = max(d, L)
            for dh, dw in move:
                if 0 <= h+dh < H and 0 <= w+dw < W and D[h+dh][w+dw] > d + 1:
                    q.append((d+1, h+dh, w+dw))
    print(L)


    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    D = [[3000 for _ in range(W)] for h in range(H)]
    q = deque()
    move = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    for h in range(H):
        a = input().strip("\n")
        for w in range(W):
            if a[w] == "#": 
                D[h][w] = 0
                for dh, dw in move:
                    if 0 <= h+dh < H and 0 <= w+dw < W: q.append((1, h+dh, w+dw))
    L = 0
    while q:
        d, h, w = q.popleft()
        if D[h][w] > d:
            D[h][w] = d
            L = max(d, L)
            for dh, dw in move:
                if 0 <= h+dh < H and 0 <= w+dw < W:
                    q.append((d+1, h+dh, w+dw))
    print(L)


    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [input().strip("\n") for _ in range(H)]
    D = [[3000 for _ in range(W)] for h in range(H)]
    q = deque()
    move = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#": 
                D[h][w] = 0
                for dh, dw in move:
                    if 0 <= h+dh < H and 0 <= w+dw < W: q.append((1, h+dh, w+dw))
    L = 0
    while q:
        d, h, w = q.popleft()
        if D[h][w] > d:
            D[h][w] = d
            L = max(d, L)
            for dh, dw in move:
                if 0 <= h+dh < H and 0 <= w+dw < W:
                    q.append((d+1, h+dh, w+dw))
    print(L)


    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [input().strip("\n") for _ in range(H)]
    D = [[3000 for _ in range(W)] for h in range(H)]
    q = deque()
    move = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#": 
                D[h][w] = 0
                for dh, dw in move:
                    if 0 <= h+dh < H and 0 <= w+dw < W: q.append((1, h+dh, w+dw))
    L = 0
    while q:
        d, h, w = q.popleft()
        if D[h][w] > d:
            D[h][w] = d
            L = max(d, L)
            for dh, dw in move:
                if 0 <= h+dh < H and 0 <= w+dw < W and D[h+dh][w+dw] > d + 1:
                    q.append((d+1, h+dh, w+dw))
    print(L)


    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [input().strip("\n") for _ in range(H)]
    D = [[3000 for _ in range(W)] for h in range(H)]
    q = deque()
    move = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#": q.append((0, h, w))
    L = 0
    while q:
        d, h, w = q.popleft()
        if D[h][w] > d:
            D[h][w] = d
            L = max(d, L)
            for dh, dw in move:
                if 0 <= h+dh < H and 0 <= w+dw < W and D[h+dh][w+dw] > d + 1:
                    q.append((d+1, h+dh, w+dw))
    print(L)


    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [input().strip("\n") for _ in range(H)]
    D = [[10 ** 5 for _ in range(W)] for h in range(H)]
    q = deque()
    move = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#": q.append((0, h, w))
    L = 0
    while q:
        d, h, w = q.popleft()
        if D[h][w] > d:
            D[h][w] = d
            L = max(d, L)
            for dh, dw in move:
                if 0 <= h+dh < H and 0 <= w+dw < W and D[h+dh][w+dw] > d + 1:
                    q.append((d+1, h+dh, w+dw))
    print(L)


    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [input().strip("\n") for _ in range(H)]
    D = [[10 ** 20 for _ in range(W)] for h in range(H)]
    q = deque()
    move = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#": q.append((0, h, w))
    L = 0
    while q:
        d, h, w = q.popleft()
        if D[h][w] > d:
            D[h][w] = d
            L = max(d, L)
            for dh, dw in move:
                if 0 <= h+dh < H and 0 <= w+dw < W:
                    q.append((d+1, h+dh, w+dw))
    print(L)


    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque



readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

def bfs(start,ex_kyori):
    tansaku = deque()
    tansaku.append(start)
    visited = {i:set() for i in range(h)}
    kyori = ex_kyori
    while tansaku:
        pre_y,pre_x = tansaku.popleft()
        if pre_x in visited[pre_y]:
            continue
        for i in range(pre_x-1,pre_x+2,2):
            if 0 <= i <= w-1 and tizu[pre_y][i] == '.':
                tansaku.append([pre_y,i])
                kyori[pre_y][i] = min(kyori[pre_y][i],kyori[pre_y][pre_x]+1)
        for j in range(pre_y-1,pre_y+2,2):
            if 0 <= j <= h-1 and tizu[j][pre_x] == '.':
                tansaku.append([j,pre_x])
                kyori[j][pre_x] = min(kyori[j][pre_x],kyori[pre_y][pre_x]+1)
        visited[pre_y].add(pre_x)
    return kyori

h,w = nm()
tizu = []
sharp = []
saitan = [[10**10]*w for _ in range(h)]
for i in range(h):
    temp = list(input())
    s_temp = [[i,j] for j in range(w)  if temp[j] == '#' ]
    tizu.append(temp)
    sharp += s_temp
for i,j in sharp:
    saitan[i][j] = 0 
for i in sharp:
    saitan = bfs(i,saitan)
print(max((max(i) for i in saitan)))