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:
#!/usr/bin/env python3
import sys
import heapq
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

h,w=map(int,input().split())
A=[list(input()) for i in range(h)]
# A=(tuple(input()) for i in range(h))
# print(A)
dis=[[-1]*w for i in range(h)]
hq=[]
for i in range(h):
    for j in range(w):
        if A[i][j]=="#":
            hq.append((0,i,j))
            dis[i][j]=0
dii=[(1,0),(-1,0),(0,1),(0,-1)]
heapq.heapify(hq)
ans=0
while hq:
    count,i,j=heapq.heappop(hq)
    for di,dj in dii:
        if not (0<=i+di<h and 0<=j+dj<w):
            continue
        if dis[i+di][j+dj]==-1:
            heapq.heappush(hq, (count+1, i+di, j+dj))
            dis[i+di][j+dj]=count+1
            ans=max(ans,count+1)
#             # print(count+1)
# ans=0
# for Ai in dis:
#     ans=max(ans,max(Ai))
print(ans)
# for d in dis:
#     print(d)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import heapq
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

h,w=map(int,input().split())
A=[list(input()) for i in range(h)]
# print(A)
dis=[[-1]*w for i in range(h)]
hq=[]
for i in range(h):
    for j in range(w):
        if A[i][j]=="#":
            hq.append((0,i,j))
            dis[i][j]=0
dii=[(1,0),(-1,0),(0,1),(0,-1)]
heapq.heapify(hq)
while hq:
    count,i,j=heapq.heappop(hq)
    for di,dj in dii:
        if not (0<=i+di<h and 0<=j+dj<w):
            continue
        if dis[i+di][j+dj]==-1:
            heapq.heappush(hq, (count+1, i+di, j+dj))
            dis[i+di][j+dj]=count+1
            # print(count+1)
ans=0
for Ai in dis:
    ans=max(ans,max(Ai))
print(ans)
# for d in dis:
#     print(d)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import heapq
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

h,w=map(int,input().split())
A=[list(input()) for i in range(h)]
# print(A)
dis=[[-1]*w for i in range(h)]
hq=[]
for i in range(h):
    for j in range(w):
        if A[i][j]=="#":
            hq.append((0,i,j))
            dis[i][j]=0
dii=[(1,0),(-1,0),(0,1),(0,-1)]
heapq.heapify(hq)
while hq:
    count,i,j=heapq.heappop(hq)
    for di,dj in dii:
        if not (0<=i+di<h and 0<=j+dj<w):
            continue
        if dis[i+di][j+dj]==-1:
            hq.append((count+1,i+di,j+dj))
            dis[i+di][j+dj]=count+1
            # print(count+1)
ans=0
for Ai in dis:
    ans=max(ans,max(Ai))
print(ans)
# for d in dis:
#     print(d)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

d = [[10**6]*W for _ in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            d[i][j] = 0
            q = deque()
            q.append((i, j, 0))
            while q:
                temp = q.popleft()
                y = temp[0]
                x = temp[1]
                r = temp[2]
                if y != 0:
                    if d[y-1][x] > r+1 and A[y-1][x] == ".":
                        d[y-1][x] = r+1
                        q.append((y-1, x, r+1))
                if y != H-1:
                    if d[y+1][x] > r+1 and A[y+1][x] == ".":
                        d[y+1][x] = r+1
                        q.append((y+1, x, r+1))
                if x != 0:
                    if d[y][x-1] > r+1 and A[y][x-1] == ".":
                        d[y][x-1] = r+1
                        q.append((y, x-1, r+1))
                if x != W-1:
                    if d[y][x+1] > r+1 and A[y][x+1] == ".":
                        d[y][x+1] = r+1
                        q.append((y, x+1, r+1))
                        
ans = 0
for i in range(H):
    ans = max(ans, max(d[i]))
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections


def solve():
    sys.setrecursionlimit(2000)
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, input().rstrip('\n').split()))
    a = [list(str(input().rstrip('\n'))) for _ in range(h)]
    ql = []
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                ql.append([0, i, j, [[0, 1], [0, -1], [1, 0], [-1, 0]]])
                fq[i, j]

    while True:
        if len(ql) != 0:
            cost, xv, yv, nextv = ql.popleft()
            for nxv, nyv in nextv:
                if 0 <= xv + nxv < h and 0 <= yv + nyv < w:
                    if (xv + nxv, yv + nyv) not in fq:
                        fq[xv + nxv, yv + nyv]
                        if nxv == 1:
                            ql.append([cost + 1, xv + nxv, yv + nyv, [[0, 1], [0, -1], [1, 0]]])
                        elif nxv == -1:
                            ql.append([cost + 1, xv + nxv, yv + nyv, [[0, 1], [0, -1], [-1, 0]]])
                        elif nyv == 1:
                            ql.append([cost + 1, xv + nxv, yv + nyv, [[-1, 0], [1, 0], [0, 1]]])
                        elif nyv == -1:
                            ql.append([cost + 1, xv + nxv, yv + nyv, [[-1, 0], [1, 0], [0, -1]]])
        else:
            break
    print(cost)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections


