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
from collections import deque
import copy
import numpy


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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy
import numpy


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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy
import numpy


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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy


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

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
AA = [list(input()) for _ in range(h)]
# AA[h][w]
infi = 10 ** 10
kouho = []
ans = [[infi] * (w) for _ in range(h)]

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

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


que = deque(kouho)
while que:
    py, px, d = que.popleft()
    ans[py][px] = d
    for i in range(4):
        nx = px + dx[i]
        ny = py + dy[i]
        if nx < 0 or nx >= w:
            continue
        if ny < 0 or ny >= h:
            continue
        if ans[ny][nx] == infi:
            que.append((ny, nx, d + 1))


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

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
AA = [list(input()) for _ in range(h)]
# AA[h][w]
infi = 10 ** 10
kouho = []
ans = [[infi] * (w) for _ in range(h)]

for i in range(h):
    for j in range(w):
        if AA[i][j] == "#":
            kouho.append((i, j))

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


def bfs(sy, sx):
    ans[sy][sx] = 0
    que = deque([])
    que.append((sy, sx))
    while que:
        py, px = que.popleft()
        d = ans[py][px]
        for i in range(4):
            nx = px + dx[i]
            ny = py + dy[i]
            if nx < 0 or nx >= w:
                continue
            if ny < 0 or ny >= h:
                continue
            if ans[ny][nx] > d + 1:
                ans[ny][nx] = d + 1
                que.append((ny, nx))


for i, j in kouho:
    bfs(i, j)
cnt = 0
for i in range(h):
    for j in range(w):
        cnt = max(cnt, ans[i][j])

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def BFS(y,x):
    z= [[False for _ in range(W)] for _ in range(H)]
    v=deque( [[y,x]] )
    d[y][x]=0
    z[y][x]=True
    
    while v:
        a=v.popleft()
        for mv in move:
            s=a[0]+mv[0]
            t=a[1]+mv[1]
            if 0<=s<H and 0<=t<W:
                if z[s][t]==False:
                    z[s][t]=True
                    d[s][t]=min(d[s][t], d[a[0]][a[1]]+1)
                    v.append([s,t])
                    
    
from collections import deque
H,W=map(int,input().split())
A= [list(input()) for _ in range(H)]
d= [[2000 for _ in range(W)] for _ in range(H)]
move= [ (0,1),(0,-1),(1,0),(-1,0) ]


for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
                BFS(i,j)
                
#print(d)
maxi=0
for i in d:
    for j in i:
        maxi=max(maxi,j)
