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:
h,w=map(int,input().split())
a=[[] for _ in range(h)]
for i in range(h):
    s=input()
    for j in s:
        if j=='.':
            a[i].append(-1)
        else:
            a[i].append(0)

def bfs():
    d=[[0,1],[1,0],[-1,0],[0,-1]]
    q=[]
    c=-1
    for i in range(h):
        for j in range(w):
            if a[i][j]==0:
                q.append((i,j))
    while q:
        t=q[:]
        q=[]
        c+=1
        for i,j in t:
            for dd in d:
                di,dj=dd[0],dd[1]
                if (i+di)*(h-1-i-di)>=0 and (j+dj)*(w-1-j-dj)>=0 and a[i+di][j+dj]<0:
                    a[i+di][j+dj]=1
                    q.append((i+di,j+dj))
    return(c)

print(bfs())

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
AA = [list(input()) for _ in range(h)]
# AA[h][w]
infi = 10 ** 5
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))
            ans[i][j] = 0

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


que = deque(kouho)
while que:
    py, px, d = que.popleft()
    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:
            ans[ny][nx] = d + 1
            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: Accepted

Solution code:
from collections import deque

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

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

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

ans = 0
while que:
    x, y = que.popleft()
    for dx, dy in dxdy:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < w and 0 <= ny < h and d[ny][nx] == -1:
            que.append((nx, ny))
            d[ny][nx] = d[y][x] + 1
            ans = max(ans, d[ny][nx])

print(ans)

Submission status: Accepted

Solution code:
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) ]
z= [[False for _ in range(W)] for _ in range(H)]
ans=0

v=deque([])
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            v.append( [i,j] )
            z[i][j]=True
            d[i][j]=0
while v:
    a=v.popleft()
    #print(a,v)
    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]=d[a[0]][a[1]]+1
                v.append([s,t])
                ans=max(ans,d[s][t])
#print(d)
print(ans)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
H,W = IL()
S = SLs(H)

BL = []
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      BL.append((i,j))
d = [[-1 for j in range(W)] for i in range(H)]
for i,j in BL:
  d[i][j] = 0
q = deque(BL)
dx = [-1,1,0,0]
dy = [0,0,-1,1]
while q:
  y,x = q.popleft()
  for i in range(4):
    nx,ny = x+dx[i], y+dy[i]
    if 0<=nx<W and 0<=ny<H:
      if d[ny][nx] == -1:
        d[ny][nx] = d[y][x] + 1
        q.append((ny,nx))
print(max(max(d[i][j] for j in range(W)) for i in range(H)))

Submission status: Accepted

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

h,w = map(int,readline().split())
a = read().split()

color = [[0]*(w+2) for _ in range(h+2) ]
stack = []
for i in range(h):
    for j in range(w):
        if(a[i][j] == '#'):
            color[i+1][j+1] = 1
            stack.append((i+1,j+1))

for i in range(h+2):
    color[i][0] = 1
    color[i][-1] = 1

for j in range(w+2):
    color[0][j] = 1
    color[-1][j] = 1

ans = -1
while(stack):
    ans += 1
    new_stack = []
    while(stack):
        i,j = stack.pop()
        for x,y in zip([0,0,-1,1],[-1,1,0,0]):
            x += i
            y += j
            if(color[x][y]==0):
                color[x][y] = 1
                new_stack.append((x,y))

    stack = new_stack[::]

print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def bfs(que, maze, dis):
    max_x = len(maze[0])
    max_y = len(maze)

    while len(q) > 0:
        x, y, d = que.popleft()
        dxy = [[-1, 0], [1, 0], [0, 1], [0, -1]]

        for dx, dy in dxy:
            nx = x + dx
            ny = y + dy

            if 0 > nx or max_x <= nx or 0 > ny or max_y <= ny:
                continue
            if maze[ny][nx] == "#":
                continue
            if dis[ny][nx] != -1:
                continue

            dis[ny][nx] = d + 1
            que.append([nx, ny, dis[ny][nx]])

    return


