Problem:


Score : 300 points

Problem Statement

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

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

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

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

Constraints

1 \leq H,W \leq 1000

A_{ij} is # or ..

The given grid has at least one black square.

Input

Input is given from Standard Input in the following format:

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

Output

Print the number of operations that will be performed.

Sample Input 1

3 3
...
.#.
...

Sample Output 1

2

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

Sample Input 2

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

Sample Output 2

3



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


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
import queue
q = queue.Queue()
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
x=[[-1,0],[1,0],[0,-1],[0,1]]
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            a[i][j]=0
            for k in x:
                if 0<=i+k[0]<h and 0<=j+k[1]<w and a[i+k[0]][j+k[1]]==".":
                    a[i+k[0]][j+k[1]]=1
                    q.put([i+k[0],j+k[1],1])
ans=0
while not q.empty():
    v=q.get()
    for k in x:
        if 0<=v[0]+k[0]<h and 0<=v[1]+k[1]<w and a[v[0]+k[0]][v[1]+k[1]]==".":
            a[v[0]+k[0]][v[1]+k[1]]=v[2]+1
            q.put([v[0]+k[0],v[1]+k[1],v[2]+1])
            ans=v[2]+1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

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

def bfs(x, y):

    cnt = 0
    Q = queue.Queue()
    check = [[True for i in range(W)] for j in range(H)]
    
    Q.put((x, y, cnt))
    while Q.qsize() > 0:
        x, y , cnt = Q.get()
        for i in range(4):
            if 0 <= x + dx[i] < H and 0 <= y + dy[i] < W and check[x + dx[i]][y + dy[i]]:
                check[x + dx[i]][y + dy[i]] = False
                if field[x + dx[i]][y + dy[i]] == "#":
                    return cnt + 1
                else:
                    Q.put((x + dx[i], y + dy[i], cnt + 1))
                    
    return -1

nums=list(map(int,input().split()))
H = nums[0]
W = nums[1]


field = [[None for i in range(W)] for j in range(H)]

black = 0
sx = []
sy = []
for i in range(H):
    str1 = input()
    for j in range(W):
        field[i][j] = str1[j]
        if str1[j] == ".":
            sx.append(i)
            sy.append(j)
            
result = 0
for i in range(len(sx)):
    result = max(result, bfs(sx[i],sy[i]))

print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to only numbers
rs = lambda: stdin.readline().rstrip()  # ignores trailing space

H, W = rl()
A = [list(rs()) for _ in range(H)]
answer = 0
que = deque()
data = [[-1] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            data[i][j] = 0
            que.append((j, i))
while que:
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    p = que.popleft()
    for i in range(4):
        nx = p[0] + dx[i]
        ny = p[1] + dy[i]
        if 0 <= ny <= H-1 and 0 <= nx <= W-1:
            if data[ny][nx] == -1:
                data[ny][nx] = data[p[1]][p[0]] + 1
                que.append((nx, ny))
answer = max([max(z) for z in data])
print(answer)
# 54

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to only numbers
rs = lambda: stdin.readline().rstrip()  # ignores trailing space


def bfs(x, y):
    d = [[None] * W for _ in range(H)]
    d[y][x] = 0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque()
    que.append((x, y))

    while que:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]                
            if 0 <= ny and ny <= H-1 and 0 <= nx and nx <= W-1:
                if A[ny][nx] == '#':
                    return d[p[1]][p[0]] + 1
                if A[ny][nx] == '.' and d[ny][nx] == None:
                    d[ny][nx] = d[p[1]][p[0]] + 1
                    que.append((nx, ny))

H, W = rl()
A = [list(rs()) for _ in range(H)]
answer = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == '.':
            r = bfs(i, j)
            answer = max(answer, r)

print(answer)
# 54

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to only numbers
rs = lambda: stdin.readline().rstrip()  # ignores trailing space

