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:
H,W = list(map(int,input().split()))
M = []
for i in range(H):
    M.append(list(input()))

Bs = []
for i in range(H):
    for j in range(W):
        if M[i][j]=="#":
            Bs.append([i,j])

from collections import deque
memo = [[float("inf")] * W for i in range(H)]
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
que = deque([])
que.append(Bs)
for Bi,Bj in Bs:
    memo[Bi][Bj] = 0

while que:
    ps = que.popleft()
    next = []
    for p in ps:
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            if (0<=nx<W)and(0<=ny<H)and(memo[ny][nx]==float("inf")):
                next.append((ny, nx))
                memo[ny][nx] = memo[p[0]][p[1]] + 1
    if len(next)>0:
        que.append(next)

out = 0
for i in range(H):
    for j in range(W):
        if memo[i][j]>out:
            out = memo[i][j]
print(out)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

H, W = map(int,input().split())

INF = -1
Gmap = [list(input()) for _ in range(H)]
next_q = deque([])

def dfs_settings():
    #複数
    for h in range(H):
        for w in range(W):
            if Gmap[h][w]=='#':
                next_q.append([h,w])
                Gmap[h][w]=0

def dfs():
    ret = 0
    while len(next_q)!=0:
        #スタック取り出し(先頭)幅優先
        h,w = next_q.popleft()
        lv=Gmap[h][w]+1
        hs, ws = h + 0 , w + 1
        if ws<W and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h + 1 , w + 0
        if hs<H and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h + 0 , w - 1
        if ws>=0 and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h - 1 , w + 0
        if hs>=0 and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
    return ret

def main():
    dfs_settings()
    ret = dfs()
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

H, W = map(int,input().split())

INF = -1
Gmap = [list(input()) for _ in range(H)]
next_q = deque([])

def dfs_settings():
    #複数
    for h in range(H):
        for w in range(W):
            if Gmap[h][w]=='#':
                next_q.append([h,w])
                Gmap[h][w]=0

def dfs():
    ret = 0
    while len(next_q)!=0:
        #スタック取り出し(先頭)幅優先
        h,w = next_q.popleft()
        hs, ws = h + 0 , w + 1
        if ws<W and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = Gmap[h][w] + 1
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h + 1 , w + 0
        if hs<H and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = Gmap[h][w] + 1
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h + 0 , w - 1
        if ws>=0 and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = Gmap[h][w] + 1
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h - 1 , w + 0
        if hs>=0 and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = Gmap[h][w] + 1
            ret = max(ret, Gmap[hs][ws])
    return ret

def main():
    dfs_settings()
    ret = dfs()
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

H, W = map(int,input().split())
sth, stw = 0, 0
glh, glw = H-1, W-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
Dist = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
next_q = deque([])

def dfs_settings():
    #複数
    for h in range(H):
        for w in range(W):
            if Gmap[h][w]=='#':
                next_q.append([h,w])
                Dist[h][w]=0

def dfs():
    ret = 0
    while len(next_q)!=0:
        #スタック取り出し(先頭)幅優先
        h,w = next_q.popleft()
        hs, ws = h + 0 , w + 1
        if ws<W and Gmap[hs][ws]=='.' and Dist[hs][ws]==INF:
            next_q.append([hs,ws])
            Dist[hs][ws] = Dist[h][w] + 1
            ret = max(ret, Dist[hs][ws])
        hs, ws = h + 1 , w + 0
        if hs<H and Gmap[hs][ws]=='.' and Dist[hs][ws]==INF:
            next_q.append([hs,ws])
            Dist[hs][ws] = Dist[h][w] + 1
            ret = max(ret, Dist[hs][ws])
        hs, ws = h +0 , w - 1
        if ws>=0 and Gmap[hs][ws]=='.' and Dist[hs][ws]==INF:
            next_q.append([hs,ws])
            Dist[hs][ws] = Dist[h][w] + 1
            ret = max(ret, Dist[hs][ws])
        hs, ws = h - 1 , w + 0
        if hs>=0 and Gmap[hs][ws]=='.' and Dist[hs][ws]==INF:
            next_q.append([hs,ws])
            Dist[hs][ws] = Dist[h][w] + 1
            ret = max(ret, Dist[hs][ws])
    return ret

def main():
    dfs_settings()
    ret = dfs()
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