h, w = map(int, input().split())
maze = [[] for _ in range(h)]
distance = [[-1] * w for _ in range(h)]

for i in range(h):
    maze[i] = input()

q = deque()

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

bfs(q, maze, distance)

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

print(ans)

Submission status: Accepted

Solution code:
import sys
#import numpy as np
import math
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
input=sys.stdin.readline
h,w=map(int,input().split())
a=[list(map(str,input())) for _ in range(h)]
b=deque()
n=[-1]*(h*w)
p=((1,0),(-1,0),(0,1),(0,-1))
for x in range(h):
  for y in range(w):
    if a[x][y]=="#":
      b.append((x,y))
      n[x*w+y]=0
while b:
  x,y=b.popleft()
  for idx in p:
    s,t=idx
    if 0<=x+s<h and 0<=y+t<w:
      if n[(x+s)*w+(y+t)]==-1:
        n[(x+s)*w+(y+t)]=n[x*w+y]+1
        b.append((x+s,y+t))
print(max(n))

Submission status: Accepted

Solution code:
from collections import deque, Counter


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

    while que:
        p = que.popleft()
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]

            if 0 <= ny < H and 0 <= nx < W and dist[ny][nx] == -1:
                dist[ny][nx] = dist[p[0]][p[1]] + 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: Accepted

Solution code:
from collections import deque

import sys
input = sys.stdin.readline

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

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

queue = deque()

for x in range(H):
    for y in range(W):
        if A[x][y] == '#':
            z = x * W + y
            queue.append(z)
            dist[z] = 0

while queue:
    z = queue.popleft()
    x, y = divmod(z, W)
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if not (0 <= nx < H and 0 <= ny < W):
            continue
        nz = nx * W + ny
        if dist[nz] != -1:
            continue
        dist[nz] = dist[z] + 1
        queue.append(nz)

print(max(dist))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)
from collections import deque

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


H, W = MI()
grid = [list(input()) for _ in range(H)]

seen = set()
q = deque()
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            q.append((i, j, 0))
            seen.add(i * W + j)
while len(q) > 0:
    h, w, d = q.popleft()
    for dh, dw in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        if 0 <= h + dh < H and 0 <= w + dw < W and (h + dh) * W + w + dw not in seen:
            q.append((h + dh, w + dw, d + 1))
            seen.add((h + dh) * W + w + dw)
print(d)

Submission status: Accepted

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

visited = [[False]*(W+2) for _ in range(H+2)]
dh = [0,1,0,-1]
dw = [1,0,-1,0]

from collections import deque
d = deque()

S = [0]*(H+2)
S[0] = '*'*(W+2)
S[H+1] = '*'*(W+2)
white = 0
for h in range(1,H+1):
    S[h] = '*' + input() + '*'
    for w in range(1,W+1):
        if S[h][w]=='#':
            visited[h][w]=True
            d.append((h,w,0))
    


while len(d)>0:
    h,w,cnt = d.popleft()
    for i in range(4):
        h0 = h+dh[i]
        w0 = w+dw[i]
        if S[h0][w0]=='.' and visited[h0][w0]==False:
            visited[h0][w0]=True
            d.append((h0,w0,cnt+1))
print(cnt)

Submission status: Accepted

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

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

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))

moves = [(0,1),(0,-1),(1,0),(-1,0)] #全方向調べる

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

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))

moves = [(0,1),(0,-1),(1,0),(-1,0)] #全方向調べる

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

Solution code:
from collections import deque
def main():
    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)
main()

Submission status: Accepted

Solution code:
from collections import deque

dy = (1, 0, -1, 0)
dx = (0, 1, 0, -1)

h, w = map(int, input().split())
table = []
for _ in range(h):
    table.append(list(input()))
q = deque()
for y in range(h):
    for x in range(w):
        if table[y][x] == "#":
            q.append((y, x))
            table[y][x] = 0