def F(grid):
    def black(x, y):
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= ny and ny <= H-1 and 0 <= nx and nx <= W-1 and \
                    grid[ny][nx] == '.':
                grid[ny][nx] = '#'
                data[ny][nx] = 'Visited'

    data = [[None] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '#' and data[i][j] == None:
                black(i, j)
    
    return grid

H, W = rl()
A = [list(rs()) for _ in range(H)]
answer = 0
while True:
    if all([x.count('.')==0 for x in A]):
        break
    A = F(A)
    answer += 1

print(answer)
# 54

Submission status: Time Limit Exceeded

Solution code:
H, W =  map(int, input().split(' '))
table = [list(input()) for _ in range(H)]

buf = []

for i in range(H):
    for j in range(W):
        if table[i][j] == '#':
            buf.append((i, j))


ans = 0
while True:
    n = sum([row.count('#') for row in table])
    if n == H * W:
        break


    buf2 = []
    for i, j in buf:
        if i-1 >= 0 and table[i-1][j] != '#':
            table[i - 1][j] = '#'
            buf2.append((i-1, j))

        if i+1 < H and table[i+1][j] != '#':
            table[i + 1][j] = '#'
            buf2.append((i+1, j))

        if j-1 >= 0 and table[i][j-1] != '#':
            table[i][j-1] = '#'
            buf2.append((i, j-1))

        if j+1 < W and table[i][j+1] != '#':
            table[i][j+1] = '#'
            buf2.append((i, j+1))

    ans += 1
    buf = buf2


    # print('-- -- --')
    # print(buf)
    # for row in table:
    #     print(''.join(row))


print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
H, W =  map(int, input().split(' '))
table = [list(input()) for _ in range(H)]

buf = []

for i in range(H):
    for j in range(W):
        if table[i][j] == '#':
            buf.append((i, j))


ans = 0
while True:
    n = 0
    for i in range(H):
        for j in range(W):
            if table[i][j] == '#':
                n += 1
    if n == H * W:
        break


    buf2 = []
    for i, j in buf:
        if i-1 >= 0 and table[i-1][j] != '#':
            table[i - 1][j] = '#'
            buf2.append((i-1, j))

        if i+1 < H and table[i+1][j] != '#':
            table[i + 1][j] = '#'
            buf2.append((i+1, j))

        if j-1 >= 0 and table[i][j-1] != '#':
            table[i][j-1] = '#'
            buf2.append((i, j-1))

        if j+1 < W and table[i][j+1] != '#':
            table[i][j+1] = '#'
            buf2.append((i, j+1))

    ans += 1
    buf = buf2


    # print('-- -- --')
    # print(buf)
    # for row in table:
    #     print(''.join(row))


print(ans)

Submission status: Time Limit Exceeded

Solution code:
#A - Darker and Darker
import copy
import sys
from collections import deque
H,W = (int(i) for i in input().split())
s_tmp = []
for _ in range(H):
    s_tmp.append(list(input()))
d = [[1, 0], [-1, 0], [0, 1], [0, -1]]
q = deque()
s = copy.deepcopy(s_tmp)
flg = False
cnt = 0
dot_cnt = 1
while dot_cnt > 0:
    
    cnt += 1
    dot_cnt = 0
    for i in range(H):
        for j in range(W):
            if s[i][j] == '#':
                q.append([i,j])
            elif s[i][j] == '.':
                dot_cnt += 1

    while len(q) > 0:
        #print(q)
        node = q.popleft()#qから左端を取り出す(幅優先)
        if node is not None:
            y = node[0]
            x = node[1]
            #上下を探索して移動できるところをスタックする
            for dx, dy in d:
                nx, ny = x + dx, y + dy
                if not (0 <= nx < W and 0 <= ny < H) or s[ny][nx] == '#':
                    continue
                else:
                    tmp = [ny,nx]
                    #if s[ny][nx] != 'y':
                        #q.append(tmp)
                    s[ny][nx] = '#'
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

def main():
    input = sys.stdin.readline  
    H,W = map(int,input().split())
    isVisited = [[False]*W for _ in range(H)]
    queue = deque()

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

    answer = 0
    a =  [(0,1),(1,0),(-1,0),(0,-1)]
    while queue:
        i,j,count = queue.popleft()

        if not isVisited[i][j]:
            isVisited[i][j] = True
            if count>answer:
                answer = count
            for ix,iy in a:
                if 0<=i+ix<H and 0<=j+iy<W:
                    queue.append((i+ix,j+iy,count+1))
 
    print(answer)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

def main():
    input = sys.stdin.readline  
    H,W = map(int,input().split())
    isVisited = []
    queue = deque()

    for i in range(H):
        isVisited.append([-1]*W)
        st = input()
        for j in range(W):
            if st[j] == "#":
                queue.append((i,j,0))

    answer = 0
    a =  [(0,1),(1,0),(-1,0),(0,-1)]
    while queue:
        i,j,count = queue.popleft()

        if isVisited[i][j] == -1:
            isVisited[i][j] = count
            if count>answer:
                answer = count
            for ix,iy in a:
                if 0<=i+ix<H and 0<=j+iy<W:
                    queue.append((i+ix,j+iy,count+1))
 
    print(answer)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

def main():
    input = sys.stdin.readline  
    H,W = map(int,input().split())
    isVisited = [[-1]*W for _ in range(H)]
    from collections import deque
    queue = deque()

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

    answer = 0
    a =  [(0,1),(1,0),(-1,0),(0,-1)]
    while queue:
        i,j,count = queue.popleft()

        if isVisited[i][j] == -1:
            isVisited[i][j] = count
            if count>answer:
                answer = count
            for ix,iy in a:
                if 0<=i+ix<H and 0<=j+iy<W:
                    queue.append((i+ix,j+iy,count+1))
 
    print(answer)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

def main():
    input = sys.stdin.readline  
    H,W = map(int,input().split())
    isVisited = [[-1]*W for _ in range(H)]
    from collections import deque
    queue = deque()

    for i in range(H):
        st = list(input())
        for j in range(W):
            if st[j] == "#":
                queue.append((i,j,0))

    answer = 0
    while queue:
        i,j,count = queue.popleft()

        if isVisited[i][j] == -1:
            isVisited[i][j] = count
            if count>answer:
                answer = count
            for ix,iy in [(0,1),(1,0),(-1,0),(0,-1)]:
                if 0<=i+ix<H and 0<=j+iy<W:
                    queue.append((i+ix,j+iy,count+1))
 
    print(answer)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

def main():
    input = sys.stdin.readline  
    H,W = map(int,input().split())
    isVisited = [[-1]*W for _ in range(H)]
    from collections import deque
    queue = deque()

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

    answer = 0
    while queue:
        i,j,count = queue.popleft()

        if isVisited[i][j] == -1:
            isVisited[i][j] = count
            if count>answer:
                answer = count
            for ix,iy in [(0,1),(1,0),(-1,0),(0,-1)]:
                if 0<=i+ix<H and 0<=j+iy<W:
                    queue.append((i+ix,j+iy,count+1))
 
    print(answer)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

def main():
    input = sys.stdin.readline  
    H,W = map(int,input().split())
    isVisited = [[-1]*W for _ in range(H)]
    from collections import deque
    queue = deque()

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

    answer = 0
    while queue:
        i,j,count = queue.popleft()

        if 0<=i<H and 0<=j<W and isVisited[i][j] == -1:
            isVisited[i][j] = count
            if count>answer:
                answer = count
            for ix,iy in [(0,1),(1,0),(-1,0),(0,-1)]:
               queue.append((i+ix,j+iy,count+1))
 
    print(answer)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

def main():
    input = sys.stdin.readline  
    H,W = map(int,input().split())
    isVisited = [[-1]*W for _ in range(H)]
    from collections import deque
    queue = deque()

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

    while queue:
        i,j,count = queue.popleft()

        if 0<=i<H and 0<=j<W and isVisited[i][j] == -1:
            isVisited[i][j] = count
            for ix,iy in [(0,1),(1,0),(-1,0),(0,-1)]:
               queue.append((i+ix,j+iy,count+1))
 
    answer = 0
    for i in range(H):
        answer = max(answer,max(isVisited[i]))
    print(answer)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def main():
    H,W = map(int,input().split())
    isVisited = [[-1]*W for _ in range(H)]
    from collections import deque

    queue = deque()

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

    while queue:
        i,j,count = queue.popleft()

        if 0<=i<H and 0<=j<W and isVisited[i][j] == -1:
            isVisited[i][j] = count
            for ix,iy in [(0,1),(1,0),(-1,0),(0,-1)]:
               queue.append((i+ix,j+iy,count+1))
 
    answer = 0
    for i in range(H):
        answer = max(answer,max(isVisited[i]))
    print(answer)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())