def solve():
    sys.setrecursionlimit(2000)
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, input().rstrip('\n').split()))
    a = [list(str(input().rstrip('\n'))) for _ in range(h)]
    ql = []
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                ql.append([0, i, j])
                fq[i, j]

    while True:
        if len(ql) != 0:
            cost, xv, yv = ql.popleft()
            for xv, yv in [[xv + 1, yv], [xv - 1, yv], [xv, yv + 1], [xv, yv - 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if (xv, yv) not in fq:
                        ql.append([cost + 1, xv, yv])
                        fq[xv, yv]
        else:
            break
    print(cost)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections


def solve():
    sys.setrecursionlimit(2000)
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, input().rstrip('\n').split()))
    a = [list(str(input().rstrip('\n'))) for _ in range(h)]
    ql = []
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                ql.append([0, i, j])
                fq[i, j]

    mt = 0
    while True:
        if len(ql) != 0:
            cost, xv, yv = ql.popleft()
            mt = max(mt, cost)
            for xv, yv in [[xv + 1, yv], [xv - 1, yv], [xv, yv + 1], [xv, yv - 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if (xv, yv) not in fq:
                        ql.append([cost + 1, xv, yv])
                        fq[xv, yv]
        else:
            break
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    h,w = map(int,input().split())
    a=[]
    que=[]
    for _ in range(h):
        a.append(list(input()))
    for i in range(h):
        for j in range(w):
            if a[i][j]=="#":
                que.append([i,j])
                a[i][j]=0
    ans=0
    while que!=[]:
        [i,j]=que[0]
        que.pop(0)
        if j<w-1 and a[i][j+1]==".":
            que.append([i,j+1])
            a[i][j+1]=a[i][j]+1
            if ans < a[i][j]+1:
                ans=a[i][j]+1
        if 0<j and a[i][j-1]==".":
            que.append([i,j-1])
            a[i][j-1]=a[i][j]+1
            if ans < a[i][j]+1:
                ans=a[i][j]+1
        if i<h-1 and a[i+1][j]==".":
            que.append([i+1,j])
            a[i+1][j]=a[i][j]+1
            if ans < a[i][j]+1:
                ans=a[i][j]+1
        if 0<i and a[i-1][j]==".":
            que.append([i-1,j])
            a[i-1][j]=a[i][j]+1
            if ans < a[i][j]+1:
                ans=a[i][j]+1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    h,w = map(int,input().split()) 
    x=[[-1 for _ in range(w)] for _ in range(h)]
    a=[]
    que=[]
    for _ in range(h):
        a.append(list(input()))
    for i in range(h):
        for j in range(w):
            if a[i][j]=="#":
                que.append([i,j])
                x[i][j]=0
    ans=0
    while que!=[]:
        [i,j]=que[0]
        que.pop(0)
        if j<w-1 and x[i][j+1]==-1:
            que.append([i,j+1])
            x[i][j+1]=x[i][j]+1
            if ans < x[i][j]+1:
                ans=x[i][j]+1
        if 0<j and x[i][j-1]==-1:
            que.append([i,j-1])
            x[i][j-1]=x[i][j]+1
            if ans < x[i][j]+1:
                ans=x[i][j]+1
        if i<h-1 and x[i+1][j]==-1:
            que.append([i+1,j])
            x[i+1][j]=x[i][j]+1
            if ans < x[i][j]+1:
                ans=x[i][j]+1
        if 0<i and x[i-1][j]==-1:
            que.append([i-1,j])
            x[i-1][j]=x[i][j]+1
            if ans < x[i][j]+1:
                ans=x[i][j]+1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    h,w = map(int,input().split()) 
    x=[[-1 for _ in range(w)] for _ in range(h)]
    a=[]
    for _ in range(h):
        a.append(list(input()))
    for i in range(h):
        for j in range(w):
            if a[i][j]=="#":
                x[i][j]=0
    cnt=0
    check=0
    while True:
        key=0
        for i in range(h):
            for j in range(w):
                if x[i][j]==-1:
                    key=1
                    if j<w-1 and x[i][j+1]==check:
                        x[i][j]=x[i][j+1]+1
                    elif 0<j and x[i][j-1]==check:
                        x[i][j]=x[i][j-1]+1
                    elif i<h-1 and x[i+1][j]==check:
                        x[i][j]=x[i+1][j]+1
                    elif 0<i and x[i-1][j]==check:
                        x[i][j]=x[i-1][j]+1
        if key==0:
            break
        else:
            check+=1
            cnt+=1
    print(cnt)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    h,w = map(int,input().split()) 
    x=[[0 for _ in range(w)] for _ in range(h)]
    a=[]
    for _ in range(h):
        a.append(list(input()))
    for i in range(h):
        for j in range(w):
            if a[i][j]=="#":
                x[i][j]=1
    cnt=0
    while True:
        key=0
        b=[]
        for i in range(h):
            for j in range(w):
                key1=0
                if x[i][j]==0:
                    key=1
                    if j<w-1 and a[i][j+1]=="#":
                        x[i][j]=1
                        key1=1
                    elif 0<j and a[i][j-1]=="#":
                        x[i][j]=1
                        key1=1
                    elif i<h-1 and a[i+1][j]=="#":
                        x[i][j]=1
                        key1=1
                    elif 0<i and a[i-1][j]=="#":
                        x[i][j]=1
                        key1=1
                if key1==1:
                    b.append([i,j])
        while b!=[]:
            [n,m]=b[0]
            a[n][m]="#"
            b.pop(0)
        if key==0:
            break
        else:
            cnt+=1
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

matrix = [[1]*(w+2)]
matrix += [[1] + [x == '#' for x in input().rstrip()] + [1] for _ in range(h)]
matrix.append([1]*(w+2))

matrix_list1 = []

cnt = -1

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j]:
            matrix_list1.append((i,j))

while matrix_list1:
    matrix_list2 = []
    for x,y in matrix_list1:
        if not matrix[x+1][y]:
            matrix[x+1][y] = 1
            matrix_list2.append((x+1,y))
        if not matrix[x-1][y]:
            matrix[x-1][y] = 1
            matrix_list2.append((x-1,y))
        if not matrix[x][y+1]:
            matrix[x][y+1] = 1
            matrix_list2.append((x,y+1))
        if not matrix[x][y-1]:
            matrix[x][y-1] = 1
            matrix_list2.append((x,y-1))
    matrix_list1 = matrix_list2
    cnt += 1
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())

