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: Accepted

Solution code:
from collections import deque


def main():
    H, W = map(int, input().split())
    A = [input() for _ in range(H)]
    q = deque()
    visited = [[False] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                q.append((i, j, 0))
                visited[i][j] = True
    ans = 0
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    while len(q):
        i, j, cost = q.popleft()
        ans = max(ans, cost)
        for d in directions:
            ni = i + d[0]
            nj = j + d[1]
            if 0 <= ni < H and 0 <= nj < W and not visited[ni][nj]:
                q.append((ni, nj, cost+1))
                visited[ni][nj] = True
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

offsets = [(1, 0), (-1, 0), (0, 1), (0, -1)]
graph = [[float('inf')] * W for _ in range(H)]
deq = deque()

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

while deq:
    x, y = deq.popleft()
        
    for i, j in offsets:
        if (not 0 <= x + i < H) or (not 0 <= y + j < W):
            continue

        if graph[x + i][y + j] < float('inf'):
            continue

        if grid[x + i][y + j] == '#':
            continue
            
        graph[x + i][y + j] = graph[x][y] + 1
        deq.append((x + i, y + j))
        
print(max(max(v) for v in graph))

Submission status: Accepted

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

  q = []
  reached = [[True]*(w+2)]
  for i in range(1, h+1):
    reached.append([True] + [s == '#' for s in list(input())] + [True])
    for j in range(1,w+1):
      if reached[i][j]: q.append((i,j))
  reached.append([True]*(w+2))

  res = 0
  for i in range(100000000):
    qq = []
    for k,l in q:
      if not reached[k+1][l]:
        qq.append((k+1, l))
        reached[k+1][l] = True
      if not reached[k][l+1]:
        qq.append((k, l+1))
        reached[k][l+1] = True
      if not reached[k-1][l]:
        qq.append((k-1, l))
        reached[k-1][l] = True
      if not reached[k][l-1]:
        qq.append((k, l-1))
        reached[k][l-1] = True
    if len(qq) == 0:
      break
    else:
      pass

    q = qq
    res += 1

  print(res)
  return 0

if __name__ == "__main__":
  main()

Submission status: Accepted

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

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



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


while len(stack)!=0:
    now_point=stack.popleft()
    for i in range(4):
        target_h=now_point[0]+dx[i]
        target_w=now_point[1]+dy[i]
        if 0<=target_h<h and 0<=target_w<w:
            if a[target_h][target_w]==".":
                need_visited[target_h][target_w]=need_visited[now_point[0]][now_point[1]]+1
                a[target_h][target_w]="#"
                stack.append([target_h, target_w])
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans, need_visited[i][j])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

painted = deque()
for h in range(H):
    for w in range(W):
        if cell[h][w] == '#':
            painted.append([h, w, 0])

ans = 0
while len(painted) > 0:
    blackcell = painted.popleft()
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = blackcell[0] + dy
        nw = blackcell[1] + dx
        d = blackcell[2]
        if 0 <= nh < H and 0 <= nw < W and cell[nh][nw] == '.':
            cell[nh][nw] = '#'
            painted.append([nh, nw, d + 1])
        ans = d

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

painted = deque()
for h in range(H):
    for w in range(W):
        if cell[h][w] == '#':
            painted.append([h, w, 0])

ans = 0
while len(painted) > 0:
    blackcell = painted.popleft()
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = blackcell[0] + dy
        nw = blackcell[1] + dx
        d = blackcell[2]
        if 0 <= nh < H and 0 <= nw < W and cell[nh][nw] == '.':
            cell[nh][nw] = '#'
            painted.append([nh, nw, d + 1])
        ans = d

print(ans)

Submission status: Accepted

Solution code:
H, W = [int(x) for x in input().split()]
cell = [list(input()) for i in range(H)]

painted = []
for h in range(H):
    for w in range(W):
        if cell[h][w] == '#':
            painted.append([h, w])

ans = 0
while len(painted) > 0:
    to_be_painted = []
    for blackcell in painted:
        h = blackcell[0]
        w = blackcell[1]
        for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            nh = h + dy
            nw = w + dx
            if 0 <= nh and nh < H and 0 <= nw and nw < W and cell[nh][nw] == '.':
                cell[nh][nw] = '#'
                to_be_painted.append([nh, nw])
    painted = to_be_painted
    if len(painted) > 0: ans += 1