H, W = map(int,input().split())
sth, stw = 0, 0
glh, glw = H-1, W-1
#sth,stw = list(map(int,input().split()))
#sth, stw = sth-1, stw-1
#glh, glw = list(map(int,input().split()))
#glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
Dist = [[INF]*W for _ in range(H)]
#direc = [[1,0], [-1,0], [0,1], [0,-1]]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
next_q = deque([])

def dfs_settings():
    #複数
    for h in range(H):
        for w in range(W):
            if Gmap[h][w]=='#':
                next_q.append([h,w])
                Dist[h][w]=0

def dfs():
    ret = 0
    while len(next_q)!=0:
        #スタック取り出し(先頭)幅優先
        h,w = next_q.popleft()
        for d in direc:
            hs, ws = h + d[0], w + d[1]
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and Dist[hs][ws]==INF:
                next_q.append([hs,ws])
                Dist[hs][ws] = Dist[h][w] + 1
                ret = max(ret, Dist[hs][ws])
    return ret

def main():
    dfs_settings()
    ret = dfs()
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

INF = -1
H, W = map(int,input().split())
Gmap = [list(input()) for _ in range(H)]
Dist = [[INF]*W for _ in range(H)]
direc = [[1,0], [-1,0], [0,1], [0,-1]]

def dfs():
    q = deque([])
    for h in range(H):
        for w in range(W):
            if Gmap[h][w]=='#':
                q.append([h,w])
                Dist[h][w]=0
    while len(q)!=0:
        #スタック取り出し(先頭)幅優先
        h,w = q.popleft()
        for d in direc:
            hs, ws = h + d[0], w + d[1]
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and Dist[hs][ws]==INF:
                q.append([hs,ws])
                Dist[hs][ws] = Dist[h][w] + 1

def main():
    dfs()
    print(max([max(Dist[h]) for h in range(H)]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
Q = deque()
h = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            Q.append([i, j])
        else:
            h += 1
Qtmp = deque()

yudrl = [0, 1, 0, -1]
xudrl = [1, 0, -1, 0]

c = 0
while h > 0:
    c += 1
    while len(Q) > 0:
        Qtmp.append(Q.pop())
    while len(Qtmp) > 0:
        q = Qtmp.pop()

        for i in range(4):
            y = q[0] + yudrl[i]
            x = q[1] + xudrl[i]

            if y < 0 or y > H - 1 or x < 0 or x > W - 1:
                continue
            if A[y][x] == '#':
                continue
            A[y][x] = '#'
            h -= 1
            Q.append([y, x])
print(c)

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])
Qtmp = deque()

yudrl = [0, 1, 0, -1]
xudrl = [1, 0, -1, 0]

c = 0
while len(Q) > 0:
    c += 1
    while len(Q) > 0:
        Qtmp.append(Q.pop())
    while len(Qtmp) > 0:
        q = Qtmp.pop()

        for i in range(4):
            y = q[0] + yudrl[i]
            x = q[1] + xudrl[i]

            if y < 0 or y > H - 1 or x < 0 or x > W - 1:
                continue
            if A[y][x] == '#':
                continue
            A[y][x] = '#'
            Q.append([y, x])
print(c - 1)

Submission status: Time Limit Exceeded

Solution code:
import collections
INF = 10**18
def bfs(starth,startw):
    d = [[-1]*w for i in range(h)]
    d[starth][startw] = 0
    q = collections.deque([])
    q.append((starth,startw))
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    while q:
        p = q.popleft()
        nowh = p[0]
        noww = p[1]
        for i in range(4):
            nexth = nowh + dy[i]
            nextw = noww + dx[i]
            if 0<=nextw<w and 0<=nexth<h:
                if d[nexth][nextw] == -1 and li[nexth][nextw] != "#":
                    q.append([nexth,nextw])
                    d[nexth][nextw] = d[nowh][noww] + 1
    return d
h,w = map(int,input().split())
li = [list(input()) for i in range(h)]
cost = [[INF]*w for i in range(h)]
koho = []
for i in range(h):
    for j in range(w):
        if li[i][j] == "#":
            koho.append([i,j])
for i in range(len(koho)):
    starth = koho[i][0]
    startw = koho[i][1]
    a = bfs(starth,startw)
    for j in range(h):
        for k in range(w):
            cost[j][k] = min(cost[j][k],a[j][k])