MAP=[["." for i in range (W)]for i in range(H)]
LIST=[0]*10**7

l=0
r=0
for i in range(H):
    A=list(input())
    for j in range(W):
        if(A[j]=="#"):
            MAP[i][j]="#"
            LIST[r]=(i,j,0)
            r+=1

while(True):
    T=LIST[l]
    i=T[0]
    j=T[1]
    if(i>0):
        if(MAP[i-1][j]=="."):
            MAP[i-1][j]="#"
            LIST[r]=(i-1,j,T[2]+1)
            r+=1  
    if(i+1<H):
        if(MAP[i+1][j]=="."):
            MAP[i+1][j]="#"
            LIST[r]=(i+1,j,T[2]+1)
            r+=1  
    if(j>0):
        if(MAP[i][j-1]=="."):
            MAP[i][j-1]="#"
            LIST[r]=(i,j-1,T[2]+1)
            r+=1  
    if(j+1<W):
        if(MAP[i][j+1]=="."):
            MAP[i][j+1]="#"
            LIST[r]=(i,j+1,T[2]+1)
            r+=1
    l+=1
    if(r<=l):
        print(LIST[r-1][2])
        exit()

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())

MAP=[["." for i in range (W)]for i in range(H)]
LIST=[(0,0,0)]*10**8

