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:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    H,W = map(int, input().split())
    grid = [list(input().rstrip()) for _ in range(H)]
    q = []
    visited = [[False]*W for _ in range(H)]
    for y in range(H):
        for x in range(W):
            if grid[y][x] == '#':
                q.append((y,x))
                visited[y][x] = True
    ans = -1
    while q:
        ans += 1
        nq = []
        for y,x in q:
            if 0 < x and not visited[y][x-1]:
                visited[y][x-1] = True
                nq.append((y,x-1))
            if x < W-1 and not visited[y][x+1]:
                visited[y][x+1] = True
                nq.append((y,x+1))
            if 0 < y and not visited[y-1][x]:
                visited[y-1][x] = True
                nq.append((y-1, x))
            if y < H-1 and not visited[y+1][x]:
                visited[y+1][x] = True
                nq.append((y+1,x))
        if nq:
            q = nq[:]
        else:
            break
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
# from bisect import *
# from collections import *
# from copy import deepcopy
# from heapq import *
# from itertools import *
# from math import *
# from operator import *
# from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    H,W = map(int, input().split())
    grid = [list(input().rstrip()) for _ in range(H)]
    q = []
    visited = [[False]*W for _ in range(H)]
    for y in range(H):
        for x in range(W):
            if grid[y][x] == '#':
                q.append((y,x))
                visited[y][x] = True
    ans = -1
    while q:
        ans += 1
        nq = []
        for y,x in q:
            if 0 < x and not visited[y][x-1]:
                visited[y][x-1] = True
                nq.append((y,x-1))
            if x < W-1 and not visited[y][x+1]:
                visited[y][x+1] = True
                nq.append((y,x+1))
            if 0 < y and not visited[y-1][x]:
                visited[y-1][x] = True
                nq.append((y-1, x))
            if y < H-1 and not visited[y+1][x]:
                visited[y+1][x] = True
                nq.append((y+1,x))
        if nq:
            q = nq[:]
        else:
            break
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    H, W = map(int,input().split())
    visited = [[False]*W for _ in range(H)]
    q = []
    for y in range(H):
        S = input().rstrip()
        for x, s in enumerate(S):
            if s == "#":
                q.append((y, x))
                visited[y][x] = True

    ans = -1
    while q:
        ans += 1
        nq = []
        for y, x in q:
            if 0 < x and not visited[y][x-1]:
                visited[y][x-1] = True
                nq.append((y,x-1))
            if x < W-1 and not visited[y][x+1]:
                visited[y][x+1] = True
                nq.append((y,x+1))
            if 0 < y and not visited[y-1][x]:
                visited[y-1][x] = True
                nq.append((y-1, x))
            if y < H-1 and not visited[y+1][x]:
                visited[y+1][x] = True
                nq.append((y+1,x))
        if nq:
            q = nq
        else:
            break

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    H, W = map(int,input().split())
    visited = [[False]*W for _ in range(H)]
    q = []
    for y in range(H):
        S = input()
        for x, s in enumerate(S):
            if s == "#":
                q.append((y, x))
                visited[y][x] = True

    ans = -1
    while q:
        ans += 1
        nq = []
        for y, x in q:
            if 0 < x and not visited[y][x-1]:
                visited[y][x-1] = True
                nq.append((y,x-1))
            if x < W-1 and not visited[y][x+1]:
                visited[y][x+1] = True
                nq.append((y,x+1))
            if 0 < y and not visited[y-1][x]:
                visited[y-1][x] = True
                nq.append((y-1, x))
            if y < H-1 and not visited[y+1][x]:
                visited[y+1][x] = True
                nq.append((y+1,x))
        if nq:
            q = nq
        else:
            break

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from pprint import pprint

from collections import deque

h, w = map(int, sys.stdin.readline().strip().split(" "))
field = []
for _ in range(h):
    field.append(list(sys.stdin.readline().strip()))

# pprint(field)

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

while q:
    count, y, x = q.popleft()
    for dy, dx in ((-1, 0), (1, 0), (0, 1), (0, -1)):
        if 0 <= y+dy < h and 0 <= x+dx < w:
            # print(y+dy, x+dx, field[y+dy][x+dx])
            if field[y+dy][x+dx] == "#":
                continue
            else:
                field[y+dy][x+dx] = "#"
                q.append((count+1, y+dy, x+dx))