print(ans)

Submission status: Accepted

Solution code:
"""
解説と提出 #5747380を参考に作成
"""

from collections import deque


def solve():
    H, W = map(int, input().split())
    # mass = [[False] * W for _ in range(H)]
    # queue1 = deque([])
    # queue2 = deque([])
    queue1 = []
    queue2 = []
    mass = []
    mass.append([False] * (W + 2))  # 外枠
    for Hi in range(1, H + 1):
        mass.append([False] + [s == '.' for s in list(input())] + [False])
        for Wi in range(1, W + 1):
            if not mass[Hi][Wi]:
                queue1.append((Hi, Wi))
    mass.append([False] * (W + 2))  # 外枠
    import datetime
    d = datetime.datetime.now()
    count = -1
    while True:
        # print('count: {}, queue:{}'.format(count, len(queue1)))
        if len(queue1) == 0:
            break
        for h, w in queue1:
            # left
            if mass[h][w - 1]:
                mass[h][w - 1] = False
                queue2.append((h, w - 1))
            # right
            if mass[h][w + 1]:
                mass[h][w + 1] = False
                queue2.append((h, w + 1))
            # top
            if mass[h + 1][w]:
                mass[h + 1][w] = False
                queue2.append((h + 1, w))
            # button
            if mass[h - 1][w]:
                mass[h - 1][w] = False
                queue2.append((h - 1, w))

        count += 1
        queue1 = queue2
        queue2 = []
    print(count)

    # print(datetime.datetime.now() - d)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

H,W = map(int,input().split())
A = list(list(input()) for _ in range(H))
dirc = [(0,1),(1,0),(0,-1),(-1,0)]
q = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] =="#":
            A[i][j] = 0
            q.append((i,j))
ans = 0
while q:
    y,x = q.popleft()
    for dy,dx in dirc:
        if 0<=dy+y<H and 0<=dx+x<W and A[dy+y][dx+x]==".":
            A[dy+y][dx+x] = A[y][x]+1
            ans = max(ans,A[dy+y][dx+x])
            q.append((dy+y,dx+x))

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

H,W = map(int,input().split())
A = []
for i in range(H):
    A.append([0 if i == "#" else H+W for i in list(input())])
A = np.array(A)

for i in range(H-1):
  A[i+1, :] = np.minimum(A[i, :] + 1, A[i+1, :])
for i in range(H-1,0,-1):
  A[i-1,:] = np.minimum(A[i,:]+1,A[i-1,:])
for i in range(W-1):
  A[:,i+1] = np.minimum(A[:,i]+1,A[:,i+1])
for i in range(W-1,0,-1):
  A[:,i-1] = np.minimum(A[:,i]+1,A[:,i-1])
print(np.max(A))

Submission status: Accepted

Solution code:
import sys
import numpy as np

#%% Smart Solution

input = sys.stdin.readline

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

status = np.full((H, W), H*W, dtype=int)
for i in range(H):
    for j, c in enumerate(input()):
        if c == "#":
            status[i,j] = 0


for h in range(1, H):
    status[h, :] = np.minimum(status[h, :], status[h-1, :] + 1)
for h in range(0, H-1)[::-1]:
    status[h, :] = np.minimum(status[h, :], status[h+1, :] + 1)
for w in range(1, W):
    status[:, w] = np.minimum(status[:, w], status[:, w-1] + 1)
for w in range(0, W-1)[::-1]:
    status[:, w] = np.minimum(status[:, w], status[:, w+1] + 1)

print(np.max(status))

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
A=[[None]*(W+2)]
A.extend([[i=="." for i in "#"+input()+"#"] for _ in range(H)])
A.append([None]*(W+2))

#q=[[(i,j) for i in range(1,H+1) for j in range(1,W+1) if not A[i][j]]]
q=[(i,j) for i in range(1,H+1) for j in range(1,W+1) if not A[i][j]]