l=0
r=0
for i in range(H):
    A=list(input())
    for j in range(W):
        if(A[j]=="#"):
            MAP[i][j]="#"
            LIST[r]=(i,j,0)
            r+=1

while(True):
    T=LIST[l]
    i=T[0]
    j=T[1]
    if(i>0):
        if(MAP[i-1][j]=="."):
            MAP[i-1][j]="#"
            LIST[r]=(i-1,j,T[2]+1)
            r+=1  
    if(i+1<H):
        if(MAP[i+1][j]=="."):
            MAP[i+1][j]="#"
            LIST[r]=(i+1,j,T[2]+1)
            r+=1  
    if(j>0):
        if(MAP[i][j-1]=="."):
            MAP[i][j-1]="#"
            LIST[r]=(i,j-1,T[2]+1)
            r+=1  
    if(j+1<W):
        if(MAP[i][j+1]=="."):
            MAP[i][j+1]="#"
            LIST[r]=(i,j+1,T[2]+1)
            r+=1
    l+=1
    if(r<=l):
        print(LIST[r-1][2])
        exit()

Submission status: Time Limit Exceeded

Solution code:
import copy
H,W=map(int,input().split())


MAP=[["." for i in range (W+2)]for i in range(H+2)]
tMAP=[["." for i in range (W+2)]for i in range(H+2)]

for i in range(H):
    A=list(input())
    for j in range(W):
        MAP[i+1][j+1]=A[j]
tMAP=copy.deepcopy(MAP)

c=0
while(True):
    k=0
    for i in range(1,H+1):
        for j in range(1,W+1):
            if(MAP[i][j]=="."):
                k=1
    if(k==0):
        break
    c+=1
    for i in range(1,H+1):
        for j in range(1,W+1):
            if(MAP[i][j]=="#"):
                tMAP[i-1][j]="#"
                tMAP[i+1][j]="#"
                tMAP[i][j-1]="#"
                tMAP[i][j+1]="#"
    MAP=copy.deepcopy(tMAP)
print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def solve():
    H, W = map(int, input().split())
    grid = [['' for _ in range(W)] for _ in range(H)]
    que = deque()
    for i in range(H):
        grid[i] = list(input())
        for j in range(W):
            if grid[i][j] == '#':
                que.append([i, j])
    
    xy = [[0, -1], [1, 0], [0, 1], [-1, 0]]
    ans = 0
    while que:
        n = len(que)
        for _ in range(n):
            y, x = que.popleft()
            for i in range(4):
                xi = x - xy[i][0]
                yi = y - xy[i][1]
                if 0 <= xi <= W-1 and 0 <= yi <= H-1:
                    if grid[yi][xi] == '.':
                        grid[yi][xi] = '#'
                        que.append([yi, xi])
        ans += 1
    print(ans-1)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int, input().split())
a = ["#"+input()+"#" for _ in range(h)]
s = "#"*(w+2)
a = [s] + a + [s]


ds = [[0] + [-1]*w + [0] for _ in range(h)]
ds = [[0]*(w+2)] + ds + [[0]*(w+2)]