# pprint(field)
print(count)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    H,W = map(int, input().split())

    A = [[a for a in input()] for _ in range(H)]
    #stack = deque([(i, j) for i in range(H) for j in range(W) if A[i][j]=="#"])
    stack = [(i, j) for i in range(H) for j in range(W) if A[i][j]=="#"]
    ans = 0
    flag = False
    if stack:
        flag = True
    while flag:
        ans += 1
        flag = False
        #new_stack = deque()
        new_stack = []
        for a,b in stack:
        #while stack:
            #a,b = stack.pop() # 取り出す
            # A[a][b]の隣接マスについて調べる
             # 上
            if a != 0 and A[a-1][b] == ".": # 白の場合
                    A[a-1][b] = "#"
                    new_stack.append((a-1,b))
             # 下
            if a != H-1 and A[a+1][b] == ".": # 白の場合
                    A[a+1][b] = "#"
                    new_stack.append((a+1,b))
            # 左
            if b != 0 and A[a][b-1] == ".": # 白の場合
                    A[a][b-1] = "#"
                    new_stack.append((a,b-1))
            # 右
            if b != W-1 and A[a][b+1] == ".": # 白の場合
                    A[a][b+1] = "#"
                    new_stack.append((a,b+1))
        stack = new_stack
        if stack:
            flag = True
        else:
            ans -= 1 

    print(ans)
            


if __name__ == "__main__":
    main()