for k in range(2000):
#k=0
#while(q):
    r=[]
    #q.append([])
    #for i,j in q[k]:
    for i,j in q:
        if A[i-1][j]:
            A[i-1][j]=None
            #q[k+1].append((i-1,j))
            r.append((i-1,j))
        if A[i+1][j]:
            A[i+1][j]=None
            #q[k+1].append((i+1,j))
            r.append((i+1,j))
        if A[i][j-1]:
            A[i][j-1]=None
            #q[k+1].append((i,j-1))
            r.append((i,j-1))
        if A[i][j+1]:
            A[i][j+1]=None
            #q[k+1].append((i,j+1))
            r.append((i,j+1))
    if not len(r):
        break
    q=r
print(k)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
A=[[None]*(W+2)]
A.extend([[i=="." for i in "#"+input()+"#"] for _ in range(H)])
A.append([None]*(W+2))

#q=[[(i,j) for i in range(1,H+1) for j in range(1,W+1) if not A[i][j]]]
q=[(i,j) for i in range(1,H+1) for j in range(1,W+1) if not A[i][j]]

#for k in range(2000):
k=0
while(q):
    r=[]
    #q.append([])
    #for i,j in q[k]:
    for i,j in q:
        if A[i-1][j]:
            A[i-1][j]=None
            #q[k+1].append((i-1,j))
            r.append((i-1,j))
        if A[i+1][j]:
            A[i+1][j]=None
            #q[k+1].append((i+1,j))
            r.append((i+1,j))
        if A[i][j-1]:
            A[i][j-1]=None
            #q[k+1].append((i,j-1))
            r.append((i,j-1))
        if A[i][j+1]:
            A[i][j+1]=None
            #q[k+1].append((i,j+1))
            r.append((i,j+1))
    if not len(r):
        break
    q=r
    k+=1
print(k)

Submission status: Accepted

Solution code:
import numpy as np
from scipy import ndimage

h, w = map(int, input().split())
map = [input() for _ in range(h)]
mapB = np.zeros((h, w))
for i, ii in enumerate(map):
  for j, jj in enumerate(ii):
    if jj == '.':
      mapB[i, j] = 1
dist = ndimage.distance_transform_cdt(mapB, metric="taxicab")
print(dist.max())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from scipy import ndimage
s = sys.stdin.readlines()
N, W = map(int, s[0].split())
W_matrix = [list(line.strip()) for line in s[1:N + 1]]
matrix_like_list = [[1 if x == "." else 0 for x in W_list] for W_list in W_matrix]
dist = ndimage.distance_transform_cdt(matrix_like_list, metric="taxicab")
print(dist.max())

Submission status: Accepted

Solution code:
from scipy.ndimage import*;print(morphology.distance_transform_cdt([[t>'#'for t in s[:-1]]for s in open(0)][1:],'taxicab').max())

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

grid = [[v for v in input()[:-1]] for _ in range(H)]

Q = []
cnt = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] == "#":
            Q.append([i, j])
            cnt += 1

DX = [-1, 1, 0, 0]
DY = [0, 0, -1, 1]
d = 0
while cnt < H*W:
    d += 1
    tmp = []
    for sx, sy in Q:
        for x, y in zip(DX, DY):
            new_x = sx+x
            new_y = sy+y
            if 0 <= new_x < H and 0 <= new_y < W:
                if grid[new_x][new_y] == ".":
                    grid[new_x][new_y] = "#"
                    tmp.append([new_x, new_y])
                    cnt += 1
            else:
                continue
    Q = tmp

print(d)

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

H, W = map(int, input().split())
grid = [[v for v in input()[:-1]] for _ in range(H)]

Q = []
cnt = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] == "#":
            Q.append([i, j])
            cnt += 1

DX = [-1, 1, 0, 0]
DY = [0, 0, -1, 1]
d = 0
# for _ in range(5):
while cnt < H*W:
    d += 1
    tmp = []
    #print("d->", d)
    # print(Q)
    # print(dist)
    # print(cnt)
    # print("-------")
    for x, y in Q:
        for dx, dy in zip(DX, DY):
            nx = x+dx
            ny = y+dy
            if 0 <= nx < H and 0 <= ny < W:
                if grid[nx][ny] == ".":
                    grid[nx][ny] = "#"
                    tmp.append([nx, ny])
                    cnt += 1
            else:
                continue
    Q = tmp
# print(dist)
print(d)

Submission status: Accepted

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

grid = []
blacks = []
for i in range(H):
    row = list(input(""))
    grid.append(row)

    for idx, r in enumerate(row):
        if r == "#":
            blacks.append((i, idx))

