Problem:


Score : 300 points

Problem Statement

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

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

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

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

Constraints

1 \leq H,W \leq 1000

A_{ij} is # or ..

The given grid has at least one black square.

Input

Input is given from Standard Input in the following format:

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

Output

Print the number of operations that will be performed.

Sample Input 1

3 3
...
.#.
...

Sample Output 1

2

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

Sample Input 2

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

Sample Output 2

3



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


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    h, w = list(map(int, readline().split()))
    a = [[True] * w for _ in range(h)]
    ql = []
    ql = collections.deque(ql)
    for i in range(h):
        s = str(readline().rstrip().decode('utf-8'))
        for j in range(w):
            if s[j] == "#":
                a[i][j] = False
                ql.append([0, i, j])

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


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    h, w = list(map(int, readline().split()))
    a = [[True] * w for _ in range(h)]
    ql = []
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    for i in range(h):
        s = str(readline().rstrip().decode('utf-8'))
        for j in range(w):
            if s[j] == "#":
                a[i][j] = False
                ql.append([0, i, j])
                fq[i, j]

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


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    h, w = list(map(int, readline().split()))
    a = [["."] * w for _ in range(h)]
    ql = []
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    for i in range(h):
        s = str(readline().rstrip().decode('utf-8'))
        for j in range(w):
            if s[j] == "#":
                a[i][j] = "#"
                ql.append([0, i, j])
                fq[i, j]

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


if __name__ == '__main__':
    solve()

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]

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


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, x, y = ql.popleft()
            mt = max(mt, cost)
            for xv, yv in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if (xv, yv) not in fq and a[xv][yv] == ".":
                        ql.append([cost + 1, xv, yv])
                        fq[xv, yv]
        else:
            break
    print(mt)


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 and a[xv][yv] == ".":
                        ql.append([cost + 1, xv, yv])
                        fq[xv, yv]
        else:
            break
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:

import queue
import numpy as np

H,W=map(int,input().split())
c=np.array([list(input()) for _ in range(H)])







#import queue
def bfs(array,start,height,width):
    v=[[-1]*width for _ in range(height)]

    q=queue.Queue()
    q.put([start[0],start[1]])
    move=[[0,1],[0,-1],[1,0],[-1,0]]
    v[start[0]][start[1]]=0
    while not q.empty():
        pos=q.get()
        if array[pos[0]][pos[1]]=="#":          
            break
        
        for m in move:
            y=pos[0]+m[0]
            x=pos[1]+m[1]
            if y>=0 and y<height and x>=0 and x<width and  v[y][x]==-1 :
                v[y][x]=v[pos[0]][pos[1]]+1
                q.put([y,x])
    return v[pos[0]][pos[1]]


ans=0
for i in range(H):
    for j in range(W):
        if c[i][j]==".":
            ans=max(ans,bfs(c,[i,j],H,W))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

def main():
    h,w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])
    dy = [1,-1,0,0]
    dx = [0,0,1,-1]
    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y,x = que.popleft()
            for i in range(4):
                nh = y + dy[i]
                nw = x + dx[i]
                if (0<=nh<h) and (0<=nw<w):
                    if a[nh][nw] == False:
                        a[nh][nw] = True
                        nque.append((nh,nw))
           
        if nque:
            que = copy.copy(nque)
        else:
            break
    print(count-1)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]


    # スタート地点をqueueに追加
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append([y,x-1])
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append([y,x+1])
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append([y-1,x])
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append([y+1,x])

        if nque:
            que = copy.copy(nque)
        else:
            break

    print(count - 1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

def main():
    h,w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y,x = que.popleft()
            if x >0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append([y,x-1])
            if x <w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append([y,x+1])
            if y >0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append([y-1,x])
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append([y+1,x])
        if nque:
            que = copy.copy(nque)
        else:
            break
    print(count-1)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

def main():
    h,w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]
    # dy = [1,-1,0,0]
    # dx = [0,0,1,-1]
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y,x = que.popleft()
            if x >0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append([y,x-1])
            if x <w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append([y,x+1])
            if y >0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append([y-1,x])
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append([y+1,x])
            # for i in range(4):
            #     nh = h + dy[i]
            #     nw = w + dx[i]
            #     if (0<=nh<H) and (0<=nw<W):
            #         if field[nh][nw] == False:
            #             field[nh][nw] = True
            #             nqueue.append((nh,nw))
        if nque:
            que = copy.copy(nque)
        else:
            break
    print(count-1)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