while q:
    y, x = q.popleft()
    d = table[y][x]
    for k in range(4):
        ny, nx = y + dy[k], x + dx[k]
        if 0 <= ny < h and 0 <= nx < w:
            if table[ny][nx] == ".":
                table[ny][nx] = d + 1
                q.append((ny, nx))
print(max(list(map(lambda n: max(n), table))))

Submission status: Accepted

Solution code:

import numpy as np
from collections import deque

def parse():
  H, W = map(int, input().split(" "))
  grid = [list(input()) for y in range(H)]
  return H, W, grid

def print_grid(grid):
  H = len(grid)
  print("grid:")
  for line in grid:
    for c in line:
      print(c, end="")
    print("")

def main():
  H, W, grid = parse()
  # print(H, W)
  # print_grid(grid)

  dark_points = [(x + 1, y + 1) for x in range(W) for y in range(H) if grid[y][x] == "#"]

  visited = [[True] * (W + 2)]
  visited += [[True] + [False for x in range(W)] + [True] for y in range(H)]
  visited.append([True for x in range(W + 2)])
  # for y in range(H + 2):
  #   print(visited[y])
  # exit(0)
  for x, y in dark_points:
    visited[y][x] = True
  
  # visited = np.zeros((H, W), int)
  # for y in range(H):
  #   for x in range(W):
  #     if grid[y][x] == ".":
  #       visited[y][x] = H * W

  # for y in range(1, H):  # ↓
  #   visited[y][:] = np.minimum(visited[y][:], visited[y - 1][:] + 1)

  # for y in range(H - 2, -1, -1):
  #   visited[y, :] = np.minimum(visited[y, :], visited[y + 1][:] + 1)

  # for x in range(1, W):
  #   visited[:, x] = np.minimum(visited[:, x], visited[:, x - 1] + 1)

  # for x in range(W - 2, -1, -1):
  #   visited[:, x] = np.minimum(visited[:, x], visited[:, x + 1] + 1)

  # print(dark_points)
  # exit(0)

  q = dark_points
  ans = 0
  while len(q) > 0:
    ans += 1
    next_q = []
    for x, y in q:
      if not visited[y - 1][x]: # 上
        visited[y - 1][x] = ans
        next_q.append((x, y - 1))
      if not visited[y + 1][x]: # 下
        visited[y + 1][x] = ans
        next_q.append((x, y + 1))
      if not visited[y][x - 1]: # 左
        visited[y][x - 1] = ans
        next_q.append((x - 1, y))
      if not visited[y][x + 1]: # 右
        visited[y][x + 1] = ans
        next_q.append((x + 1, y))
      
    # for y in range(H + 2):
    #   print(visited[y])
    # input()
    
    q = next_q

  print(ans - 1)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
H, W = map(int, input().rstrip().split())
checked = [[True]*(W+2)]
checked += [[True] + [ch == "#" for ch in input().rstrip()] + [True]
            for i in range(H)]
checked.append([True]*(W+2))

black_list = []
# 初期化
# 0 => 黒、 -1 => 白
for i in range(1, H+1):
    for j in range(1, W+1):
        if checked[i][j]:
            black_list.append((i, j))

# 黒の周辺4方向のうち、白だったら黒にする
ans = -1
while black_list:
    ans += 1
    tmp = []
    for x, y in black_list:
        # 上
        if not checked[x-1][y]:
            checked[x-1][y] = True
            tmp.append((x-1, y))
        # 下
        if not checked[x+1][y]:
            checked[x+1][y] = True
            tmp.append((x+1, y))
        # 左
        if not checked[x][y-1]:
            checked[x][y-1] = True
            tmp.append((x, y-1))

        # 右
        if not checked[x][y+1]:
            checked[x][y+1] = True
            tmp.append((x, y+1))

    black_list = tmp

print(ans)

Submission status: Accepted

Solution code:

import numpy as np

def parse():
  H, W = map(int, input().split(" "))
  grid = [list(input()) for y in range(H)]
  return H, W, grid

def print_grid(grid):
  H = len(grid)
  print("grid:")
  for line in grid:
    for c in line:
      print(c, end="")
    print("")