c = 0
while len(blacks) > 0:
    c += 1

    new_blacks = []
    for b in blacks:
        top = b[0] - 1
        bottom = b[0] + 1
        left = b[1] - 1
        right = b[1] + 1

        if top >= 0:
            if grid[top][b[1]] == ".":
                grid[top][b[1]] = "#"
                new_blacks.append((top, b[1]))
        if bottom < H:
            if grid[bottom][b[1]] == ".":
                grid[bottom][b[1]] = "#"
                new_blacks.append((bottom, b[1]))
        if left >= 0:
            if grid[b[0]][left] == ".":
                grid[b[0]][left] = "#"
                new_blacks.append((b[0], left))
        if right < W:
            if grid[b[0]][right] == ".":
                grid[b[0]][right] = "#"
                new_blacks.append((b[0], right))

    blacks = new_blacks

print(c - 1)

Submission status: Accepted

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．
from collections import deque
import copy

def main():
  H, W = list(map(int, input().split()))
  L = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
  cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  result = 0
  while True:
    nq = deque()
    while q:
      i, j = q.popleft()
      if i > 0 and not L[i-1][j]:
        L[i-1][j] = True
        nq.append((i-1, j))
      if j > 0 and not L[i][j-1]:
        L[i][j-1] = True
        nq.append((i, j-1))
      if i < H-1 and not L[i+1][j]:
        L[i+1][j] = True
        nq.append((i+1, j))
      if j < W-1 and not L[i][j+1]:
        L[i][j+1] = True
        nq.append((i, j+1))
    if nq:
      q = copy.copy(nq)
    else:
      break    
    result += 1
  print(result)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
#bfs2-AGC033A
h,w=map(int,input().split())
s=[input() for _ in range(h)]

from collections import deque

sxy=[]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            sxy.append([i,j])
ddx=[1,-1,0,0]
ddy=[0,0,1,-1]

t=[[-1 for _ in range(w)] for _ in range(h)]
q=deque()
for txy in sxy:
    q.append(txy)
    t[txy[0]][txy[1]]=0

count=0
while q:
    y,x=q.popleft()
    count+=1
    for (dx,dy) in zip(ddx,ddy):
        ny=y+dy
        nx=x+dx
        if not (0<=nx<w and 0<=ny<h):continue
        if t[ny][nx]==-1:
            t[ny][nx]=t[y][x]+1
            q.append([ny,nx])
a=0
for i in range(h):
    for j in range(w):
        a=max(a,t[i][j])
print(a)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    from collections import deque

    h, w = map(int, input().split())
    a = [input() for _ in range(h)]
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    dist = [[-1 for __ in range(w)] for _ in range(h)]
    blacks = deque()

    # See:
    # http://drken1215.hatenablog.com/entry/2019/05/05/223200?_ga=2.177845805.987014750.1556545680-1855989383.1556545680
    # https://blog.kichi2004.jp/2019/05/agc033/
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                dist[i][j] = 0
                blacks.append((i, j))

    while blacks:
        current = blacks.popleft()
        cur_x = current[1]
        cur_y = current[0]

        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]

            if next_x < 0 or next_x >= w or next_y < 0 or next_y >= h:
                continue

            if dist[next_y][next_x] == -1:
                dist[next_y][next_x] = dist[cur_y][cur_x] + 1
                blacks.append((next_y, next_x))

    ans = 0

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    from collections import deque

    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    dist = [[-1 for __ in range(w)] for _ in range(h)]
    blacks = deque()

    # See:
    # http://drken1215.hatenablog.com/entry/2019/05/05/223200?_ga=2.177845805.987014750.1556545680-1855989383.1556545680
    # https://blog.kichi2004.jp/2019/05/agc033/
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                dist[i][j] = 0
                blacks.append((i, j))

    while blacks:
        current = blacks.popleft()
        cur_x = current[1]
        cur_y = current[0]

        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]

            if next_x < 0 or next_x >= w or next_y < 0 or next_y >= h:
                continue

            if dist[next_y][next_x] == -1:
                dist[next_y][next_x] = dist[cur_y][cur_x] + 1
                blacks.append((next_y, next_x))

    ans = 0

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def sol():
    h,w=map(int,input().split())
    l=[]
    d=set()
    for i in range(h):
        s=list(input())
        for j in range(w):
            if s[j]=="#": d.add((i,j))
        l.append(s)
    ans=-1
    for i in range(2000):
        if len(d)==0: break
        ans+=1
        t=set()
        for j in d:
            if 0<=j[0]+1<h and l[j[0]+1][j[1]]==".":
                l[j[0]+1][j[1]]="#"
                t.add((j[0]+1,j[1]))
            if 0<=j[0]-1<h and l[j[0]-1][j[1]]==".":
                l[j[0]-1][j[1]]="#"
                t.add((j[0]-1,j[1]))
            if 0<=j[1]+1<w and l[j[0]][j[1]+1]==".":
                l[j[0]][j[1]+1]="#"
                t.add((j[0],j[1]+1))
            if 0<=j[1]-1<w and l[j[0]][j[1]-1]==".":
                l[j[0]][j[1]-1]="#"
                t.add((j[0],j[1]-1))
        d=t
    print(ans)