Submission status: Accepted

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

    A = [[False for _ in range(W)] for _ in range(H)]

    Q = []
    for y in range(H):
        S = input()
        for x, s in enumerate(S):
            if s == "#":
                Q.append((y, x))
                A[y][x] = True

    ans = 0
    while Q:
        ans += 1
        NQ = []
        for y, x in Q:
            if x > 0 and A[y][x-1] == False:
                A[y][x-1] = True
                NQ.append((y,x-1))
            if x < W-1 and A[y][x+1] == False:
                A[y][x+1] = True
                NQ.append((y,x+1))
            if y > 0 and A[y-1][x] == False:
                A[y-1][x] = True
                NQ.append((y-1, x))
            if y < H-1 and A[y+1][x] == False:
                A[y+1][x] = True
                NQ.append((y+1,x))
        if NQ:
            Q = NQ
        else:
            break

    print(ans-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

B = int(1E8)

def main():

    H, W = map(int, input().split())
    
    l = 0
    q = []
    checked = []
    for h in range(H):
        S = input()
        L = []
        for w in range(W):
            if S[w] == '#':
                l += 1
                L.append(True)
                q.append(B*h+w)
            else:
                L.append(False)
        checked.append(L)

    Next = [[[] for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if h != 0:
                Next[h][w].append(B*(h-1) + w)
            if h != H-1:
                Next[h][w].append(B*(h+1) + w)
            if w != 0:
                Next[h][w].append(B*h + w-1)
            if w != W-1:
                Next[h][w].append(B*h + w+1)

    c = -1
    for _ in range(H+W+2):
        qq = []
        if len(q) == 0:
            break
        for hw in q:
            h, w = hw//B, hw%B
            for nhw in Next[h][w]:
                nh, nw = nhw//B, nhw%B
                if not checked[nh][nw]:
                    qq.append(B*nh + nw)
                    checked[nh][nw] = True
        q = qq
        c += 1

    print(c)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import copy
import  math
import bisect
from collections import *
from operator import itemgetter
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

h, w = na()
maze = [list(input()) for _ in range(h)]
que = deque()
d = [[-1] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            d[i][j] = 0
            que.append((i, j))
l = 0

while que:
    x, y = que.popleft()
    l = d[x][y]
    for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        nx = x + dx
        ny = y + dy
        if not 0 <= nx < h or not 0 <= ny < w or d[nx][ny] != -1:
            continue
        d[nx][ny] = l + 1
        que.append((nx, ny))
print(l)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
cnt = [[float('inf') for _ in range(w)] for _ in range(h)]
ans = 0
searched = [[0 for _ in range(w)] for _ in range(h)]
q = deque([])

def bfs():
  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      next_y = y + dy
      next_x = x + dx 
      if 0 <= next_y < h and 0 <= next_x < w and searched[next_y][next_x] == 0 and a[next_y][next_x] == '.' and cnt[next_y][next_x] > cnt[y][x]+1:
        searched[next_y][next_x] = 1
        q.append([next_y, next_x])
        cnt[next_y][next_x] = cnt[y][x]+1

for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      cnt[i][j] = 0
      searched[i][j] = 1
      q.append([i, j])

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

print(ans)

Submission status: Accepted

Solution code:
import collections
def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(input())
    cur = []
    visited = collections.defaultdict(dict)
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                cur.append([i, j])
                visited[i][j] = 1
            else:
                visited[i][j] = 0
    mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    count = 0
    while cur:
        temp = []
        for i, j in cur:
            for di, dj in mv:
                i1, j1 = i+di, j+dj
                if 0 <= i1 < H and 0 <= j1 < W and not visited[i1][j1]:
                    visited[i1][j1] = True
                    temp.append([i1, j1])
        if len(temp) > 0:
            count += 1
        cur = temp
    return count

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect


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

    checked = [[False] * W for _ in range(H)]
    ans = 0

    que = []
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#' and not checked[h][w]:
                que.append((h, w))
                checked[h][w] = True
    while que:
        next_que = []
        while que:
            h, w = que.pop()
            dx4 = [0, 0, 1, -1]
            dy4 = [1, -1, 0, 0]

            for dx, dy in zip(dx4, dy4):
                next_h = h + dy
                next_w = w + dx
                if 0 <= next_h < H and 0 <= next_w < W and A[next_h][next_w] == '.' and not checked[next_h][next_w]:
                    A[next_h][next_w] = '#'
                    checked[h][w] = True
                    next_que.append((next_h, next_w))
        que = next_que
        if que:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
a=[input() for _ in range(h)]
dxy=[(0,1),(1,0),(-1,0),(0,-1)]
inf=float("inf")

dp=[[inf]*w for _ in range(h)]
q=deque()

for y,l in enumerate(a):
    for x,c in enumerate(l):
        if c=="#":
            dp[y][x]=0
            q.append((x,y))
ans=0
while q:
    x,y=q.popleft()
    d=dp[y][x]
    for dx,dy in dxy:
        nx,ny=x+dx,y+dy
        if not 0<=nx<w: continue
        if not 0<=ny<h: continue
        if dp[ny][nx]<=d+1: continue
        dp[ny][nx]=d+1
        q.append((nx,ny))
        ans=max(ans,d+1)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque
import copy

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


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

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

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

    print(count - 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

Map = [[] for _ in range(H)]
reached = [[False] * W for _ in range(H)]
q = deque()
cnt = 0
count = 0
tempList = []
for y in range(H):
    for i, x in enumerate(input()):
        Map[y].append(x)
        if x == "#":
            cnt += 1
            reached[y][i] = True
            if i + 1 < W and not reached[y][i + 1]:
                reached[y][i + 1] = True
                tempList.append((i + 1, y))

            if i > 0 and not reached[y][i - 1]:
                reached[y][i - 1] = True
                tempList.append((i - 1, y))

            if y + 1 < H and not reached[y + 1][i]:
                reached[y + 1][i] = True
                tempList.append((i, y + 1))

            if y > 0 and not reached[y - 1][i]:
                reached[y - 1][i] = True
                tempList.append((i, y - 1))
if cnt==H*W:
    print(0)
    exit()

q.append(tempList)


def BFS(blist):
    global count
    tList = []

    count += 1

    for (x, y) in blist:
        if x+1<W and not reached[y][x + 1]:
            reached[y][x + 1] = True
            tList.append((x + 1, y))

        if x-1>=0 and not reached[y][x - 1]:
            reached[y][x - 1] = True
            tList.append((x - 1, y))

        if y+1<H and not reached[y + 1][x]:
            reached[y + 1][x] = True
            tList.append((x, y + 1))

        if y-1>=0 and not reached[y - 1][x]:
            reached[y - 1][x] = True
            tList.append((x, y - 1))

    if tList:
        q.append(tList)


while q:
    BFS(q.popleft())

print(count)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from scipy.ndimage.morphology import distance_transform_cdt
INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())
sys.setrecursionlimit(10 ** 9)


def main():
    H, W = MAP()
    A = [INPUT() for _ in range(H)]
    A = np.array([[(Ai[j] != "#") for j in range(W)] for Ai in A])
    print(distance_transform_cdt(A, metric="taxicab").max())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import copy

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


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

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

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

    print(count - 1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
   

H, W = LI()
A = []
for _ in range(H):
    A.append(S())
seen = [[0 for _ in range(W)] for __ in range(H)]

def main():
    q = deque()
    ans = 0
    for i, cc in enumerate(A):
        for j, c in enumerate(cc):
            if c == '#':
                q.append((i, j, 0))
                seen[i][j] = 1
    while q:
        cur_row, cur_col, num = q.popleft()
        for dr, dc in zip(DR, DC):
            n_row = cur_row + dr
            n_col = cur_col + dc
            if not (0 <= n_row < H and 0 <= n_col < W):
                continue
            if seen[n_row][n_col]:
                continue
            if A[n_row][n_col] == '#':
                continue
            q.append((n_row, n_col, num + 1))
            seen[n_row][n_col] = 1
            ans = max(ans, num + 1)
    print(ans)

main()

Submission status: Accepted

Solution code:
from collections import deque

H, W = list(map(int, input().split()))
field = [[i=='#' for i in input()] for _ in range(H)]
count = 0

def bfs():
  global count
  q = deque()
  for y in range(H):
    for x in range(W):
      if field[y][x]:
        q.append((y, x))
  while True:
    nq = deque()
    while len(q) > 0:
      y, x = q.popleft()
      for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
          continue
        if field[ny][nx]:
          continue
        field[ny][nx] = True
        nq.append((ny, nx))
    if len(nq) > 0:
      q = nq
    else:
      break
    count += 1
      
bfs()
print(count)

Submission status: Accepted

Solution code:
from collections import deque
import copy

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

Submission status: Accepted

Solution code:
from collections import deque
import copy

def main():
  H, W = map(int, input().split())
  maps = [[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 maps[i][j]])
  count = 0
  while True:
    nq = deque()
    while q:
      x, y = q.popleft()
      if x > 0 and not maps[x-1][y]:
        maps[x-1][y] = True
        nq.append((x-1,y))
      if y > 0 and not maps[x][y-1]:
        maps[x][y-1] = True
        nq.append((x,y-1))
      if x < H-1 and not maps[x+1][y]:
        maps[x+1][y] = True
        nq.append((x+1,y))
      if y < W-1 and not maps[x][y+1]:
        maps[x][y+1] = True
        nq.append((x,y+1))
    if nq:
      q = copy.copy(nq)
    else:
        break
    count += 1
  print(count)

if __name__ == "__main__":
  main()

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:
from scipy.ndimage import distance_transform_cdt
h,w = map(int, input().split())
grid = [[i=="." for i in input()] for _ in range(h)]
print(distance_transform_cdt(grid, metric='taxicab').max())

# reference : https://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.ndimage.morphology.distance_transform_bf.html

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
grid = [list(input()) for _ in range(h)]
nxt = deque()
for i in range(h):
		for j in range(w):
			if grid[i][j] == "#":
				nxt.append((i,j,0))
a=0
while nxt:
	i,j,t = nxt.popleft()
	if t > a:
		a+=1
	for i,j in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
		if (-1<i<h)&(-1<j<w) and grid[i][j] == ".":
				grid[i][j] = "#"
				nxt.append((i,j,t+1))
print(a)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import numpy as np
# from time import perf_counter


def main():
    h, w = map(int, input().split())
    max_value = h + w
    gridmap = []

    for y in range(h):
        gridmap.append([0 if v == '#' else max_value for v in input().strip()])

    values = np.array(gridmap)

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

    for x in range(w - 1, 0, -1):
        values[:, x - 1] = np.minimum(values[:, x] + 1, values[:, x - 1])

    for y in range(h - 1):
        values[y + 1, :] = np.minimum(values[y, :] + 1, values[y + 1, :])

    for y in range(h - 1, 0, -1):
        values[y - 1, :] = np.minimum(values[y, :] + 1, values[y - 1, :])

    print(np.max(values))


if __name__ == '__main__':
    # st = perf_counter()
    main()
    # ed = perf_counter()
    # print(ed - st)

Submission status: Accepted

Solution code:
from collections import deque
 
H, W = map(int, input().split())
A = [input() for i in range(H)]
q = deque()
c = [[-1] * W for i in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            q.append((i, j))
            c[i][j] = 0
D = [[0, 1], [1, 0], [0, -1], [-1, 0]]
while q:
    y, x = q.popleft()
    for dy, dx in D:
        ny, nx = y+dy, x+dx
        if 0 <= ny < H and 0 <= nx < W and c[ny][nx] == -1:
            q.append((ny, nx))
            c[ny][nx] = c[y][x]+1
print(max([max(l) for l in c]))

Submission status: Accepted

Solution code:
import numpy
H,W = map(int,input().split())
a_list = []
INF = 10**10
for i in range(H):
    str = input()
    a_list.append([0 if i == "#" else INF for i in list(str)])

a_list = numpy.array(a_list)
for x in range(W-1):
    a_list[:,x+1] = numpy.minimum(a_list[:,x]+1,a_list[:,x+1])
    a_list[:,-x-2] = numpy.minimum(a_list[:,-x-1]+1,a_list[:,-x-2])

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

print(a_list.max())

Submission status: Accepted

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq

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

dist = [[10000000 for i in range(W)] for j in range(H)]

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


while len(now) > 0:
	loc = now.popleft()
	if loc[0] < H - 1 and dist[loc[0] + 1][loc[1]] > dist[loc[0]][loc[1]] + 1:
		dist[loc[0] + 1][loc[1]] = dist[loc[0]][loc[1]] + 1
		now.append([loc[0] + 1, loc[1]])
	if loc[0] > 0 and dist[loc[0] - 1][loc[1]] > dist[loc[0]][loc[1]] + 1:
		dist[loc[0] - 1][loc[1]] = dist[loc[0]][loc[1]] + 1
		now.append([loc[0] - 1, loc[1]])
	if loc[1] < W - 1 and dist[loc[0]][loc[1] + 1] > dist[loc[0]][loc[1]] + 1:
		dist[loc[0]][loc[1] + 1] = dist[loc[0]][loc[1]] + 1
		now.append([loc[0], loc[1] + 1])
	if loc[1] > 0 and dist[loc[0]][loc[1] - 1] > dist[loc[0]][loc[1]] + 1:
		dist[loc[0]][loc[1] - 1] = dist[loc[0]][loc[1]] + 1
		now.append([loc[0], loc[1] - 1])

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

Submission status: Accepted

Solution code:
from collections import deque
import sys
def main():
    H,W = list(map(int,sys.stdin.readline().split()))
    place_h = [0,-1,0,1]
    place_w = [1,0,-1,0]
    black = 0
    q = deque([])
    dist = []
    A = []
    for i in range(H):
        a = sys.stdin.readline().split()
        a = list(a[0])
        dist_sub = []
        for j in range(W):
            if a[j] == "#":
                black += 1
                q.append([i,j])
                dist_sub.append(0)
            else:
                dist_sub.append(-1)
        A.append(a)
        dist.append(dist_sub)

    ans = 0
    
    while len(q) > 0:
        vh,vw = q.popleft()
        for m in range(4):
            nvh = vh+place_h[m]
            nvw = vw+place_w[m]
            if 0<=nvh<H and 0<=nvw<W and dist[nvh][nvw] == -1:
                q.append([nvh,nvw])
                dist[nvh][nvw] = dist[vh][vw]+1
                if ans < dist[nvh][nvw]:
                    ans = dist[nvh][nvw]

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np

H, W = map(int, input().split())
A = [[] for _ in range(H)]
inf = 10 ** 7
for i in range(H):
    A[i] = list(input())
    for j in range(W):
        if A[i][j] == '.':
            A[i][j] = inf
        elif A[i][j] == '#':
            A[i][j] = 0

A = np.array(A)

#print(A)

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

#print(A)
for j in range(W-2, -1, -1):
    A[:,j] = np.minimum(A[:,j+1]+1, A[:,j])

#print(A)

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

#print(A)

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

#print(A)


ans = np.max(A)

#for i in range(H):
#    ans_list.append(max(A[i]))

print(ans)

Submission status: Accepted

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

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

q=deque()

res = 0
while len(next_q) != 0:
    q=copy.copy(next_q)
    next_q.clear()
    while q:
        y, x = q.popleft()
        if y > 0 and L[y - 1][x] == 0:
            L[y - 1][x] = 1
            next_q.append((y - 1, x))
        if y < H - 1 and L[y + 1][x] == 0:
            L[y + 1][x] = 1
            next_q.append((y + 1, x))
        if x > 0 and L[y][x - 1] == 0:
            L[y][x - 1] = 1
            next_q.append((y, x - 1))
        if x < W - 1 and L[y][x + 1] == 0:
            L[y][x + 1] = 1
            next_q.append((y, x + 1))
    if len(next_q)==0: break
    res += 1
print(res)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
Q = deque()
INF = H+W+1
C = [[-1]*W for i in range(H)]
for y in range(H):
  for x in range(W):
    if A[y][x] == "#":
      Q.append((y,x))
      C[y][x] = 0
X = [1,0,-1,0]
Y = [0,-1,0,1]
      
while Q:
  y,x = Q.popleft()
  for i in range(4):
    ny = y + Y[i]
    nx = x + X[i]
    if 0<=ny<H and 0<=nx<W and C[ny][nx]==-1 and A[ny][nx] == ".":
      C[ny][nx] = C[y][x] + 1
      Q.append((ny,nx))
ans = 0
for i in range(H):
  ans = max(ans,max(C[i]))
print(ans)