def main():
  H, W, grid = parse()
  # print(H, W)
  # print_grid(grid)

  # visited = [[W * H if grid[y][x] == "." else 0 for x in range(W)] for y in range(H)]
  visited = np.zeros((H, W), int)
  for y in range(H):
    # visited.append([])
    for x in range(W):
      if grid[y][x] == ".":
        visited[y][x] = H * W

  for y in range(1, H):  # ↓
    # 要素ごとの処理
    # print(visited)
    visited[y][:] = np.minimum(visited[y][:], visited[y - 1][:] + 1)
    # print(visited)
    # input()
    # print(visited[y])
    # exit(0)

  for y in range(H - 2, -1, -1):
    visited[y, :] = np.minimum(visited[y, :], visited[y + 1][:] + 1)

  for x in range(1, W):
    visited[:, x] = np.minimum(visited[:, x], visited[:, x - 1] + 1)

  for x in range(W - 2, -1, -1):
    visited[:, x] = np.minimum(visited[:, x], visited[:, x + 1] + 1)

  # print(visited)
  # exit(0)

  # max_len = 0
  # for y in range(H):
  #   max_val = max(visited[y])
  #   max_len = max_len if max_len > max_val else max_val
  # print(max_len)
  print(np.max(visited))

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from collections import deque
def main():
    H,W = map(int, input().split())
    road = [[False]*W for _ in range(H)]
    arrived = [[False]*W for _ in range(H)]
    que = deque([]) # BFS:appendleftとpopでキュー
    origWhite = 0
    for i in range(H):
        c = input()
        for j in range(W):
            if c[j]=='.':
                road[i][j] = True
                origWhite += 1
            else:
                que.append((i,j))
                arrived[i][j] = True

    if origWhite<=0:
        print(0)
        return

    directions = [(1,0),(0,1),(-1,0),(0,-1)] # 東西南北に移動可能
    depth = [[0]*W for _ in range(H)]
    while que:
        x1,y1 = que.pop()
        for dx,dy in directions:
            x2,y2 = x1+dx,y1+dy
            # 枠外
            if x2<0 or H<=x2 or y2<0 or W<=y2:
                continue
            # 壁
            if not road[x2][y2]:
                continue
            # 探索済み
            if arrived[x2][y2]:
                continue
            que.appendleft((x2,y2))
            arrived[x2][y2] = True
            origWhite -= 1
            depth[x2][y2] = depth[x1][y1]+1
            if origWhite<=0:
                print(depth[x2][y2])
                return


main()

Submission status: Accepted

Solution code:
import sys
#import numpy as np
import math
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
input=sys.stdin.readline
h,w=map(int,input().split())
a=[list(map(str,input())) for _ in range(h)]
b=deque()
n=[-1]*(h*w)
c=0
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
             b.append((i,j))
             n[i*w+j]=0
        else:
            continue
while b:
    z=b.popleft()
    i=z[0]
    j=z[1]
    if i<h-1 and n[(i+1)*w+j]==-1:
      n[(i+1)*w+j]=n[i*w+j]+1
      c=max(c,n[i*w+j]+1)
      b.append(((i+1),j))
      f=True
    if i>0  and n[(i-1)*w+j]==-1:
      n[(i-1)*w+j]=n[i*w+j]+1
      c=max(c,n[i*w+j]+1)
      b.append(((i-1),j))
      f=True
    if j<w-1 and n[i*w+(j+1)]==-1:
      f=True
      n[i*w+(j+1)]=n[i*w+j]+1
      c=max(c,n[i*w+j]+1)
      b.append((i,(j+1)))
    if j>0  and n[i*w+(j-1)]==-1:
      f=True
      n[i*w+(j-1)]=n[i*w+j]+1
      c=max(c,n[i*w+j]+1)
      b.append((i,(j-1)))
   
print(c)

Submission status: Accepted

Solution code:
import sys
#import numpy as np
import math
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
input=sys.stdin.readline
h,w=map(int,input().split())
a=[list(map(str,input())) for _ in range(h)]
b=deque()
n=[-1]*(h*w)
c=0
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
             b.append((i,j))
             n[i*w+j]=0
        else:
            continue