matrix = [[1]*(w+2)]
matrix += [[1] + [x == '#' for x in input().rstrip()] + [1] for _ in range(h)]
matrix.append([1]*(w+2))

matrix_list1 = []

cnt = -1

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j]:
            matrix_list1.append((i,j))

while matrix_list1:
    matrix_list2 = []
    for x,y in matrix_list1:
        if not matrix[x+1][y]:
            matrix[x+1][y] = 1
            matrix_list2.append((x+1,y))
        if not matrix[x-1][y]:
            matrix[x-1][y] = 1
            matrix_list2.append((x-1,y))
        if not matrix[x][y+1]:
            matrix[x][y+1] = 1
            matrix_list2.append((x,y+1))
        if not matrix[x][y-1]:
            matrix[x][y-1] = 1
            matrix_list2.append((x,y-1))
    matrix_list1 = matrix_list2
    cnt += 1
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())

matrix = [[1]*(w+2)]
matrix += [[1] + [x == '#' for x in input().rstrip()] + [1] for _ in range(h)]
matrix.append([1]*(w+2))

matrix_list1 = []

cnt = -1

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j]:
            matrix_list1.append([i,j])

while matrix_list1:
    matrix_list2 = []
    for x,y in matrix_list1:
        if not matrix[x+1][y]:
            matrix[x+1][y] = 1
            matrix_list2.append([x+1,y])
        if not matrix[x-1][y]:
            matrix[x-1][y] = 1
            matrix_list2.append([x-1,y])
        if not matrix[x][y+1]:
            matrix[x][y+1] = 1
            matrix_list2.append([x,y+1])
        if not matrix[x][y-1]:
            matrix[x][y-1] = 1
            matrix_list2.append([x,y-1])
    matrix_list1 = matrix_list2
    cnt += 1
    