print(maxi)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    A = [input().strip() for _ in range(H)]

    q = collections.deque()

    ans = [[0] * W for j in range(H)]

    for j in range(H):
        for i in range(W):
            if A[j][i] == '#':
                q.append((j, i, 0))
                ans[j][i] = -1

    while q:
        c = q.popleft()
        y, x, d = c[0], c[1], c[2]
        for ny, nx in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
            if 0 <= y + ny < H and 0 <= x + nx < W:
                if ans[y + ny][x + nx] == 0:
                    ans[y + ny][x + nx] = d + 1
                    q.append((y + ny, x + nx, d + 1))

    a = 0
    for aa in ans:
        a = max(a, max(aa))
    print(a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
digtmp = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def flatten_2dim(array):
    return [item for sublist in array for item in sublist]

def main():
    H, W = map(int, input().split())
    grid = []; black = deque([])
    grid.append([0]*(W+2))
    for i in range(H):
        tmp = list(input()[:-1])
        for j in range(W):
            if tmp[j] == '#':
                black.append((i+1, j+1))
                tmp[j] = 0
        grid.append([0] + tmp + [0])
    grid.append([0]*(W+2))

    for _ in range(pow(10, 6)):
        fr = black.popleft()
        gfr = grid[fr[0]][fr[1]]
        for d in digtmp:
            to = (fr[0]+d[0], fr[1]+d[1])
            gto = grid[to[0]][to[1]]
            if gto == '.':
                grid[to[0]][to[1]] = gfr + 1
                black.append(to)
            elif gto != '#':
                if gfr + 1 < gto:
                    grid[to[0]][to[1]] = gfr + 1
                    black.append(to)
            else:
                pass
        if len(black) == 0:
            break
    
    ans = max(flatten_2dim(grid))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    A = [input().strip() for _ in range(H)]
    memo = [[10 ** 7] * W for j in range(H)]

    for j in range(H):
        for i in range(W):
            if A[j][i] == '#':
                q = collections.deque()
                q.append((j, i, 1))

                while q:
                    c = q.popleft()
                    x, y = c[1], c[0]
                    for nx, ny in [[0, 1], [0, -1], [-1, 0], [1, 0]]:
                        if 0 <= x + nx < W and 0 <= y + ny < H:
                            if A[y + ny][x + nx] == '.' and memo[y + ny][x + nx] > c[2]:
                                memo[y + ny][x + nx] = c[2]
                                q.append((y + ny, x + nx, c[2] + 1))

    ans = 0
    for j in range(H):
        for i in range(W):
            if memo[j][i] == 10 ** 7:
                continue
            ans = max(ans, memo[j][i])

    print(ans)








if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def bfs(H, W, dist, black_induces):
    queue = deque(black_induces)
    while queue:
        h, w = queue.popleft()
        for y, x in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
            hh, ww = h + y, w + x
            if not (0 <= hh < H and 0 <= ww < W):
                continue
            if dist[hh][ww] == -1:
                dist[hh][ww] = dist[h][w] + 1
                queue.append((hh, ww))


def main():
    H, W = map(int, input().split())
    dist = [[] for _ in range(H)]
    black_induces = []
    for i in range(H):
        A = input().rstrip()
        for j, s in enumerate(A):
            if s == "#":
                dist[i].append(0)
                black_induces.append((i, j))
            else:
                dist[i].append(-1)

    bfs(H, W, dist, black_induces)

    ans = max(max(d) for d in dist)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def bfs(H, W, dist):
    queue = deque()
    for h in range(H):
        for w in range(W):
            if dist[h][w] == 0:
                queue.append((h, w))
    while queue:
        h, w = queue.popleft()
        for y, x in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
            hh, ww = h + y, w + x
            if not (0 <= hh < H and 0 <= ww < W):
                continue
            if dist[hh][ww] == -1:
                dist[hh][ww] = dist[h][w] + 1
                queue.append((hh, ww))


def main():
    H, W = map(int, input().split())
    A = [None] * H
    for i in range(H):
        A[i] = input().rstrip()

    distance = [[0 if A[h][w] == "#" else -1
        for w in range(W)] for h in range(H)]

    bfs(H, W, distance)

    ans = max(max(d) for d in distance)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter


def bfs():
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    while que:
        p = que.popleft()
        y = p[0]
        x = p[1]

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if 0 <= ny < H and 0 <= nx < W and dist[ny][nx] == -1:
                dist[ny][nx] = dist[y][x] + 1
                que.append((ny, nx))
    return dist


# Input params and answer
H, W = map(int, input().split())
Map = [list(input()) for i in range(H)]
dist = [[-1] * W for i in range(H)]

# Initial Black Point
que = deque([])
for h in range(H):
    for w in range(W):
        if Map[h][w] == "#":
            que.append((h, w))
            dist[h][w] = 0

# BFS
nd = bfs()

ans = 0
for h in range(H):
    for w in range(W):
        if nd[h][w] > ans:
            ans = nd[h][w]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter


def bfs():
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    while que:
        p = que.popleft()
        y = p[0]
        x = p[1]

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if 0 <= ny < H and 0 <= nx < W and dist[ny][nx] == float("inf"):
                dist[ny][nx] = dist[y][x] + 1
                que.append((ny, nx))

    return dist


# Input params and answer
H, W = map(int, input().split())
Map = [list(input()) for i in range(H)]
dist = [[float("inf")] * W for i in range(H)]

# Initial Black Point
que = deque([])
for h in range(H):
    for w in range(W):
        if Map[h][w] == "#":
            que.append((h, w))
            dist[h][w] = 0

# BFS
nd = bfs()

# 1 dim array
c = []
for l in nd:
    c += l

print(max(c))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter


def bfs():
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    while que:
        p = que.popleft()
        y = p[0]
        x = p[1]

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if 0 <= ny < H and 0 <= nx < W and Map[ny][nx] != "#" and dist[ny][nx] == float("inf"):
                dist[ny][nx] = dist[y][x] + 1
                que.append((ny, nx))

    return dist


# Input params and answer
H, W = map(int, input().split())
Map = [list(input()) for i in range(H)]
dist = [[float("inf")] * W for i in range(H)]

# Initial Black Point
que = deque([])
for h in range(H):
    for w in range(W):
        if Map[h][w] == "#":
            que.append((h, w))
            dist[h][w] = 0

# BFS
nd = bfs()

# 1 dim array
c = []
for l in nd:
    c += l

print(max(c))

Submission status: Time Limit Exceeded

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

maze = [list(input()) for _ in range(n)]

def bfs():
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    d = [([-1]*m)for _ in range(n)]
    q = deque([])
    for i in range(n):
        for j in range(m):
            if maze[i][j] == "#":
                d[i][j] = 0
                q.append((i,j))
    a = 0

    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < n and 0<= ny < m and maze[nx][ny] != '#' and d[nx][ny] == -1:
                q.append((nx,ny))
                d[nx][ny] = d[x][y] +1
                a = max(a,d[nx][ny])
    return a

print(bfs())

Submission status: Time Limit Exceeded

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

maze = [list(input()) for _ in range(n)]

def bfs():
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    d = [([-1]*m)for _ in range(n)]
    q = deque([])
    for i in range(n):
        for j in range(m):
            if maze[i][j] == "#":
                d[i][j] = 0
                q.append((i,j))


    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < n and 0<= ny < m and maze[nx][ny] != '#' and d[nx][ny] == -1:
                q.append((nx,ny))
                d[nx][ny] = d[x][y] +1
    return max(sum(d,[]))

print(bfs())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m = map(int,input().split())
p = [input() for _ in range(n)]
q = deque([])
a = 0
for i in range(n):
    for j in range(m):
        if p[i][j] == "#":
            q.append((i,j))
for i in range(n):
    for j in range(m):
        a = max(min(abs(i-a)+abs(j-b)for a,b in q),a)
print(a)

Submission status: Time Limit Exceeded

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

maze = [list(input()) for _ in range(n)]

def bfs():
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    d = [([-1]*m)for _ in range(n)]
    q = deque([])
    for i in range(n):
        for j in range(m):
            if maze[i][j] == "#":
                d[i][j] = 0
                q.append((i,j))


    while q:
        x,y = q.popleft()
        if -1 in sum(d,[]):
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<= nx < n and 0<= ny < m and maze[nx][ny] != '#' and d[nx][ny] == -1:
                    q.append((nx,ny))
                    d[nx][ny] = d[x][y] +1
    return max(sum(d,[]))

print(bfs())

Submission status: Time Limit Exceeded

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

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

grid = [None] * H
dist = [[2000] * W for i in range(H)]
from collections import deque
q = deque([])
for i in range(H):
  grid[i] = readline().rstrip()
  for j in range(len(grid[i])):
    if grid[i][j] == "#":
      q.append((i,j,0))

cases = ((0,1),(0,-1),(1,0),(-1,0))
ans = 0
seen = set()
while q:
  y,x,d = q.popleft()
  if dist[y][x] <= d:
    continue
  dist[y][x] = d
  seen.add((y,x))
  if ans < d:
    ans = d
  for c in cases:
    if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
      if (y + c[0],x + c[1]) in seen:
        continue
      q.append((y + c[0],x + c[1],d + 1))
print(ans)

Submission status: Time Limit Exceeded

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

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

grid = [None] * H
dist = [[2000] * W for i in range(H)]
from collections import deque
q = deque([])
for i in range(H):
  grid[i] = readline().rstrip()
  for j in range(len(grid[i])):
    if grid[i][j] == "#":
      q.append((i,j,0))

cases = ((0,1),(0,-1),(1,0),(-1,0))
ans = 0
while q:
  y,x,d = q.popleft()
  if dist[y][x] <= d:
    continue
  dist[y][x] = d
  if ans < d:
    ans = d
  for c in cases:
    if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
      q.append((y + c[0],x + c[1],d + 1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

D = [[0] * W for _ in range(H)]

Q = deque()
Q1 = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            D[i][j] = 1
            Q.append([i, j])

yudlr = [1, -1, 0, 0]
xudlr = [0, 0, -1, 1]

C = 0
while len(Q) > 0:
    C += 1
    while len(Q) > 0:
        Q1.append(Q.pop())
    while len(Q1) > 0:
        q = Q1.popleft()
        y = q[0]
        x = q[1]
        for i in range(4):
            y1 = y + yudlr[i]
            x1 = x + xudlr[i]
            if y1 < 0 or y1 >= H or x1 < 0 or x1 >= W:
                continue
            if D[y1][x1] == 1:
                continue
            D[y1][x1] = 1
            Q.append([y1, x1])

print(C - 1)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
from collections import deque

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

D = [[0] * W for _ in range(H)]

Q = deque()
Q1 = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            D[i][j] = 1
            Q.append([i, j])

yudlr = [1, -1, 0, 0]
xudlr = [0, 0, -1, 1]

C = 0
while len(Q) > 0:
    C += 1
    Q1 = deepcopy(Q)
    Q.clear()
    while len(Q1) > 0:
        q = Q1.popleft()
        y = q[0]
        x = q[1]
        for i in range(4):
            y1 = y + yudlr[i]
            x1 = x + xudlr[i]
            if y1 < 0 or y1 >= H or x1 < 0 or x1 >= W:
                continue
            if D[y1][x1] == 1:
                continue
            D[y1][x1] = 1
            Q.append([y1, x1])

print(C - 1)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    H, W = [int(item) for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]

    fp = [[-1 for _ in range(W)] for _ in range(H)]

    que = collections.deque()
    next_y_x = [[0, 1], [1, 0], [-1, 0], [0, -1]]
    

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




    while que:
        temp = que.popleft()

        for dy, dx in next_y_x:
            ny = temp[0] + dy
            nx = temp[1] + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                if fp[ny][nx] == -1:
                    que.append([ny, nx, temp[2]+1])
                    fp[ny][nx] = temp[2] + 1

    temp_max_list = []
    for line in fp:
        temp_max_list.append(max(line))

    print(max(temp_max_list))



if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))



ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)