vectors = [(-1,0),(1,0),(0,-1),(0,1)]

stack = []

ans = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if a[i][j] == "#":
            stack.append((i,j))
            ds[i][j] = 0

while stack:
    nh,nw = stack.pop(0)
    for vh,vw in vectors:
        if ds[nh+vh][nw+vw] == -1:
            stack.append((nh+vh,nw+vw))
            ds[nh+vh][nw+vw] = ds[nh][nw] + 1
            ans = ds[nh][nw] + 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int, input().split())
a = ["#"+input()+"#" for _ in range(h)]
s = "#"*(w+2)
a = [s] + a + [s]


ds = [[0] + [-1]*w + [0] for _ in range(h)]
ds = [[0]*(w+2)] + ds + [[0]*(w+2)]

vectors = set([(-1,0),(1,0),(0,-1),(0,1)])

stack = []

ans = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if a[i][j] == "#":
            stack.append((i,j))
            ds[i][j] = 0

while stack:
    nh,nw = stack.pop(0)
    for vh,vw in vectors:
        if ds[nh+vh][nw+vw] == -1:
            stack.append((nh+vh,nw+vw))
            ds[nh+vh][nw+vw] = ds[nh][nw] + 1
            ans = ds[nh][nw] + 1

print(ans)

Submission status: Time Limit Exceeded

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

ds = [[-1]*w for _ in range(h)]

vectors = set([(-1,0),(1,0),(0,-1),(0,1)])

stack = []

ans = 0

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

while stack:
    nh,nw = stack.pop(0)
    for vh,vw in vectors:
        if nh+vh>=0 and nh+vh<h and nw+vw>=0 and nw+vw<w:
            if ds[nh+vh][nw+vw] == -1:
                stack.append((nh+vh,nw+vw))
                ds[nh+vh][nw+vw] = ds[nh][nw] + 1
                ans = ds[nh][nw] + 1

print(ans)

Submission status: Time Limit Exceeded

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

ds = [[-1]*w for _ in range(h)]

vectors = [(-1,0),(1,0),(0,-1),(0,1)]

stack = []

ans = 0

visited = [[False]*w for _ in range(h)]

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

while stack:
    nh,nw = stack.pop(0)
    for vh,vw in vectors:
        if nh+vh>=0 and nh+vh<h and nw+vw>=0 and nw+vw<w:
            if ds[nh+vh][nw+vw] == -1:
                stack.append((nh+vh,nw+vw))
                ds[nh+vh][nw+vw] = ds[nh][nw] + 1
                ans = ds[nh][nw] + 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections as cl

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

ds = [[-1]*w for _ in range(h)]

vectors = [(-1,0),(1,0),(0,-1),(0,1)]

stack = cl.deque([])

ans = 0