if __name__ == "__main__":
    sol()

Submission status: Accepted

Solution code:
H,W = [ int(it) for it in input().split() ]
li = [ [1 if it=="#" else 0 for it in input() ] for i in range(H) ]
#[print(it) for it in li]

po = []
for i in range(H):
  for j in range(W):
    if li[i][j]==1:
      po.append( (i,j) )
g = 0
for i in range(10000):
  po_ = []
  s = 0
  dw=[[0,1],[0,-1],[1,0],[-1,0]]
  for p,q in po:
    for dp,dq in dw:
      if ( 0<=p+dp and p+dp<H and 0<=q+dq and q+dq<W ):
        if (li[p+dp][q+dq]==0):
          s += 1
          li[p+dp][q+dq]=1
          po_.append( (p+dp,q+dq) )
  if (s==0):
    break
  else:
    g += 1
  po = po_
      
#[print(it) for it in li]
print (g)

Submission status: Accepted

Solution code:
import numpy as np

H, W = map(int, input().split())
b = []
for _ in range(H):
    b.append([0 if i == "#" else H+W for i in list(input())])
a = np.array(b)

for i in range(1, H):
    a[i, :] = np.minimum(a[i, :], a[i-1, :] + 1)
for i in range(H - 2, -1, -1):
    a[i, :] = np.minimum(a[i, :], a[i+1, :] + 1)
for j in range(1, W):
    a[:, j] = np.minimum(a[:,j], a[:, j-1] + 1)
for j in range(W -2, -1, - 1):
    a[:, j] = np.minimum(a[:, j], a[:, j+1] + 1)

print(np.max(a))

Submission status: Accepted

Solution code:
def bfs(q_list):
    cnt = -1
    while q_list:
        cnt += 1
        new_q_list = []
        for h, w in q_list:
            if not m_list[h][w+1]:
                m_list[h][w+1] = True
                new_q_list.append((h, w+1))
            if not m_list[h+1][w]:
                m_list[h+1][w] = True
                new_q_list.append((h+1, w))
            if not m_list[h][w-1]:
                m_list[h][w-1] = True
                new_q_list.append((h, w-1))
            if not m_list[h-1][w]:
                m_list[h-1][w] = True
                new_q_list.append((h-1, w))
        q_list = new_q_list
    print(cnt)


if __name__ == "__main__":
    h_len, w_len = map(int, input().split())
    m_list = [[True for _ in range(w_len+2)]]
    q_list = []
    for i in range(h_len):
        tmp = [True]
        s_in = input()
        for j, s in enumerate(s_in):
            if s == '#':
                q_list.append((i+1, j+1))
                tmp.append(True)
            else:
                tmp.append(False)
        tmp.append(True)
        m_list.append(tmp)
    m_list.append([True for _ in range(w_len+2)])
    bfs(q_list)

Submission status: Accepted

Solution code:
def bfs(q_list):
    cnt = -1
    while q_list:
        cnt += 1
        new_q_list = []
        for h, w in q_list:
            if not m_list[h][w+1]:
                m_list[h][w+1] = True
                new_q_list.append((h, w+1))
            if not m_list[h+1][w]:
                m_list[h+1][w] = True
                new_q_list.append((h+1, w))
            if not m_list[h][w-1]:
                m_list[h][w-1] = True
                new_q_list.append((h, w-1))
            if not m_list[h-1][w]:
                m_list[h-1][w] = True
                new_q_list.append((h-1, w))
        q_list = new_q_list
    print(cnt)