print(cnt)

Submission status: Time Limit Exceeded

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

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

matrix = [[1]*(w+2)]
matrix += [[1] + [x == '#' for x in input().rstrip()] + [1] for _ in range(h)]
matrix.append([1]*(w+2))

matrix_list1 = deque()
cnt = -1

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j]:
            matrix_list1.append([i,j])

while len(matrix_list1) != 0:     
    for _ in range(len(matrix_list1)):
        x,y = matrix_list1.popleft()
        if not matrix[x+1][y]:
            matrix[x+1][y] = 1
            matrix_list1.append([x+1,y])
        if not matrix[x-1][y]:
            matrix[x-1][y] = 1
            matrix_list1.append([x-1,y])
        if not matrix[x][y+1]:
            matrix[x][y+1] = 1
            matrix_list1.append([x,y+1])
        if not matrix[x][y-1]:
            matrix[x][y-1] = 1
            matrix_list1.append([x,y-1])
    cnt += 1
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

matrix = [[1]*(w+2)]
matrix += [[1] + [x == '#' for x in input().rstrip()] + [1] for _ in range(h)]
matrix.append([1]*(w+2))

matrix_list1 = deque()
cnt = -1

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j]:
            matrix_list1.append([i,j])

while len(matrix_list1) != 0:     
    for _ in range(len(matrix_list1)):
        x,y = matrix_list1.popleft()
        if not matrix[x+1][y]:
            matrix[x+1][y] = 1
            matrix_list1.append([x+1,y])
        if not matrix[x-1][y]:
            matrix[x-1][y] = 1
            matrix_list1.append([x-1,y])
        if not matrix[x][y+1]:
            matrix[x][y+1] = 1
            matrix_list1.append([x,y+1])
        if not matrix[x][y-1]:
            matrix[x][y-1] = 1
            matrix_list1.append([x,y-1])
    cnt += 1
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = map(int,input().split())
matrix = [[1]*(w+2)] + [list("a" + input() + "a") for _ in range(h)] + [[1]*(w+2)]

matrix_list1 = deque()
cnt = -1

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j] == "#":
            matrix[i][j] = 1
            matrix_list1.append([i,j])
        else:
            matrix[i][j] = 0

while len(matrix_list1) != 0:     
    for _ in range(len(matrix_list1)):
        x,y = matrix_list1.popleft()
        if not matrix[x+1][y]:
            matrix[x+1][y] = 1
            matrix_list1.append([x+1,y])
        if not matrix[x-1][y]:
            matrix[x-1][y] = 1
            matrix_list1.append([x-1,y])
        if not matrix[x][y+1]:
            matrix[x][y+1] = 1
            matrix_list1.append([x,y+1])
        if not matrix[x][y-1]:
            matrix[x][y-1] = 1
            matrix_list1.append([x,y-1])
    cnt += 1
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = map(int,input().split())
matrix = [["a"]*(w+2)] + [list("a" + input() + "a") for _ in range(h)] + [["a"]*(w+2)]

matrix_list1 = deque()
cnt = -1

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j] == "#":
            matrix_list1.append([i,j])

while len(matrix_list1) != 0:     
    for _ in range(len(matrix_list1)):
        x,y = matrix_list1.popleft()
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "#"
            matrix_list1.append([x+1,y])
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "#"
            matrix_list1.append([x-1,y])
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "#"
            matrix_list1.append([x,y+1])
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "#"
            matrix_list1.append([x,y-1])
    cnt += 1
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

matrix_list1 = deque()
cnt = -1

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j] == "#":
            matrix_list1.append([i,j])