ans = -1
for i in range(h):
    for j in range(w):
        ans = max(cost[i][j],ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
INF = 10**18
h,w = map(int,input().split())
li = [list(input()) for i in range(h)]
koho = []
d = [[-1]*w for i in range(h)]
q = collections.deque([])
for i in range(h):
    for j in range(w):
        if li[i][j] == "#":
            d[i][j] = 0
            q.append([i,j])
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while q:
    p = q.popleft()
    y = p[0]
    x = p[1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<w and 0<=ny<h:
            if d[ny][nx] == -1:
                q.append([ny,nx])
                d[ny][nx] = d[y][x] + 1
ans = -1
for i in range(h):
    for j in range(w):
        ans = max(ans,d[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
INF = 10**18
def bfs(starth,startw):
    d = [[-1]*w for i in range(h)]
    d[starth][startw] = 0
    q = collections.deque([])
    q.append((starth,startw))
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    while q:
        p = q.popleft()
        nowh = p[0]
        noww = p[1]
        for i in range(4):
            nexth = nowh + dy[i]
            nextw = noww + dx[i]
            if 0<=nextw<w and 0<=nexth<h:
                if d[nexth][nextw] == -1 and li[nexth][nextw] != "#":
                    q.append([nexth,nextw])
                    d[nexth][nextw] = d[nowh][noww] + 1
    return d
h,w = map(int,input().split())
li = [list(input()) for i in range(h)]
cost = [[INF]*w for i in range(h)]
koho = []
for i in range(h):
    for j in range(w):
        if li[i][j] == "#":
            koho.append([i,j])
for i in range(len(koho)):
    starth = koho[i][0]
    startw = koho[i][1]
    a = bfs(starth,startw)
    for j in range(h):
        for k in range(w):
            cost[j][k] = min(cost[j][k],a[j][k])

ans = -1
for i in range(h):
    for j in range(w):
        ans = max(cost[i][j],ans)
print(ans)

Submission status: Time Limit Exceeded

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

H, W = map(int, input().split())
a = [list(input().rstrip()) for h in range(H)]
start = set()

for h in range(H):
  for w in range(W):
    if a[h][w] == '#':
      start.add((h, w))


def dfs(si, sj):
  di = [1, 0, -1, 0]
  dj = [0, 1, 0, -1]
  d = [[float('inf')]*W for h in range(H)]
  d[si][sj] = 0
  a[si][sj] = '#'
  np = deque()
  for i in range(4):
    ni = si + di[i]
    nj = sj + dj[i]
    if 0 <= ni < H and 0 <= nj < W and a[ni][nj] != '#' and d[ni][nj] == float('inf'):
      np.append((ni, nj))
      d[ni][nj] = d[si][sj] + 1
  return np

n = 0

def dfs2(sp):
  global n
  ns = set()
  for s in sp:
    for p in dfs(s[0], s[1]):
      ns.add(p)
  if len(ns) > 0:
    n += 1
    dfs2(ns)

dfs2(start)
print(n)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
a = []
queue = deque([])
dist = [[-1 for j in range(W)] for i in range(H)]
for i in range(H):
    inp = input()
    a.append(inp)
    for j in range(W):
        if inp[j] == "#":
            queue.append([i,j])
            dist[i][j] = 0
dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]
ans = 0
while len(queue) != 0:
    now = queue.popleft()
    h = now[0]
    w = now[1]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        elif dist[nh][nw] == -1:
            dist[nh][nw] = dist[h][w] +1
            ans = max(dist[nh][nw], ans)
            queue.append([nh, nw])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
a = []
for _ in range(H):
    a.append(input())
queue = deque([])
dist = [[-1 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if a[i][j] == "#":
            queue.append([i,j])
            dist[i][j] = 0
dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]
while len(queue) != 0:
    now = queue.popleft()
    h = now[0]
    w = now[1]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        elif dist[nh][nw] == -1:
            dist[nh][nw] = dist[h][w] +1
            queue.append([nh, nw])
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:
from copy import deepcopy
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

M = []
vx = [0,1,0,-1]
vy = [1,0,-1,0]
H = 0
W = 0

def main():
    global M,H,W
    H,W = map(int, input().split())  
    for i in range(H):
        M.append(list(input()))
    cnt = 0
    while True:
        OKflag = True
        
        for i in range(H):
            for j in range(W):
                if M[i][j] == '.':
                    OKflag = False
                    break

        if OKflag:
            print(cnt)
            return 

        last = cnt -1
        if last == -1 :
            last = '#'
        

        for i in range(H):
            for j in range(W):
                if M[i][j] == last:
                    if i-1>=0:
                        if M[i-1][j] == '.':
                            M[i-1][j] = cnt
                    if i+1<H:
                        if M[i+1][j] == '.':
                            M[i+1][j] = cnt
                    if j-1>=0:
                        if M[i][j-1] == '.':
                            M[i][j-1] = cnt
                    if j+1<W:
                        if M[i][j+1] == '.':
                            M[i][j+1] = cnt
        cnt += 1


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

M = []
vx = [0,1,0,-1]
vy = [1,0,-1,0]
H = 0
W = 0

def main():
    global M,H,W
    H,W = map(int, input().split())  
    for i in range(H):
        M.append(list(input()))
    print(bfs(0))


def bfs(cnt):
    global M,vx,vy,H,W
    OKflag = True
    
    for i in range(H):
        for j in range(W):
            if M[i][j] == '.':
                OKflag = False
                break

    if OKflag:
        return cnt

    last = cnt -1
    if last == -1 :
        last = '#'
    

    for i in range(H):
        for j in range(W):
            if M[i][j] == last:
                if i-1>=0:
                    if M[i-1][j] == '.':
                        M[i-1][j] = cnt
                if i+1<H:
                    if M[i+1][j] == '.':
                        M[i+1][j] = cnt
                if j-1>=0:
                    if M[i][j-1] == '.':
                        M[i][j-1] = cnt
                if j+1<W:
                    if M[i][j+1] == '.':
                        M[i][j+1] = cnt
    return bfs(cnt+1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

M = []
vx = [0,1,0,-1]
vy = [1,0,-1,0]
H = 0
W = 0

def main():
    global M,H,W
    H,W = map(int, input().split())  
    for i in range(H):
        M.append(list(input()))
    print(bfs(0))


def bfs(cnt):
    global M,vx,vy,H,W
    OKflag = True
    for i in range(H):
        for j in range(W):
            if M[i][j] == '.':
                OKflag = False

    if OKflag:
        return cnt

    last = cnt -1
    if last == -1 :
        last = '#'

    for i in range(H):
        for j in range(W):
            if M[i][j] == last:
                for k in range(len(vx)):
                    if i+vx[k]>=0 and i+vx[k]<H and j+vy[k]>=0 and j+vy[k] < W and last == M[i][j]:
                        if M[i+vx[k]][j+vy[k]] == '.':
                            M[i+vx[k]][j+vy[k]] = cnt
    return bfs(cnt+1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

M = []
MD = []
vx = [0,1,0,-1]
vy = [1,0,-1,0]
H = 0
W = 0

def main():
    global M,H,W
    H,W = map(int, input().split())  
    for i in range(H):
        M.append(list(input()))
    print(bfs(0))


def bfs(cnt):
    global M,MD,vx,vy,H,W
    OKflag = True
    for i in range(H):
        for j in range(W):
            if M[i][j] == '.':
                OKflag = False

    if OKflag:
        return cnt
    MD = deepcopy(M)

    for i in range(H):
        for j in range(W):
            if M[i][j] == '#':
                for k in range(len(vx)):
                    if i+vx[k]>=0 and i+vx[k]<H and j+vy[k]>=0 and j+vy[k] < W:
                        MD[i+vx[k]][j+vy[k]] = '#'
    M = MD
    return bfs(cnt+1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
import sys
sys.setrecursionlimit(10 ** 6)

M = []
MD = []
vx = [0,1,0,-1]
vy = [1,0,-1,0]
H = 0
W = 0

def main():
    global M,H,W
    H,W = map(int, input().split())  
    for i in range(H):
        M.append(list(input()))
    print(bfs(0))


def bfs(cnt):
    global M,MD,vx,vy,H,W
    OKflag = True
    for i in range(H):
        for j in range(W):
            if M[i][j] == '.':
                OKflag = False

    if OKflag:
        return cnt
    MD = deepcopy(M)

    for i in range(H):
        for j in range(W):
            if M[i][j] == '#':
                for k in range(len(vx)):
                    if i+vx[k]>=0 and i+vx[k]<H and j+vy[k]>=0 and j+vy[k] < W:
                        MD[i+vx[k]][j+vy[k]] = '#'
    M = deepcopy(MD)
    return bfs(cnt+1)
    




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
u = [list(input()) for _ in range(h)]
from collections import deque
q = deque([])
dist = [[-1 for i in range(w)] for j in range(h)]
for i in range(h):
    for j in range(w):
        if u[i][j]=='#':
            q.append((i,j))
            dist[i][j]=0

while q:
    (i,j) = q.popleft()
    if 0<=i-1<h:
        if u[i-1][j]=='.' and dist[i-1][j]==-1:
            u[i-1][j]='#'
            q.append((i-1,j))
            dist[i-1][j]=dist[i][j]+1
    if 0<=i+1<h:
        if u[i+1][j]=='.' and dist[i+1][j]==-1:
            u[i+1][j]='#'
            q.append((i+1,j))
            dist[i+1][j]=dist[i][j]+1
    if 0<=j-1<w:
        if u[i][j-1]=='.' and dist[i][j-1]==-1:
            u[i][j-1]='#'
            q.append((i,j-1))
            dist[i][j-1]=dist[i][j]+1
    if 0<=j+1<w:
        if u[i][j+1]=='.' and dist[i][j+1]==-1:
            u[i][j+1]='#'
            q.append((i,j+1))
            dist[i][j+1]=dist[i][j]+1

z=[]
for b in dist:
    z.append(max(b))

print(max(z))

Submission status: Time Limit Exceeded

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

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

d = [[10**4] * w for i in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

que = deque([])
for i in range(h):
  for j in range(w):
    if c[i][j] == '#':
      que.append((i,j,0))
      d[i][j] = 0

ans = 0
while que:
  p = que.popleft()
  for i in range(4):
      nw = p[1] + dx[i]
      nh = p[0] + dy[i]
      if 0 <= nw < w and 0 <= nh < h and p[2] < d[nh][nw]:
          que.append((nh,nw,p[2]+1))
          d[nh][nw] = p[2]+1
          ans = max(ans,p[2]+1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

cnt=0

itta=[[float('inf')]*w for i in range(h)]

d=deque()
aaa=d.append
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            aaa([i,j])
            itta[i][j]=0

# print(d)
# print(itta)

while d:
    cnt+=1
    for l in range(len(d)):
        nh,nw=d.popleft()
        for i in range(4):
            d1,d2=direction[i]
            if 0<=nh+d1<h and 0<=nw+d2<w:
                if itta[nh+d1][nw+d2]==float('inf'):
                    itta[nh+d1][nw+d2]=cnt
                    aaa([nh+d1,nw+d2])
    # print(d)

# print(itta)
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

cnt=0

itta=[[float('inf')]*w for i in range(h)]

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

# print(d)
# print(itta)
while d:
    cnt+=1
    for l in range(len(d)):
        nh,nw=d.popleft()
        for i in range(4):
            d1,d2=direction[i]
            if 0<=nh+d1<h and 0<=nw+d2<w:
                if itta[nh+d1][nw+d2]==float('inf'):
                    itta[nh+d1][nw+d2]=cnt
                    d.append([nh+d1,nw+d2])
    # print(d)

# print(itta)
print(cnt-1)

Submission status: Time Limit Exceeded

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

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

def bfs(sh,sw):
    d = [[False] * w for i in range(h)]

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

    que = deque([])
    que.append((sh,sw,0))
    d[sh][sw] = True
    chk = False
    while que:
        p = que.popleft()
        if c[p[0]][p[1]] == '#':
            a = p[2]
            break
        for i in range(4):
            nw = p[1] + dx[i]
            nh = p[0] + dy[i]
            
            if 0 <= nw < w and 0 <= nh < h and c[nh][nw] == '#':
                chk = True
                a = p[2] + 1
            elif 0 <= nw < w and 0 <= nh < h and d[nh][nw] == False:
                que.append((nh,nw,p[2]+1))
                d[nh][nw] = True
        if chk:
          break
    return a
  
ans = 0
for i in range(h):
  for j in range(w):
    res = bfs(i,j)
    ans = max(ans,res)
print(ans)

Submission status: Time Limit Exceeded

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

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

def bfs(sh,sw):
    d = [[False] * w for i in range(h)]

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

    que = deque([])
    que.append((sh,sw,0))
    d[sh][sw] = True

    while que:
        p = que.popleft()
        if c[p[0]][p[1]] == '#':
            break
        for i in range(4):
            nw = p[1] + dx[i]
            nh = p[0] + dy[i]

            if 0 <= nw < w and 0 <= nh < h and d[nh][nw] == False:
                que.append((nh,nw,p[2]+1))
                d[nh][nw] = True
    return p[2]
  
ans = 0
for i in range(h):
  for j in range(w):
    res = bfs(i,j)
    ans = max(ans,res)
print(ans)

Submission status: Time Limit Exceeded

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

def bfs(sh,sw):
    d = [[False] * w for i in range(h)]

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

    que = deque([])
    que.append((sh,sw,0))
    d[sh][sw] = True

    while que:
        p = que.popleft()
        if c[p[0]][p[1]] == '#':
            break
        for i in range(4):
            nw = p[1] + dx[i]
            nh = p[0] + dy[i]

            if 0 <= nw < w and 0 <= nh < h and d[nh][nw] == False:
                que.append((nh,nw,p[2]+1))
                d[nh][nw] = True
    return p[2]
  
ans = 0
for i in range(h):
  for j in range(w):
    res = bfs(i,j)
    ans = max(ans,res)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

Map = [[-1] * W for i in range(H)]

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

ans = 0
while d:
  x, y = d.popleft()
  dist = Map[x][y]
  for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
    u, v = x + dx, y + dy
    if 0<=u<H and 0<=v<W and Map[u][v]==-1:
      Map[u][v] = dist + 1
      ans = max(ans, dist + 1)
      d.append([u, v])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
H,W=map(int,input().split())
A=[input() for _ in range(H)]
q=deque()
dist=[[-1]*W for i in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j]=='#':
            dist[i][j]=0
            q.append((i,j))
while q:
    h,w=q.popleft()
    d=dist[h][w]
    for dh,dw in ((1,0),(-1,0),(0,1),(0,-1)):
        new_h=h+dh
        new_w=w+dw
        if new_h<0 or H<=new_h or new_w<0 or W<=new_w:
            continue
        if dist[new_h][new_w]==-1:
            dist[new_h][new_w]=d+1
            q.append((new_h,new_w))
print(d)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

def agc033_a():
    H, W = map(int, readline().split())
    dist = [[-1] * W for _ in range(H)]
    que = deque()
    for i, ln in enumerate(read().split()):
        for j, c in enumerate(ln.strip().decode('UTF-8')):
            if c == '#':
                que.append((i, j))
                dist[i][j] = 0

    while que:
        x, y = que.popleft()
        for i, j in ((x-1, y), (x, y-1), (x, y+1), (x+1, y)):
            if i < 0 or H-1 < i or j < 0 or W-1 < j: continue
            if dist[i][j] != -1: continue
            dist[i][j] = dist[x][y] + 1
            que.append((i, j))

    ans = 0
    for row in dist:
        ans = max(max(row), ans)
    print(ans)

agc033_a()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque
import numpy as np

def agc033_a():
    H, W = map(int, readline().split())
    grid = np.full((H+2, W+2), '#', dtype=object)
    for i, ln in enumerate(read().split()):
        grid[i+1, 1:W+1] = [str(x) for x in ln.strip().decode('UTF-8')]

    que = deque()
    dist = np.ones((H+2, W+2), dtype=int)
    dist *= -1

    for i in range(1, H+1):
        for j in range(1, W+1):
            if grid[i, j] == '#':
                que.append((i, j))
                dist[i, j] = 0

    while que:
        x, y = que.popleft()
        for i, j in ((x-1, y), (x, y-1), (x, y+1), (x+1, y)):
            if grid[i, j] == '#': continue
            if dist[i, j] != -1: continue
            dist[i, j] = dist[x, y] + 1
            que.append((i, j))

    ans = dist.max()
    print(ans)

agc033_a()

Submission status: Time Limit Exceeded

Solution code:
# A - Darker and Darker
import numpy as np

H,W = map(int,input().split())
B = np.full((H,W),-1,dtype=int)

queue = []

for i in range(H):
    A = input()
    for j in range(W):
        if A[j]=='#':
            B[i][j] = 0
            queue.append((i,j))

while queue!=[]:
    I,J = queue.pop(0)
    for i,j in [(I-1,J),(I+1,J),(I,J-1),(I,J+1)]:
        if i>=0 and i<H and j>=0 and j<W and B[i][j]<0:
            B[i][j] = B[I][J]+1
            queue.append((i,j))

print(np.max(B))

Submission status: Time Limit Exceeded

Solution code:
# A - Darker and Darker
import numpy as np

H,W = map(int,input().split())
h,w = np.arange(H,dtype=int),np.arange(W,dtype=int)
B = -1 * np.ones((H,W),dtype=int)

queue = []

for i in h:
    A = input()
    for j in w:
        if A[j]=='#':
            B[i][j] = 0
            queue.append((i,j))

while queue!=[]:
    I,J = queue.pop(0)
    for i,j in [(I-1,J),(I+1,J),(I,J-1),(I,J+1)]:
        if (i in h) and (j in w) and B[i][j]<0:
            B[i][j] = B[I][J]+1
            queue.append((i,j))

print(np.max(B))