visited = [[False]*w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            stack.appendleft((i,j))
            ds[i][j] = 0

while stack:
    nh,nw = stack.pop()
    for vh,vw in vectors:
        if nh+vh>=0 and nh+vh<h and nw+vw>=0 and nw+vw<w:
            if ds[nh+vh][nw+vw] == -1:
                stack.appendleft((nh+vh,nw+vw))
                ds[nh+vh][nw+vw] = ds[nh][nw] + 1
                ans = ds[nh][nw] + 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
mat = []
alr = [[-1 for i in range(W)] for j in range(H)]
que = deque()
for i in range(H):
    mat.append(list(input()))
    for j in range(W):
        if mat[i][j] == '#':
            alr[i][j] = 0
            que.append([i,j])

x1 = [0,0,1,-1]
y1 = [1,-1,0,0]
count = 0
while que:
    q = que.popleft()
    for i in range(4):
        if (0 <= q[0]+x1[i] <= H-1) and (0 <= q[1]+y1[i] <= W-1):
            if mat[q[0]+x1[i]][q[1]+y1[i]] == '.' and alr[q[0]+x1[i]][q[1]+y1[i]] == -1:
                alr[q[0]+x1[i]][q[1]+y1[i]] = alr[q[0]][q[1]] + 1
                count = max(count,alr[q[0]][q[1]] + 1)
                que.append([q[0]+x1[i],q[1]+y1[i]])
                mat[q[0]+x1[i]][q[1]+y1[i]] = '#'

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
mat = []
alr = [[-1 for i in range(W)] for j in range(H)]
que = deque()
for i in range(H):
    mat.append(list(input()))
    for j in range(W):
        if mat[i][j] == '#':
            alr[i][j] = 0
            que.append([i,j])

x1 = [0,0,1,-1]
y1 = [1,-1,0,0]
count = 0
while que:
    q = que.popleft()
    for i in range(4):
        if (0 <= q[0]+x1[i] <= H-1) and (0 <= q[1]+y1[i] <= W-1):
            if mat[q[0]+x1[i]][q[1]+y1[i]] == '.' and alr[q[0]+x1[i]][q[1]+y1[i]] == -1:
                alr[q[0]+x1[i]][q[1]+y1[i]] = alr[q[0]][q[1]] + 1
                que.append([q[0]+x1[i],q[1]+y1[i]])
                mat[q[0]+x1[i]][q[1]+y1[i]] = '#'
maxa = 0
for i in alr:
    for j in i:
        maxa = max(maxa,j)
print(maxa)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W=map(int,input().split())
if H==1 and W==1:
    print(0)
    exit()

A=[]
B=deque([])
C=[[-1]*W for i in range(H)]
cnt=0
for h in range(H):
    temp=list(input())
    A.append(temp)
    for w in range(W):
        if A[h][w]=="#":
            B.append([h,w,0])
            C[h][w]=0
            cnt+=1


step=[[1,0],[-1,0],[0,1],[0,-1]]
ans=[]
while B:
    P=B.popleft()
    for x,y in step:
        if 0<=P[0]+y<=H-1 and 0<=P[1]+x<=W-1:
            if C[P[0]+y][P[1]+x]==-1:
                B.append([P[0]+y,P[1]+x,P[2]+1])
                C[P[0]+y][P[1]+x]=1
                ans.append(P[2]+1)
                cnt+=1
                if cnt==H*W:break

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int,input().split())
grid = [list(input()) for _ in range(H)]
w_cnt = 0
for i in range(H):
    w_cnt += grid[i].count('.')


d = [[-1]*W for _ in range(H)]
dx = [0,1,0,-1]
dy = [1,0,-1,0]


que = deque()
for x in range(W):
    for y in range(H):
        if grid[y][x] == '#':
            d[y][x] = 0
            que.append([x,y])

while len(que) != 0:
    p = que.popleft()
    for i in range(4):
        nx = p[0] + dx[i]
        ny = p[1] + dy[i]
        #print(nx,ny)
        if 0 <= nx <= W-1 and 0 <= ny <= H-1 and grid[ny][nx] == '.' and d[ny][nx] == -1:
            que.append([nx,ny])
            d[ny][nx] = d[p[1]][p[0]] + 1

# print(d)
# print(d[H-1][W-1])
res = 0
for x in range(W):
    for y in range(H):
        res = max(res,d[y][x])
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
h,w=map(int, input().split(' '))
a = [input() for i in range(h)]
nl = [[] for i in range(h)]
q = deque()
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            nl[i].append(0)
            q.append([i,j,0])
        else:
            nl[i].append(-1)
while q:
    [s,t,cnt] = q.popleft()
    if s>0 and nl[s-1][t] == -1:
        q.append([s-1,t,cnt+1])
        nl[s-1][t] = cnt+1
    if s<h-1 and nl[s+1][t] == -1:
        q.append([s+1,t,cnt+1])
        nl[s+1][t] = cnt+1
    if t>0 and nl[s][t-1] == -1:
        q.append([s,t-1,cnt+1])
        nl[s][t-1] = cnt+1
    if t<w-1 and nl[s][t+1] == -1:
        q.append([s,t+1,cnt+1])
        nl[s][t+1] = cnt+1
ans = 0
for i in range(h):
    ans = max(ans,max(nl[i]))
print(ans)

Submission status: Time Limit Exceeded

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

lst = []
H, W = map(int, input().split())
for _ in range(H):
    l = list(input())
    lst.append(l)

from collections import deque
yx =[[1,0], [-1, 0], [0,1], [0,-1]]