while len(matrix_list1) != 0:     
    for _ in range(len(matrix_list1)):
        x,y = matrix_list1.popleft()
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "#"
            matrix_list1.append([x+1,y])
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "#"
            matrix_list1.append([x-1,y])
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "#"
            matrix_list1.append([x,y+1])
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "#"
            matrix_list1.append([x,y-1])
    cnt += 1
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

matrix_list1 = deque()
cnt = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j] == "#":
            matrix_list1.append([i,j])

while len(matrix_list1) != 0:     
    for _ in range(len(matrix_list1)):
        x,y = matrix_list1.popleft()
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "#"
            matrix_list1.append([x+1,y])
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "#"
            matrix_list1.append([x-1,y])
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "#"
            matrix_list1.append([x,y+1])
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "#"
            matrix_list1.append([x,y-1])
    else:
        if len(matrix_list1) > 0:
            cnt += 1
    
print(cnt)

Submission status: Time Limit Exceeded

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

matrix_list1 = []
matrix_list2 = []
cnt = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j] == "#":
            matrix_list1.append([i,j])

while len(matrix_list1) != 0:     
    for x,y in matrix_list1:
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "#"
            matrix_list2.append([x+1,y])
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "#"
            matrix_list2.append([x-1,y])
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "#"
            matrix_list2.append([x,y+1])
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "#"
            matrix_list2.append([x,y-1])
    else:
        matrix_list1 = matrix_list2.copy()
        matrix_list2 = []
        if len(matrix_list1) > 0:
            cnt += 1
    
print(cnt)

Submission status: Time Limit Exceeded

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

matrix_list1 = []
matrix_list2 = []
cnt = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j] == "#":
            tap = [i,j]
            matrix_list1.append(tap)

while len(matrix_list1) != 0:     
    for x,y in matrix_list1:
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "#"
            tap = [x+1,y]
            matrix_list2.append(tap)
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "#"
            tap = [x-1,y]
            matrix_list2.append(tap)
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "#"
            tap = [x,y+1]
            matrix_list2.append(tap)
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "#"
            tap = [x,y-1]
            matrix_list2.append(tap)
    else:
        matrix_list1 = matrix_list2.copy()
        matrix_list2 = []
        if len(matrix_list1) > 0:
            cnt += 1
    
print(cnt)

Submission status: Time Limit Exceeded

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

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


def check(aij):
    i, j, c = aij[0], aij[1], aij[2]
    for dy, dx in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        if 0 <= i + dy < H and 0 <= j + dx < W and A[i + dy][j + dx] == ".":
            A[i + dy][j + dx] = c + 1
            que.append([i + dy, j + dx, c + 1])


while len(que) > 0:
    check(que.pop(0))


num=0
for i in range(H):
    for j in range(W):
        num = max(num, A[i][j])