if __name__ == "__main__":
    h_len, w_len = map(int, input().split())
    m_list = [[True for _ in range(w_len+2)]]
    for _ in range(h_len):
        m_list.append([True] + [s=='#' for s in input()] + [True])
    m_list.append([True for _ in range(w_len+2)])
    q_list = []
    for h, w_list in enumerate(m_list):
        if 0 < h < h_len+1:
            for w, a in enumerate(w_list):
                if 0 < w < w_len + 1 and a:
                    q_list.append((h, w))
    bfs(q_list)

Submission status: Accepted

Solution code:
def bfs(q_list):
    cnt = -1
    while q_list:
        cnt += 1
        new_q_list = []
        for h, w in q_list:
            if not m_list[h][w+1]:
                m_list[h][w+1] = True
                new_q_list.append((h, w+1))
            if not m_list[h+1][w]:
                m_list[h+1][w] = True
                new_q_list.append((h+1, w))
            if not m_list[h][w-1]:
                m_list[h][w-1] = True
                new_q_list.append((h, w-1))
            if not m_list[h-1][w]:
                m_list[h-1][w] = True
                new_q_list.append((h-1, w))
        q_list = new_q_list
    print(cnt)


if __name__ == "__main__":
    h_len, w_len = map(int, input().split())
    m_list = [[True for _ in range(w_len+2)]]
    for _ in range(h_len):
        m_list.append([True] + [s=='#' for s in input()] + [True])
    m_list.append([True for _ in range(w_len+2)])
    q_list = []
    for h in range(1, h_len+1):
        for w in range(1, w_len+1):
            if m_list[h][w]:
                q_list.append((h, w))
    bfs(q_list)

Submission status: Accepted

Solution code:
from collections import deque
h,w=(int(i) for i in input().split())
#print(h,w)

a=[[i for i in input()] for j in range(h)]
#print(a)

cnt=0
ans=0
black=deque([])
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            cnt+=1
            black.append((i,j))
dy=deque([1,0,-1,0])
dx=deque([0,1,0,-1])
#print(black)
#print(cnt)

while cnt<h*w:
    for i in range(len(black)):
        data=black.popleft()
        for j in range(4):
            if 0<=data[0]+dy[j]<h and 0<=data[1]+dx[j]<w:
                if a[data[0]+dy[j]][data[1]+dx[j]]=='.':
                    a[data[0]+dy[j]][data[1]+dx[j]]='#'
                    cnt+=1
                    black.append((data[0]+dy[j],data[1]+dx[j]))
    ans+=1
    
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

H,W = map(int,input().split())
A = []
for i in range(H):
    A.append([0 if i == "#" else H+W for i in list(input())])
A = np.array(A)

for i in range(H-1):
  A[i+1, :] = np.minimum(A[i, :] + 1, A[i+1, :])
for i in range(H-1,0,-1):
  A[i-1,:] = np.minimum(A[i,:]+1,A[i-1,:])
for i in range(W-1):
  A[:,i+1] = np.minimum(A[:,i]+1,A[:,i+1])
for i in range(W-1,0,-1):
  A[:,i-1] = np.minimum(A[:,i]+1,A[:,i-1])
print(np.max(A))

Submission status: Accepted

Solution code:
def cnt(h,w):
  q=[]
  arr=[[True]*(w+2)]
  arr.extend([[True]+[s!='.' for s in input()]+[True] for _ in range(h)])
  arr.append([True]*(w+2))
  for i in range(1,h+1):
    for j in range(1,w+1):
      if arr[i][j]:
        q.append([i,j])
  ans=0
  while 1:
    nq=[]
    for y,x in q:
      if not arr[y-1][x]:
        nq.append((y-1,x))
        arr[y-1][x]=True
      if not arr[y][x-1]:
        nq.append((y,x-1))
        arr[y][x-1]=True
      if not arr[y+1][x]:
        nq.append((y+1,x))
        arr[y+1][x]=True
      if not arr[y][x+1]:
        nq.append((y,x+1))
        arr[y][x+1]=True
    if len(nq)==0:
      break
    else:
      q=nq
      ans+=1
  return ans
    
h,w=map(int,input().split())
print(cnt(h,w))