def main():
    h,w = map(int, input().split())
    field = [[j == "#" for j in input()] for _ in range(h)]
    # dy = [1,-1,0,0]
    # dx = [0,0,1,-1]
    que = deque([(i, j) for i in range(h) for j in range(w) if field[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y,x = que.popleft()
            if x >0 and not field[y][x-1]:
                field[y][x-1] = True
                nque.append([y,x-1])
            if x <w-1 and not field[y][x+1]:
                field[y][x+1] = True
                nque.append([y,x+1])
            if y >0 and not field[y-1][x]:
                field[y-1][x] = True
                nque.append([y-1,x])
            if y < h-1 and not field[y+1][x]:
                field[y+1][x] = True
                nque.append([y+1,x])
            # for i in range(4):
            #     nh = h + dy[i]
            #     nw = w + dx[i]
            #     if (0<=nh<H) and (0<=nw<W):
            #         if field[nh][nw] == False:
            #             field[nh][nw] = True
            #             nqueue.append((nh,nw))
        if nque:
            que = copy.copy(nque)
        else:
            break
    print(count-1)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
h,w = map(int, input().split())
field = [[j == "#" for j in input()] for _ in range(h)]
que = deque([(i, j) for i in range(h) for j in range(w) if field[i][j]])

count = 0
while True:
    count += 1
    nque = deque()
    while que:
        y,x = que.popleft()
        if x >0 and not field[y][x-1]:
            field[y][x-1] = True
            nque.append([y,x-1])
        if x <w-1 and not field[y][x+1]:
            field[y][x+1] = True
            nque.append([y,x+1])
        if y >0 and not field[y-1][x]:
            field[y-1][x] = True
            nque.append([y-1,x])
        if y < h-1 and not field[y+1][x]:
            field[y+1][x] = True
            nque.append([y+1,x])
    if nque:
        que = copy.copy(nque)
    else:
        break
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
H,W = map(int, input().split())
field = [[j == "#" for j in input()] for _ in range(H)]
# dy = [1,-1,0,0]
# dx = [0,0,1,-1]
que = deque([(i, j) for i in range(H) for j in range(W) if field[i][j]])

count = 0
while True:
    count += 1
    nque = deque()
    while que:
        h,w = que.popleft()
        if w >0 and not field[h][w-1]:
            field[h][w-1] = True
            nque.append([h,w-1])
        if w <W-1 and not field[h][w+1]:
            field[h][w+1] = True
            nque.append([h,w+1])
        if h >0 and not field[h-1][w]:
            field[h-1][w] = True
            nque.append([h-1,w])
        if h < H-1 and not field[h+1][w]:
            field[h+1][w] = True
            nque.append([h+1,w])
        # for i in range(4):
        #     nh = h + dy[i]
        #     nw = w + dx[i]
        #     if (0<=nh<H) and (0<=nw<W):
        #         if field[nh][nw] == False:
        #             field[nh][nw] = True
        #             nqueue.append((nh,nw))
    if nque:
        que = copy.copy(nque)
    else:
        break
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
H,W = map(int, input().split())
field = [[j == "#" for j in input()] for _ in range(H)]
# dy = [1,-1,0,0]
# dx = [0,0,1,-1]
queue = deque([(i, j) for i in range(H) for j in range(W) if field[i][j]])

count = 0
while True:
    count += 1
    nqueue = deque()
    while queue:
        h,w = queue.popleft()
        if w >0 and not field[h][w-1]:
            field[h][w-1] = True
            nqueue.append([h,w-1])
        if w <W-1 and not field[h][w+1]:
            field[h][w+1] = True
            nqueue.append([h,w+1])
        if h >0 and not field[h-1][w]:
            field[h-1][w] = True
            nqueue.append([h-1,w])
        if h < H-1 and not field[h+1][w]:
            field[h+1][w] = True
            nqueue.append([h+1,w])
        # for i in range(4):
        #     nh = h + dy[i]
        #     nw = w + dx[i]
        #     if (0<=nh<H) and (0<=nw<W):
        #         if field[nh][nw] == False:
        #             field[nh][nw] = True
        #             nqueue.append((nh,nw))
    if nqueue:
        queue = copy.copy(nqueue)
    else:
        break
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
H,W = map(int, input().split())
field = [[j == "#" for j in input()] for _ in range(H)]
dy = [1,-1,0,0]
dx = [0,0,1,-1]

queue = deque()
# sy,sx = 0,0
# gy,gx = H-1,W-1
queue = deque([(i, j) for i in range(H) for j in range(W) if field[i][j]])
# for i in range(H):
#     for j in range(W):
#         if field[i][j] == True:
#             queue.append([i,j])
# queue = [[sy,sx]]
flag = False
count = 0
while True:
    count += 1
    nqueue = deque()
    while queue:
        h,w = queue.popleft()
        if w >0 and not field[h][w-1]:
            field[h][w-1] = True
            nqueue.append([h,w-1])
        if w <W-1 and not field[h][w+1]:
            field[h][w+1] = True
            nqueue.append([h,w+1])
        if h >0 and not field[h-1][w]:
            field[h-1][w] = True
            nqueue.append([h-1,w])
        if h < H-1 and not field[h+1][w]:
            field[h+1][w] = True
            nqueue.append([h+1,w])
        # for i in range(4):
        #     nh = h + dy[i]
        #     nw = w + dx[i]
        #     if (0<=nh<H) and (0<=nw<W):
        #         if field[nh][nw] == False:
        #             field[nh][nw] = True
        #             nqueue.append((nh,nw))
    if nqueue:
        queue = copy.copy(nqueue)
    else:
        break
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append([h, w, 0])

ans = 0
while len(black_cells) > 0:
    one_black_cell = black_cells.popleft()  # キューとして使うのでpop()ではなくpopleft()
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = one_black_cell[0] + dy
        nw = one_black_cell[1] + dx
        d = one_black_cell[2]
        if nh < 0 or H <= nh or nw < 0 or W <= nw:
            continue
        if grid[nh][nw] == '.':
            grid[nh][nw] = '#'
            black_cells.append([nh, nw, d + 1])
        ans = d

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
H,W = map(int, input().split())
field = [[j == "#" for j in input()] for _ in range(H)]
dy = [1,-1,0,0]
dx = [0,0,1,-1]

queue = deque()
# sy,sx = 0,0
# gy,gx = H-1,W-1
queue = deque([(i, j) for i in range(H) for j in range(W) if field[i][j]])
# for i in range(H):
#     for j in range(W):
#         if field[i][j] == True:
#             queue.append([i,j])
# queue = [[sy,sx]]
flag = False
count = 0
while True:
    count += 1
    nqueue = deque()
    while queue:
        h,w = queue.popleft()
        for i in range(4):
            nh = h + dy[i]
            nw = w + dx[i]
            if (0<=nh<H) and (0<=nw<W):
                if field[nh][nw] == False:
                    field[nh][nw] = True
                    nqueue.append((nh,nw))
    if nqueue:
        queue = copy.copy(nqueue)
    else:
        break
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
H,W = map(int, input().split())
field = [[j == "#" for j in input()] for _ in range(H)]
dy = [1,-1,0,0]
dx = [0,0,1,-1]

queue = deque()
# sy,sx = 0,0
# gy,gx = H-1,W-1
queue = deque([(i, j) for i in range(H) for j in range(W) if field[i][j]])
# for i in range(H):
#     for j in range(W):
#         if field[i][j] == True:
#             queue.append([i,j])
# queue = [[sy,sx]]
flag = False
count = 0
while True:
    count += 1
    nqueue = deque()
    while queue:
        h,w = queue.popleft()
        for i in range(4):
            nh = h + dy[i]
            nw = w + dx[i]
            if (0<=nh<H) and (0<=nw<W):
                if field[nh][nw] == False:
                    field[nh][nw] = True
                    nqueue.append([nh,nw])
    if nqueue:
        queue = copy.copy(nqueue)
    else:
        break
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
H,W = map(int, input().split())
field = [[j == "#" for j in input()] for _ in range(H)]
dy = [1,-1,0,0]
dx = [0,0,1,-1]

queue = deque()
# sy,sx = 0,0
# gy,gx = H-1,W-1
for i in range(H):
    for j in range(W):
        if field[i][j] == True:
            queue.append([i,j])
# queue = [[sy,sx]]
flag = False
count = 0
while True:
    count += 1
    nqueue = deque()
    while queue:
        h,w = queue.popleft()
        for i in range(4):
            nh = h + dy[i]
            nw = w + dx[i]
            if (0<=nh<H) and (0<=nw<W):
                if field[nh][nw] == False:
                    field[nh][nw] = True
                    nqueue.append([nh,nw])
    if nqueue:
        queue = copy.copy(nqueue)
    else:
        break
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W = map(int, input().split())
    field = [list(input()) for _ in range(H)]
    dd = ((1, 0), (-1, 0), (0, 1), (0, -1))

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

    while q:
        qn = []
        moves += 1
        for x, y in q:
            for dx, dy in dd:
                nx, ny = int(x + dx), int(y + dy)
                if 0 <= nx < H and 0 <= ny < W:
                    if field[nx][ny] == ".":
                        field[nx][ny] = moves
                        qn.append((nx, ny))

        q = qn

    m = []
    for i in range(H):
        m.append(max(field[i]))
    print(max(m))


main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def main():
    H, W = map(int, input().split())
    A = np.zeros([H, W])
    for h in range(H):
        A[h, :] = list(map(lambda x: 1 if x == "#" else 0, input()))

    costs = np.zeros([H, W])
    dd = ((1, 0), (-1, 0), (0, 1), (0, -1))

    s = np.where(A == 1)
    s = np.array(s)
    len_s = s.shape[1]
    q = []
    for i in range(len_s):
        q.append((s[0, i], s[1, i]))

    moves = 0

    while q:
        qn = []
        moves += 1
        for x, y in q:
            for dx, dy in dd:
                nx, ny = int(x + dx), int(y + dy)
                if 0 <= nx < H and 0 <= ny < W:
                    if A[nx, ny] == 0:
                        costs[nx, ny] = moves
                        A[nx, ny] = 1
                        qn.append((nx, ny))

        q = qn
        if np.all(A == 1):
            break

    print(int(np.max(costs)))


main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def main():
    H, W = map(int, input().split())
    A = np.zeros([H, W])
    for h in range(H):
        A[h, :] = list(map(lambda x: 1 if x == "#" else 0, input()))

    costs = np.zeros([H, W])
    dd = ((1, 0), (-1, 0), (0, 1), (0, -1))

    s = np.where(A == 1)
    s = np.array(s)
    len_s = s.shape[1]
    q = []
    for i in range(len_s):
        q.append((s[0, i], s[1, i]))

    moves = 0

    while q:
        qn = []
        moves += 1
        for x, y in q:
            for dx, dy in dd:
                nx, ny = int(x + dx), int(y + dy)
                if 0 <= nx < H and 0 <= ny < W:
                    if A[nx, ny] == 0:
                        costs[nx, ny] = moves
                        A[nx, ny] = 1
                        qn.append((nx, ny))

        q = qn

    print(int(np.max(costs)))


main()

Submission status: Time Limit Exceeded

Solution code:
import copy
H,W = map(int, input().split())
field = [[j == "#" for j in input()] for _ in range(H)]
dy = [1,-1,0,0]
dx = [0,0,1,-1]

queue = []
# sy,sx = 0,0
# gy,gx = H-1,W-1
for i in range(H):
    for j in range(W):
        if field[i][j] == True:
            queue.append([i,j])
# queue = [[sy,sx]]
flag = False
count = 0
while True:
    count += 1
    nqueue = []
    while queue:
        h,w = queue.pop(0)
        for i in range(4):
            nh = h + dy[i]
            nw = w + dx[i]
            if (0<=nh<H) and (0<=nw<W):
                if field[nh][nw] != '#':
                    if field[nh][nw] == False:
                        field[nh][nw] = True
                        nqueue.append([nh,nw])
    if nqueue:
        queue = copy.copy(nqueue)
    else:
        break
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
import copy
H,W = map(int, input().split())
field = [list(input()) for _ in range(H)]
dy = [1,-1,0,0]
dx = [0,0,1,-1]

queue = []
# sy,sx = 0,0
# gy,gx = H-1,W-1
seen = [[0 for i in range(W)] for j in range(H)]
for i in range(H):
    for j in range(W):
        if field[i][j] == '#':
            seen[i][j] = 1
            queue.append([i,j])
# queue = [[sy,sx]]
flag = False
count = 0
while True:
    count += 1
    nqueue = []
    while queue:
        h,w = queue.pop(0)
        for i in range(4):
            nh = h + dy[i]
            nw = w + dx[i]
            if (0<=nh<H) and (0<=nw<W):
                if field[nh][nw] != '#':
                    if seen[nh][nw] == 0:
                        seen[nh][nw] = 1
                        nqueue.append([nh,nw])
    if nqueue:
        queue = copy.copy(nqueue)
    else:
        break
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().split())
field = [list(input()) for _ in range(H)]
dy = [1,-1,0,0]
dx = [0,0,1,-1]


queues = []
# sy,sx = 0,0
# gy,gx = H-1,W-1
seen = [[0 for i in range(W)] for j in range(H)]
for i in range(H):
    for j in range(W):
        if field[i][j] == '#':
            seen[i][j] = 1
            queues.append([[i,j]])
# queue = [[sy,sx]]
flag = False
count = 0
while flag == False:
    count += 1
    for ix, queue in enumerate(queues):
        if queue == []:
            continue
        h,w = queue.pop(0)
        for i in range(4):
            nh = h + dy[i]
            nw = w + dx[i]
            # if (nh == gy) and (nw == gx):
            #     count = before+1
            #     flag = True
            if (0<=nh<H) and (0<=nw<W):
                if field[nh][nw] != '#':
                    if seen[nh][nw] == 0:
                        seen[nh][nw] = 1
                        queue.append([nh,nw])
        queues[ix] = queue
    has_zero = False
    for i in range(H):
        for j in range(W):
            if seen[i][j] == 0:
                has_zero = True
                break
        if has_zero:
            break
    if has_zero == False:
        flag = True
    
        # if flag:
        #     break
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import heapq
input = lambda: sys.stdin.buffer.readline()[:-1].decode('utf-8')
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
from collections import deque
input = lambda: sys.stdin.buffer.readline()[:-1].decode('utf-8')
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=deque()
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=hq.popleft()
    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
            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:
import copy
h,w = map(int,input().split())
a = []
for i in range(h+2):
  a.append([2] * (w+2))
d = 0
for i in range(h):
  b = input()
  c = 0
  for k in b:
    if k == '.':
      a[i+1][c+1] = 0
      d += 1
    else:
      a[i+1][c+1] = 1
    c += 1
count = 0
while d != 0:
  count += 1
  d = 0
  b = copy.deepcopy(a)
  for i in range(h):
    for k in range(w):
      if a[i+1][k+1] == 0:
        if b[i][k+1] == 1 or b[i+2][k+1] == 1 or b[i+1][k] == 1 or b[i+1][k+2] == 1:
          a[i+1][k+1] = 1
        else:
          d += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
a=[input() for _ in range(h)]
inf=10**10
dist=[[inf if c=='.' else 0 for c in r] for r in a]
dq=deque()
for i in range(h):
    for j in range(w):
        if dist[i][j]==0:
            dq.append([i,j])
diff=[[1,0],[0,1],[-1,0],[0,-1]]
ans=0
while(dq):
    y,x=dq.popleft()
    for dy,dx in diff:
        y2=y+dy
        x2=x+dx
        if 0<=y2<h and 0<=x2<w and dist[y2][x2]>dist[y][x]+1:
            dq.append([y2,x2])
            dist[y2][x2]=dist[y][x]+1
            ans=max(ans,dist[y2][x2])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import heapq
from collections import deque
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=deque()
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=hq.popleft()
    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
            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)