def bfs(sy, sx, gy, gx):
    queue = deque()
    visited = [[-1] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if lst[h][w] == '#':
                visited[h][w] = 0
                queue.append([h, w])            
    while queue:
        now = queue.popleft()
        if all([ not -1 in _ for _ in visited]):
            return max(sum(visited, []))
        for _ in yx:
            ny = now[0] + _[1]
            nx = now[1] + _[0]
            if 0 <= nx < W and 0 <= ny < H:
                if visited[ny][nx] == -1:
                    visited[ny][nx] = visited[now[0]][now[1]] + 1
                    queue.append([ny, nx])
    return -1

step = bfs(-1, -1, -1, -1)
print(step)

Submission status: Time Limit Exceeded

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

lst = []
H, W = map(int, input().split())
for _ in range(H):
    l = list(input())
    lst.append(l)

from collections import deque
x = [1, -1, 0, 0]
y = [0, 0, 1, -1]

def bfs():
    queue = deque()
    queue_append = queue.append
    visited = [[-1] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if lst[h][w] == '#':
                visited[h][w] = 0
                queue.append([h, w])            
    while queue:
        now = queue.popleft()
        if all([ not -1 in _ for _ in visited]):
            return max(sum(visited, []))
        for _ in range(4):
            ny = now[0] + y[_]
            nx = now[1] + x[_]
            if 0 <= nx < W and 0 <= ny < H:
                if visited[ny][nx] == -1:
                    visited[ny][nx] = visited[now[0]][now[1]] +1
                    queue_append([ny, nx])
    return -1

step = bfs()
print(step)

Submission status: Time Limit Exceeded

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

lst = []

H, W = map(int, input().split())
for _ in range(H):
    l = list(input())
    lst.append(l)

from collections import deque
x = [1, -1, 0, 0]
y = [0, 0, 1, -1]

def bfs(sy, sx, gy, gx):
    queue = deque()
    visited = [[-1 for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if lst[h][w] == '#':
                visited[h][w] = 0
                queue.append([h, w])            
    while queue:
        now = queue.popleft()
        if  sum([_.count(-1) for _ in visited]) == 0:
            return max(sum(visited, []))
        for _ in range(4):
            ny = now[0] + y[_]
            nx = now[1] + x[_]
            if 0 <= nx < W and 0 <= ny < H:
                if visited[ny][nx] == -1:
                    visited[ny][nx] = visited[now[0]][now[1]] +1
                    queue.append([ny, nx])
    return -1

step = bfs(-1,-1, -1, -1)
print(step)

Submission status: Time Limit Exceeded

Solution code:
lst = []
H, W = map(int, input().split())
for _ in range(H):
    l = list(input())
    lst.append(l)

from collections import deque
x = [1, -1, 0, 0]
y = [0, 0, 1, -1]

def bfs(sy, sx, gy, gx):
    queue = deque()
    queue_append = queue.append
    visited = [[-1 for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if lst[h][w] == '#':
                visited[h][w] = 0
                queue.append([h, w])            
    while queue:
        now = queue.popleft()
        if all([ not -1 in _ for _ in visited]):
            return max(sum(visited, []))
        for _ in range(4):
            ny = now[0] + y[_]
            nx = now[1] + x[_]
            if 0 <= nx < W and 0 <= ny < H:
                if visited[ny][nx] == -1:
                    visited[ny][nx] = visited[now[0]][now[1]] +1
                    queue_append([ny, nx])
    return -1

step = bfs(-1,-1, -1, -1)
print(step)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
INF=10**4
a=[[INF for j in range(W)] for i in range(H)]
for i in range(H):
  s=input()
  for j in range(len(s)):
    if s[j]=="#":
      a[i][j]=0

for i in range(H):
  for j in range(0,W-1):
    if a[i][j+1]>a[i][j]+1:
      a[i][j+1]=a[i][j]+1
for i in range(H-1,-1,-1):
  for j in range(W-1,0,-1):
    if a[i][j-1]>a[i][j]+1:
      a[i][j-1]=a[i][j]+1

for j in range(W):
  for i in range(0,H-1):
    if a[i+1][j]>a[i][j]+1:
      a[i+1][j]=a[i][j]+1
for j in range(W-1,-1,-1):
  for i in range(H-1,0,-1):
    if a[i-1][j]>a[i][j]+1:
      a[i-1][j]=a[i][j]+1

ans=0
for i in range(H):
  ans=max(ans,max(a[i]))
print(ans)