Submission status: Accepted

Solution code:
import collections
q=collections.deque()
h,w=map(int,input().split())
arr=[[] for _ in range(h+2)]
for i in range(w+2):
  arr[0].append('#')
for i in range(h):
  arr[i+1].append('#')
  for j in input():
    arr[i+1].append(j)
  arr[i+1].append('#')
for i in range(w+2):
  arr[h+1].append('#')
dx=[-1,0,1,0]
dy=[0,-1,0,1]
for i in range(1,h+1):
  for j in range(1,w+1):
    if arr[i][j]=='#':
      q.append([i,j,0])
while 1:
  y,x,cnt=q.popleft()
  for i in range(4):
    if arr[y+dy[i]][x+dx[i]]=='.':
      q.append([y+dy[i],x+dx[i],cnt+1])
      arr[y+dy[i]][x+dx[i]]='#'
  if len(q)==0:
    print(cnt)
    break

Submission status: Accepted

Solution code:
def f(h, w):
    dt = [[-1, 0], [0, -1], [0, 1], [1, 0]]
    t = [[True] * (w + 2)]
    for _ in range(h):
        t += [[True] + [(c == "#") for c in input()] + [True]]
    t += [[True] * (w + 2)]
    kuro = []
    for i, ti in enumerate(t[1:-1]):
        for j, tij in enumerate(ti[1:-1]):
            if tij:
                kuro+=[(i + 1, j + 1)]
    cnt = -1
    while kuro:
        cnt += 1
        nxt = []
        for i, j in kuro:
            ti=t[i]
            if not ti[j+1]:
                ti[j + 1]=True
                nxt += [(i, j+1)]
            if not ti[j-1]:
                ti[j - 1]=True
                nxt += [(i, j-1)]
            if not t[i - 1][j]:
                t[i - 1][j]=True
                nxt += [(i - 1, j)]
            if not t[i + 1][j]:
                t[i + 1][j]=True
                nxt += [(i + 1, j)]
        kuro = nxt
    print(cnt)
 
 
h, w = map(int, input().split())
f(h, w)

Submission status: Accepted

Solution code:
import numpy as np

H, W = map(int, input().split())
val = []
INF = 10**9
for i in range(H):
    tmp = input()
    val.append([0 if tmp[j] == '#' else INF for j in range(W)])
val = np.array(val)

for i in range(H-1):
    val[i+1, :] = np.minimum(val[i, :]+1, val[i+1, :])
for i in range(H-1, 0, -1):
    val[i-1, :] = np.minimum(val[i, :]+1, val[i-1, :])
for j in range(W-1):
    val[:, j+1] = np.minimum(val[:, j]+1, val[:, j+1])
for j in range(W-1, 0, -1):
    val[:, j-1] = np.minimum(val[:, j]+1, val[:, j-1])

print(val.max())

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product
from collections import deque

H, W = map(int, input().split())
val = []
INF = 10**9
for i in range(H):
    tmp = input()
    val.append([0 if tmp[j] == '#' else INF for j in range(W)])
val = np.array(val)

for i in range(H-1):
    val[i+1, :] = np.minimum(val[i, :]+1, val[i+1, :])
for i in range(H-1, 0, -1):
    val[i-1, :] = np.minimum(val[i, :]+1, val[i-1, :])
for j in range(W-1):
    val[:, j+1] = np.minimum(val[:, j]+1, val[:, j+1])
for j in range(W-1, 0, -1):
    val[:, j-1] = np.minimum(val[:, j]+1, val[:, j-1])

print(val.max())

Submission status: Accepted

Solution code:
from collections import deque
 
 
h, w = map(int, input().split())
hs, ws = set(range(h)), set(range(w))
d = deque()
memo = [[-1] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
a = tuple(input() for _ in hs)
b = [[i, j] for i in hs for j in ws if a[i][j] == '#']
for i, j in b:
    d.append((i, j))
    memo[i][j] = 0
while d:
    dh, dw = d.popleft()
    for i, j in move:
        dhn, dwn = dh + i, dw + j
        if (0 <= dhn < h) and (0 <= dwn < w) and (memo[dhn][dwn] < 0):
            d.append((dhn, dwn))
            memo[dhn][dwn] = memo[dh][dw] + 1
ans = max([max(e) for e in memo])
print(ans)