print(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    h, w = map(int, input().split())
    G = [("#",)*(w+2)]+[("#",)+tuple(input())+("#",) for i in range(h)]+[("#",)*(w+2)]
    dy, dx = [-1, 1, 0, 0], [0, 0, -1, 1]
    dist = [[-1 for j in range(w+2)] for i in range(h+2)]
    que = deque()
    
    for i in range(1, h+1):
        for j in range(1, w+1):
            if G[i][j] == "#":
                dist[i][j] = 0
                que.append((i, j))
    ans = 0
    while (len(que) != 0):
        y, x = que[0][0], que[0][1]
        que.popleft()

        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if G[ny][nx] == "#":
                continue
            if dist[ny][nx] == -1:
                dist[ny][nx] = dist[y][x] + 1
                que.append((ny, nx))
                ans = max(ans, dist[ny][nx])
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
def main():
    input = sys.stdin.readline
    h, w = map(int, input().split())
    G = [["#"]*(w+2)]+[["#"]+list(map(lambda x: "#" if x == "\n" else x, list(input()))) for i in range(h)]+[["#"]*(w+2)]
    dy, dx = [-1, 1, 0, 0], [0, 0, -1, 1]
    dist = [[-1 for j in range(w+2)] for i in range(h+2)]
    que = deque()
    
    for i in range(1, h+1):
        for j in range(1, w+1):
            if G[i][j] == "#":
                dist[i][j] = 0
                que.append((i, j))
    
    while (len(que) != 0):
        y, x = que[0][0], que[0][1]
        que.popleft()

        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if G[ny][nx] == "#":
                continue
            if dist[ny][nx] == -1:
                dist[ny][nx] = dist[y][x] + 1
                que.append((ny, nx))
    
    ans = 0
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            ans = max(ans, dist[i][j])
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    h, w = map(int, input().split())
    G = [["#"]*(w+2)]+[["#"]+list(input())+["#"] for i in range(h)]+[["#"]*(w+2)]
    dy, dx = [-1, 1, 0, 0], [0, 0, -1, 1]
    dist = [[-1 for j in range(w+2)] for i in range(h+2)]
    que = deque()
    
    for i in range(1, h+1):
        for j in range(1, w+1):
            if G[i][j] == "#":
                dist[i][j] = 0
                que.append((i, j))
    
    while (len(que) != 0):
        y, x = que[0][0], que[0][1]
        que.popleft()

        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if G[ny][nx] == "#":
                continue
            if dist[ny][nx] == -1:
                dist[ny][nx] = dist[y][x] + 1
                que.append((ny, nx))
    
    ans = 0
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            ans = max(ans, dist[i][j])
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    h, w = map(int, input().split())
    G = [list(input()) for i in range(h)]
    dy, dx = [-1, 1, 0, 0], [0, 0, -1, 1]
    dist = [[-1 for j in range(w)] for i in range(h)]
    que = deque()
    
    for i in range(h):
        for j in range(w):
            if G[i][j] == "#":
                dist[i][j] = 0
                que.append((i, j))
    
    while (len(que) != 0):
        y, x = que[0][0], que[0][1]
        que.popleft()

        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if (ny < 0) or (h <= ny) or (nx < 0) or (w <= nx):
                continue
            if G[ny][nx] == "#":
                continue
            if dist[ny][nx] == -1:
                dist[ny][nx] = dist[y][x] + 1
                que.append((ny, nx))
    
    ans = 0
    for i in dist:
        for j in i:
            ans = max(ans, j)
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(lambda x: int(x), input().split())
a=[]
for i in range(h):
    a.append(input())
todo=deque([])
dist=[[-1 for _ in range(w)] for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            todo.append((i, j))
            dist[i][j]=0
while todo:
    y, x=todo.popleft()
    for y1, x1 in [(y-1, x), (y+1, x), (y, x-1), (y, x+1)]:
        if y1<=-1 or y1>=h or x1<=-1 or x1>=w:
            continue
        if dist[y1][x1]!=-1:
            continue
        dist[y1][x1]=dist[y][x]+1
        todo.append((y1, x1))
ans=0
for i in range(h):
    ans=max(ans, max(dist[i]))
print(ans)

Submission status: Time Limit Exceeded

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

dist=[[-1 for _ in range(w)] for _ in range(h)]
que = deque([])
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            dist[i][j]=0
            que.append((i, j))

while que:
    y, x=que.popleft()
    for y1, x1 in [(y-1, x), (y+1, x), (y, x-1), (y, x+1)]:
        if y1<0 or y1>h-1 or x1<0 or x1>w-1:
            continue
        if dist[y1][x1]!=-1:
            continue
        dist[y1][x1]=dist[y][x]+1
        que.append((y1,x1))

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:
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, input().rstrip('\n').split()))
    a = [list(str(input().rstrip('\n'))) for _ in range(h)]
    ql = []
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                ql.append([0, i, j])
                fq[i, j]
    m_cost = 0
    while True:
        if len(ql) != 0:
            cost, x, y = ql.popleft()
            m_cost = max(m_cost, cost)
            for x, y in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]:
                if 0 <= x < h and 0 <= y < w:
                    if (x, y) not in fq and a[x][y] == ".":
                        ql.append([cost+1, x, y])
                        fq[x, y]
        else:
            break
    print(m_cost)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]

state = []
# 初期状態
for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            state.append([w, h])

tmp = []
ret = 0
while len(state) > 0:
    tmp = list()
    ret += 1
    for x, y in state:
        for nx, ny in ((1,0), (-1,0), (0,1), (0,-1)):
            nx += x
            ny += y
            if nx < 0 or ny < 0 or nx >= W or ny >= H:
                continue

            if field[ny][nx] == ".":
                field[ny][nx] = "#"
                tmp.append([nx, ny])
    state = tmp
    


print(ret-1)