p = [(1,0),(-1,0),(0,1),(0,-1)]

while b:
    i,j=b.popleft()
    for s,t in p:
      if 0 <= i+s <= h-1 and 0 <= j+t <= w-1:
        if n[(i+s)*w+(j+t)]==-1:
          n[(i+s)*w+(j+t)]=n[i*w+j]+1
          c=max(c,n[i*w+j]+1)
          b.append(((i+s),(j+t)))
    
print(c)

Submission status: Accepted

Solution code:
from scipy import array, ndimage
H, _ = map(int, input().split())
print(ndimage.distance_transform_cdt(array([[c == "." for c in input()] for _ in range(H)], dtype=bool), metric="taxicab").max())

Submission status: Accepted

Solution code:
from collections import deque
h,w = list(map(int,input().split()))
f = []
q = deque()
for i in range(h):
    a = list(input())
    for j in range(w):
        if a[j] == '#':
            q.append([0,i,j])
    f.append(a)
 
ans =0
dxy = [0,1,0,-1,0]
while(len(q)):
    c,y,x = q.popleft()
    for i in range(4):
        ny = y+dxy[i]
        nx = x+dxy[i+1]
        if nx >= w or ny >= h or nx <0 or ny <0:
            continue
        if f[ny][nx] == '.':
            f[ny][nx] = c+1
            q.append([c+1,ny,nx])
            ans = max(ans,c+1)
        elif f[ny][nx] != '#' and f[ny][nx] > c+1:
            f[ny][nx] = c+1
            q.append([c+1,ny,nx])
            ans = max(ans,c+1)
 
print(ans)

Submission status: Accepted

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

m = [list(input()) for _ in range(h)]

start_points = [(y,x) for y in range(h) for x in range(w) if m[y][x] == '#']

def bfs(start_points):
    que = deque(start_points)
    step = 0
    count_flag = False
    while len(que):
        for _ in range(len(que)):
            y,x = que.popleft()
            for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
                ny = y + dy
                nx = x + dx
                if not (0<=ny<h and 0<=nx<w) or m[ny][nx] != '.':
                    continue
                m[ny][nx] = '#'
                count_flag = True
                que.append((ny,nx))

        if count_flag:
            step += 1
            count_flag = False
        else:
            break
    return step

print(bfs(start_points))

Submission status: Accepted

Solution code:
from collections import deque

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

from collections import deque

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

def bfs(q, a):
  
    ret = deque([])
    while(q):
        pop = q.popleft()
        x, y = pop[0], pop[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < W and ny >= 0 and ny < H:
                if a[ny][nx] == -1:
                    ret.append([nx, ny])
                    a[ny][nx] = 0
    return ret, a
  
q = deque([])

a = [[0 for _ in range(W)] for _ in range(H)]
for i in range(W):
    for j in range(H):
        if A[j][i] == ".":
            a[j][i] = -1  

ans = 0
for i in range(W):
    for j in range(H):
        if a[j][i] == 0:
            q.append([i, j])

ans = -1
while q:
    ans += 1
    q, a = bfs(q, a)
            
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int, input().split())
A = [input() for _ in range(H)]

inf = 10**6
d = [[inf]*W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            q.append((i, j, 0))
            d[i][j] = 0
            
while q:
    temp = q.popleft()
    x = temp[0]
    y = temp[1]
    r = temp[2]
    if x > 0 and d[x-1][y] > r+1:
        d[x-1][y] = r+1
        q.append((x-1, y, r+1))
    if y > 0 and d[x][y-1] > r+1:
        d[x][y-1] = r+1
        q.append((x, y-1, r+1))
    if x < H-1 and d[x+1][y] > r+1:
        d[x+1][y] = r+1
        q.append((x+1, y, r+1))
    if y < W-1 and d[x][y+1] > r+1:
        d[x][y+1] = r+1
        q.append((x, y+1, r+1))

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