Submission status: Time Limit Exceeded

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

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)

Submission status: Time Limit Exceeded

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

H,W = map(int,input().split())
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
H, W = map(int, input().split())
visited = [[True] * (W + 2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True] * (W + 2))

q = []
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if visited[i][j]:
            q.append((i, j))

ans = -1
while q:
    qq = []
    ans += 1
    for h, w in q:
        if not visited[h - 1][w]:
            visited[h - 1][w] = True
            qq.append((h - 1, w))
        if not visited[h + 1][w]:
            visited[h + 1][w] = True
            qq.append((h + 1, w))
        if not visited[h][w - 1]:
            visited[h][w - 1] = True
            qq.append((h, w - 1))
        if not visited[h][w + 1]:
            visited[h][w + 1] = True
            qq.append((h, w + 1))
    q = qq
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
H, W = map(int, input().split())
visited = [[True] * (W + 2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True] * (W + 2))

q = []
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if visited[i][j]:
            q.append((i, j))

ans = -1
while q:
    tmp = []
    ans += 1
    for h, w in q:
        if not visited[h - 1][w]:
            visited[h - 1][w] = True
            tmp.append((h - 1, w))
        if not visited[h + 1][w]:
            visited[h + 1][w] = True
            tmp.append((h + 1, w))
        if not visited[h][w - 1]:
            visited[h][w - 1] = True
            tmp.append((h, w - 1))
        if not visited[h][w + 1]:
            visited[h][w + 1] = True
            tmp.append((h, w + 1))
    q = tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
visited = [[True] * (W + 2)]
visited += [[True] + [x == '#' for x in list(input())] + [True] for _ in range(H)]
visited += [[True] * (W + 2)]
ans = -1
q = []
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if visited[i][j]:
            q.append((i, j))

while q:
    tmp = []
    for h, w in q:
        if not visited[h - 1][w]:
            visited[h - 1][w] = True
            tmp.append((h - 1, w))
        if not visited[h + 1][w]:
            visited[h + 1][w] = True
            tmp.append((h + 1, w))
        if not visited[h][w - 1]:
            visited[h][w - 1] = True
            tmp.append((h, w - 1))
        if not visited[h][w + 1]:
            visited[h][w + 1] = True
            tmp.append((h, w + 1))
    q = tmp
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
visited = [[True] * (W + 2)]
visited += [[True] + [x == '#' for x in list(input())] + [True] for _ in range(H)]
visited += [[True] * (W + 2)]
ans = -1
q = []
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if visited[i][j]:
            q.append((i, j))

while q:
    tmp = []
    for h, w in q:
        for x, y in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            hx, wy = h + x, w + y
            if not visited[hx][wy]:
                visited[hx][wy] = True
                tmp.append((hx, wy))
    q = tmp
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int,input().split())
grid = []
dq = deque([])
dx = [1,-1,0,0]
dy = [0,0,1,-1]
ans = 0
d = [[-1 for i in range(w)] for j in range(h)]
for i in range(h):
    maze = list(input())
    for j in range(w):
        if maze[j] == "#":
            dq.append((j,i))
            d[i][j] = 0
    grid.append(maze)
while dq:
    x,y = dq.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx <= w-1 and 0 <= ny <= h-1 and grid[ny][nx] != "#" and d[ny][nx] == -1:
            dq.append((nx,ny))
            d[ny][nx] = d[y][x] + 1
            ans = max(ans,d[ny][nx])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
maze = []
for _ in range(h):
    maze.append(list(input()))
import collections
black = collections.deque([])
cnt = 0
for hh in range(h):
    for ww in range(w):
        if maze[hh][ww] == "#":
            cnt += 1
            black.append([hh, ww, 0])
dh = [ 0, -1, 1, 0]
dw = [ -1, 0, 0, 1]
res = 0
allcount = h*w
res = 0
while cnt < allcount:
    #print("black:", black)
    bh, bw , bturn= black.popleft()
    #print("pop", bh, bw, bturn)
    for di in range(len(dh)):
        nh = bh + dh[di]
        nw = bw + dw[di]
        if nh < 0 or nh > (h-1) or nw < 0 or nw > (w-1):
            continue
        if maze[nh][nw] == "#":
            continue
        black.append([nh, nw, bturn+1])
        #print(nh, nw)
        maze[nh][nw] = "#"
        res = max(res, bturn+1)
        cnt += 1
print(res)