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:
def main():
  from collections import deque
  s,*c=open(0)
  h,w=map(int,s.split())
  f=[-1]*h*w
  q=deque()
  a,p=q.append,q.popleft
  for i,c in enumerate(''.join(t[:w]for t in c)):
    if c=='#':
      a(i)
      f[i]=0
  while q:
    i=p()
    v=f[i]+1
    j,k,l,m,u=i+w,i-w,i+1,i-1,i%w
    if h*w>j and f[j]<0:
      a(j)
      f[j]=v
    if k>=0 and f[k]<0:
      a(k)
      f[k]=v
    if w>u+1and f[l]<0:
      a(l)
      f[l]=v
    if u and f[m]<0:
      a(m)
      f[m]=v
  print(v-1)
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
def main():
  from collections import deque
  s,*c=open(0)
  h,w=map(int,s.split())
  f=[-1]*h*w
  q=deque()
  for i,c in enumerate(''.join(t[:w]for t in c)):
    if c=='#':
      q.append(i)
      f[i]=0
  while q:
    i=q.popleft()
    v=f[i]+1
    j,k,l,m,u=i+w,i-w,i+1,i-1,i%w
    if h*w>j and f[j]<0:
      q.append(j)
      f[j]=v
    if k>=0 and f[k]<0:
      q.append(k)
      f[k]=v
    if w>u+1and f[l]<0:
      q.append(l)
      f[l]=v
    if u and f[m]<0:
      q.append(m)
      f[m]=v
  print(v-1)
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
from collections import*
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
grid=[["#"]*(w+2)]+[list("#"+input()+"#")for x in range(h)]+[["#"]*(w+2)]

stack=deque([])
for y in range(1,h+1):
    for x in range(1,w+1):
        if grid[y][x]=="#":
            grid[y][x]=0
            stack.append((y,x))

for i in range(h*w):
    tmp=deque([])
    while stack:
        my,mx=stack.pop()
        for y,x in ([0,1],[1,0],[-1,0],[0,-1]):
            if grid[my+y][mx+x]==".":
                grid[my+y][mx+x]=i+1
                tmp.append([my+y,mx+x])
    stack=tmp
    if len(tmp)==0:
        print(i)
        break

Submission status: Accepted

Solution code:
# AtCoder Grand Contest 033
# https://atcoder.jp/contests/agc033
import sys
import datetime
today = datetime.datetime.today

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main_ok():
    H, W = i2nn()
    HW = H * W
    A = ii2ss(H)
    A = [[0 if s == '#' else HW for s in line] for line in A]
    for i in range(H):
        for j in range(1, W):
            if A[i][j-1]+1 < A[i][j]:
                A[i][j] = A[i][j-1]+1
        for j in range(W-2, -1, -1):
            if A[i][j+1]+1 < A[i][j]:
                A[i][j] = A[i][j+1]+1
    for j in range(W):
        for i in range(1, H):
            if A[i-1][j]+1 < A[i][j]:
                A[i][j] = A[i-1][j]+1
        for i in range(H-2, -1, -1):
            if A[i+1][j]+1 < A[i][j]:
                A[i][j] = A[i+1][j]+1
    ans = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] > ans:
                ans = A[i][j]
    print(ans)

def main():
    H, W = i2nn()
    A = ii2ss(H)
    A = [[True] * (W + 2)] + [[True] + [s == '#' for s in line] + [True] for line in A] + [[True] * (W + 2)]
    q = []
    for i in range(1, H+1):
        for j in range(1, W+1):
            if A[i][j] == True:
                q.append((i, j))
    rec = 0
    while len(q) > 0:
        q2 = []
        for i0, j0 in q:
            i, j = i0 - 1, j0
            if A[i][j] != True:
                A[i][j] = True
                q2.append((i, j))
            i, j = i0 + 1, j0
            if A[i][j] != True:
                A[i][j] = True
                q2.append((i, j))
            i, j = i0, j0 - 1
            if A[i][j] != True:
                A[i][j] = True
                q2.append((i, j))
            i, j = i0, j0 + 1
            if A[i][j] != True:
                A[i][j] = True
                q2.append((i, j))
        rec += 1
        q = q2
    print(rec - 1)

main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

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

counts = np.zeros((H, W))
counts[A == '.'] = np.inf

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

print(int(np.max(counts)))

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 functools as ft

h,w = map(int, input().split())
mat = [[True] * (w+2)]
for _ in range(h):
    mat.append([True] + [a == '#' for a in input()] + [True])
mat.append([True]*(w+2))

prev = []
for i in range(1,h+1):
    for j in range(1,w+1):
        if mat[i][j]:
            prev.append((i,j))



round = -1
while prev:
    round += 1
    #print(prev)
    #print(mat)
    def calc(next, tup):
        x = tup[0]
        y = tup[1]
        if not mat[x-1][y]:
            next.append((x-1,y))
            mat[x-1][y] = True
        if not mat[x][y-1]:
            next.append((x,y-1))
            mat[x][y-1] = True
        if not mat[x+1][y]:
            next.append((x+1,y))
            mat[x+1][y] = True
        if not mat[x][y+1]:
            next.append((x,y+1))
            mat[x][y+1] = True
        return next
    next = ft.reduce(calc, prev, [])

    prev = next

print(round)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
INF=10**9
check=[]
for i in range(h):
    sub_list=[]
    for j in range(w):
        sub_list.append(INF)
    check.append(sub_list)
black=deque([])
for i in range(h):
    sub_list=list(input())
    for j in range(w):
        if sub_list[j]=='#':
            black.append((i,j))
            check[i][j]=0
Max=0
while len(black)>0:
    now=black.popleft()
    U=(now[0]-1,now[1])
    D=(now[0]+1,now[1])
    L=(now[0],now[1]-1)
    R=(now[0],now[1]+1)
    for i in U,D,L,R:
        if 0<=i[0]<=h-1 and 0<=i[1]<=w-1 and check[i[0]][i[1]]==INF:
            check[i[0]][i[1]]=check[now[0]][now[1]]+1
            Max=max(Max,check[i[0]][i[1]])
            black.append(i)
print(Max)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int ,input().split())
A = [input() for _ in range(H)]
dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
inf = float("inf")

dp = [[inf]*W for _ in range(H)]
q = deque()
for y, row in enumerate(A):
    for x, c in enumerate(row):
        if c == "#":
            dp[y][x] = 0
            q.append((x, y))

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) or (not 0 <= ny < H):
            continue
        if dp[ny][nx] <= d+1:
            continue
        dp[ny][nx] = d+1
        q.append((nx, ny))

print(max(max(row) for row in dp))

Submission status: Accepted

Solution code:
import numpy as np

H,W=map(int,input().split(' '))
# 回数の最大値はH+W
max_value = H+W
values =[]

# マス目に回数を入れる。黒なら0、白なら最大値を入れておく
for i in range(H):
    values.append([0 if i == '#' else max_value for i in list(input())])
# numpy配列に
values = np.array(values)

# 右のセルと比較して、
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 x in range(H-1):
    values[x+1,:] = np.minimum(values[x,:]+1,values[x+1,:])
for x in range(H-1,0,-1):
    values[x-1,:] = np.minimum(values[x,:]+1,values[x-1,:])
print(np.max(values))

Submission status: Accepted

Solution code:
# 参考: https://atcoder.jp/contests/agc033/submissions/5279051
def a_darker_and_darker(H, W, Grid):
    from scipy.ndimage import distance_transform_cdt
    # 2次元リストの各位置に対して、Falseとみなされる要素がある位置から
    # 最短の距離が格納された2次元リストを返す
    # 距離の測り方は、metricが'taxicab'だとマンハッタン距離に、
    # 'chessboard'だとチェビシェフ距離に基づく

    grid = [[1 if c == '.' else 0 for c in row] for row in Grid]
    return distance_transform_cdt(grid, metric='taxicab').max()

H, W = [int(i) for i in input().split()]
Grid = [input() for _ in range(H)]
print(a_darker_and_darker(H, W, Grid))

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
g = [[True]*(w+2)]
for i in range(h):
    g.append([True] + [a == '#' for a in input()] + [True])
g.append([True]*(w+2))

bp = []
for i in range(1, h+1):
    for j in range(1, w+1):
        if g[i][j]:
            bp.append((i, j))

cnt = 0
while bp:
    p = []
    for i, j in bp:
        if not g[i+1][j]:
            g[i+1][j] = True
            p.append((i+1, j))
        if not g[i-1][j]:
            g[i-1][j] = True
            p.append((i-1, j))       
        if not g[i][j+1]:
            g[i][j+1] = True
            p.append((i, j+1))
        if not g[i][j-1]:
            g[i][j-1] = True
            p.append((i, j-1))
    cnt += 1
    bp = p
print(cnt-1)

Submission status: Accepted

Solution code:
from scipy.ndimage import distance_transform_cdt

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
n = [[1 if x == "." else 0 for x in row] for row in a]

cnt = distance_transform_cdt(n, metric='taxicab')
print(cnt.max())

Submission status: Accepted

Solution code:
import numpy as np

H, W = map(int, input().split())
max_value = H + W #左上から右下までの最大手数
matrix = []

#黒の場合0, それ以外の場合、max_valueを代入したリストを作成-->arrayへ変換
for _ in range(H):
    matrix.append([0 if i == '#' else max_value for i in list(input())])
matrix = np.array(matrix)

for c in range(W-1):#y座標を増やしていく
    matrix[:,c+1] = np.minimum(matrix[:,c]+1, matrix[:,c+1]) #一個左+1　と　自分自身の値　の小さい方
#print (matrix)
for c in range(W-1,0,-1):
    matrix[:,c-1] = np.minimum(matrix[:,c]+1, matrix[:,c-1]) #一個右+1　と　自分自身の値　の小さい方
#print (matrix)
for c in range(H-1):
    matrix[c+1,:] = np.minimum(matrix[c,:]+1, matrix[c+1,:]) #一個下+1　と　自分自身の値　の小さい方　
#print (matrix)
for c in range(H-1,0,-1):
    matrix[c-1,:] = np.minimum(matrix[c,:]+1, matrix[c-1,:]) #一個上+1　と　自分自身の値　の小さい方
#print (matrix)
print (np.max(matrix))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')
xy = [(0, 1), (0, -1), (1, 0), (-1, 0)]


#A
def A():
    h, w = LI()
    A = SR(h)
    check = [[True for _ in range(w)] for i in range(h)]
    q = deque([])
    for tate in range(h):
        for yoko in range(w):
            if A[tate][yoko] == "#":
                q.append((tate, yoko))
                check[tate][yoko] = False
    new_q = deque([])
    ans = 0
    while True:
        while q:
            y, x = q.pop()
            for movex, movey in xy:
                if 0 <= y + movey < h and 0 <= x + movex < w and check[y + movey][x + movex]:
                    check[y + movey][x + movex] = False
                    new_q.append((y + movey, x + movex))
        if not new_q:
            break
        ans += 1
        q = new_q
        new_q = deque([])
    print(ans)
                    

        
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    A()

Submission status: Accepted

Solution code:
from collections import deque
inf = float('inf')
around = [[0,1],[1,0],[0,-1],[-1,0]]

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

dq = deque()

for i,line in enumerate(A):
    for j,e in enumerate(line):
        if e == "#":
            dq.append([i,j,0])

def bfs():
    res = 0
    while dq:
        i,j,d = dq.popleft()
        d += 1
        for di,dj in around:
            ni = i + di; nj = j + dj
            if not(0 <= ni <= H-1 and 0 <= nj <= W-1):
                continue
            if A[ni][nj] == ".":
                A[ni][nj] = "#"
                dq.append([ni,nj,d])
                if d > res:
                    res = d
    return res

ans = bfs()
print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
a = [['#'] * (w + 2)] * 2
a[1: 1] = (['#'] + list(input()) + ['#'] for _ in range(h))
d = (-1, 0), (1, 0), (0, -1), (0, 1)

step = [(i, j) for i in range(1, h + 1) for j in range(1, w + 1)
       if a[i][j] == '#']

def next_step():
    r = []
    for i, j in step:
        for di, dj in d:
            di += i
            dj += j
            if a[di][dj] == '.':
                a[di][dj] = '#'
                r.append((di, dj))
    return r

n = h * w - len(step)
r = 0
while n:
    r += 1
    step = next_step()
    n -= len(step)
print(r)

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = deque(maxlen=W*H)
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat.append((h, w, 0))
    dp[h] = s

while len(mat):
    h, w, cnt = mat.popleft()

    for t, h, w, cnt in ((h > 0, h - 1, w, cnt),(h < H-1, h + 1, w, cnt),(w > 0, h , w - 1, cnt),(w < W-1, h , w + 1, cnt)):
        if t and dp[h][w] == ".":
            mat.append((h, w, cnt+1))
            dp[h][w] = "#"

print(cnt)

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = deque()
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat.append((h, w, 0))
    dp[h] = s

while len(mat):
    h, w, cnt = mat.popleft()

    for t, h, w, cnt in [(h > 0, h - 1, w, cnt),(h < H-1, h + 1, w, cnt),(w > 0, h , w - 1, cnt),(w < W-1, h , w + 1, cnt)]:
        if t and dp[h][w] == ".":
            mat.append((h, w, cnt+1))
            dp[h][w] = "#"

print(cnt)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
a_array = [input() for x in range(h)]
black = [[False for x in range(w)] for y in range(h)]
next = set()
for row in range(h):
    for column in range(w):
        if a_array[row][column] == "#":
            black[row][column] = True
            next.add((row, column))

move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
cnt = 0
while next:
    tmp = set()
    # print(next)
    cnt += 1
    for row, column in next:
        for i, j in move:
            if not (0 <= row + i < h and 0 <= column + j < w) or black[row+i][column+j]:
                continue
            black[row+i][column+j] = True
            tmp.add((row + i, column + j))
    next = tmp
print(cnt-1)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
d = (-1, 0), (1, 0), (0, -1), (0, 1)

step = [(i, j) for i in range(h) for j in range(w) if a[i][j] == '#']

def next_step():
    r = []
    for i, j in step:
        for di, dj in d:
            di += i
            dj += j
            if 0 <= di < h and 0 <= dj < w and a[di][dj] == '.':
                a[di][dj] = '#'
                r.append((di, dj))
    return r

n = h * w - len(step)
r = 0
while n:
    r += 1
    step = next_step()
    n -= len(step)
print(r)

Submission status: Accepted

Solution code:
def a_darker_and_darker(H, W, Grid):
    def is_in_field(row, col):
        return (0 <= row < H) and (0 <= col < W)

    grid, q = [[None] * W for _ in range(H)], []
    # 黒マスがどこにあるかを調べる。ついでにgridを初期化
    for row in range(H):
        for col in range(W):
            if Grid[row][col] == '#':
                grid[row][col] = True
                q.append((row, col))
            else:
                grid[row][col] = False

    # '#'があるマスから上下左右に移動することを繰り返して任意のマスに到達する。
    # 何回繰り返せばすべてのマスに到達できるか？
    directions = ((-1, 0), (0, 1), (1, 0), (0, -1))  # 上右下左の隣接マスを指定
    ans = 0
    while q:
        tmp = []
        for row, col in q:
            for dr, dc in directions:
                nr, nc = row + dr, col + dc
                if is_in_field(nr, nc) and (not grid[nr][nc]):
                    grid[nr][nc] = True
                    tmp.append((nr, nc))
        ans += (1 if tmp else 0)
        q = tmp
    return ans

H, W = [int(i) for i in input().split()]
Grid = [input() for _ in range(H)]
print(a_darker_and_darker(H, W, Grid))

Submission status: Accepted

Solution code:
h,w=map(int, input().split())
a=[input() for i in range(h)]

from collections import deque
b=[[0]*w for i in range(h)]
q=deque()
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append((i,j))
            b[i][j]=1
ans=-1
while len(q)>0:
    ans+=1
    q2=deque()
    for i,j in q:
        if j>0 and b[i][j-1]==0:
            q2.append((i,j-1))
            b[i][j-1]=1
        if j<w-1 and b[i][j+1]==0:
            q2.append((i,j+1))
            b[i][j+1]=1
        if i>0 and b[i-1][j]==0:
            q2.append((i-1,j))
            b[i-1][j]=1
        if i<h-1 and b[i+1][j]==0:
            q2.append((i+1,j))
            b[i+1][j]=1
    q=q2
print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
d = (-1, 0), (1, 0), (0, -1), (0, 1)
p = [(i, j) for i in range(h) for j in range(w) if a[i][j] == '#']

def f():
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if 0 <= di < h and 0 <= dj < w and a[di][dj] == '.':
                a[di][dj] = '#'
                s.append((di, dj))
    return s

n = h * w - len(p)
r = 0
while n:
    r += 1
    p = f()
    n -= len(p)
print(r)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
d = (-1, 0), (1, 0), (0, -1), (0, 1)
p = [(i, j) for i in range(h) for j in range(w) if a[i][j] == '#']
n = h * w - len(p)
r = 0
while n:
    r += 1
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if 0 <= di < h and 0 <= dj < w and a[di][dj] == '.':
                a[di][dj] = '#'
                s.append((di, dj))
    p = s
    n -= len(p)
print(r)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
d = (-1, 0), (1, 0), (0, -1), (0, 1)
p = [(i, j) for i in range(h) for j in range(w) if a[i][j] == '#']

def f():
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if 0 <= di < h and 0 <= dj < w and a[di][dj] == '.':
                a[di][dj] = '#'
                yield di, dj

n = h * w - len(p)
r = 0
while n:
    r += 1
    p = list(f())
    n -= len(p)
print(r)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
d = (-1, 0), (1, 0), (0, -1), (0, 1)
p = [(i, j) for i in range(h) for j in range(w) if a[i][j] == '#']
n = h * w - len(p)
r = 0
while n:
    r += 1
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if 0 <= di < h and 0 <= dj < w and a[di][dj] == '.':
                a[di][dj] = '#'
                s.append((di, dj))
    p = s
    n -= len(p)
print(r)

Submission status: Accepted

Solution code:
class Queue():
    def __init__(self):
        self.data = []
        self.idx = 0
        self.size = 0

    def get(self):
        self.idx += 1
        self.size -= 1
        return self.data[self.idx-1]

    def put(self, item):
        self.size += 1
        self.data.append(item)

    def qsize(self):
        return self.size

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

# bfs
bfs = [[-1 for j in range(W)] for i in range(H)]
que = Queue()
for i in range(H):
    for j in range(W):
        if(A[i][j] == '#'):
            que.put((i, j))
            bfs[i][j] = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

while(que.qsize()):
    p = que.get()
    for i in range(4):
        if(0 <= p[0]+dx[i] < H and 0 <= p[1]+dy[i] < W):
            if(bfs[p[0]+dx[i]][p[1]+dy[i]] == -1):
                que.put((p[0]+dx[i], p[1]+dy[i]))
                bfs[p[0]+dx[i]][p[1]+dy[i]] = bfs[p[0]][p[1]] + 1

# print ans
print(max([max(l) for l in bfs]))

Submission status: Accepted

Solution code:
from scipy import ndimage
import numpy as np
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
 
A_array = np.array(
    [[0 if s == "#" else 1 for s in input().strip("\n")] for i in range(H)])
# print(A_array)
 
# print(A_array)
b = ndimage.morphology.distance_transform_cdt(
    A_array, metric="taxicab")
print(np.max(b))

Submission status: Accepted

Solution code:
class Queue():
    def __init__(self):
        self.data = []
        self.idx = 0
        self.size = 0

    def get(self):
        self.idx += 1
        self.size -= 1
        return self.data[self.idx-1]

    def put(self, item):
        self.size += 1
        self.data.append(item)

    def qsize(self):
        return self.size

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

# bfs
bfs = [[-1 for j in range(W)] for i in range(H)]
que = Queue()
for i in range(H):
    for j in range(W):
        if(A[i][j] == '#'):
            que.put((i, j))
            bfs[i][j] = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

while(que.qsize()):
    p = que.get()
    for i in range(4):
        if(0 <= p[0]+dx[i] < H and 0 <= p[1]+dy[i] < W):
            if(bfs[p[0]+dx[i]][p[1]+dy[i]] == -1):
                que.put((p[0]+dx[i], p[1]+dy[i]))
                bfs[p[0]+dx[i]][p[1]+dy[i]] = bfs[p[0]][p[1]] + 1

# print ans
print(max([max(l) for l in bfs]))

Submission status: Accepted

Solution code:
from scipy import ndimage
import numpy as np
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
 
A_array = np.array(
    [[0 if s == "#" else 1 for s in input()[:-1]] for i in range(H)])
# print(A_array)
 
 
# print(A_array)
b = ndimage.morphology.distance_transform_cdt(
    A_array, metric="taxicab")
print(np.max(b))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
from collections import deque
from heapq import heappush, heappop
def solve():
    H,W = map(int, input().split())
    A = [ list(input()) for _ in range(H)]
    HMANY = [ [10**9] * W for _ in range(H)]
    
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" :
                HMANY[h][w] = 0
    for w in range(W):
        for h in range(H-1):
            if HMANY[h][w]+1 < HMANY[h+1][w]:
                HMANY[h+1][w] = HMANY[h][w] + 1
        for h in range(H-1, 0, -1):
            if HMANY[h][w]+1 < HMANY[h-1][w]:
                HMANY[h-1][w] = HMANY[h][w] + 1
    
    for h in range(H):
        for w in range(W-1):
            if HMANY[h][w]+1 < HMANY[h][w+1]:
                HMANY[h][w+1] = HMANY[h][w] + 1
        for w in range(W-1, 0, -1):
            if HMANY[h][w]+1 < HMANY[h][w-1]:
                HMANY[h][w-1] = HMANY[h][w] + 1        

    ans = 0
    for h in range(H):
        ans = max(ans, max(HMANY[h]))
    # print(ans-1)
    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
from collections import deque
from heapq import heappush, heappop
def solve():
    H,W = map(int, input().split())
    A = [ list(input()) for _ in range(H)]
    HMANY = [ [10**9] * W for _ in range(H)]

    
    
    # q = deque()
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" :
                HMANY[h][w] = 0
    for w in range(W):
        for h in range(H-1):
            if HMANY[h][w]+1 < HMANY[h+1][w]:
                HMANY[h+1][w] = HMANY[h][w] + 1
        for h in range(H-1, 0, -1):
            if HMANY[h][w]+1 < HMANY[h-1][w]:
                HMANY[h-1][w] = HMANY[h][w] + 1
    
    for h in range(H):
        for w in range(W-1):
            if HMANY[h][w]+1 < HMANY[h][w+1]:
                HMANY[h][w+1] = HMANY[h][w] + 1
        for w in range(W-1, 0, -1):
            if HMANY[h][w]+1 < HMANY[h][w-1]:
                HMANY[h][w-1] = HMANY[h][w] + 1        
    #             q.append((h,w))
    #             A[h][w] = "."
    # ans = 0
    # while q:
    #     nextQ = deque()
    #     for h,w in q:
    #         A[h][w] = "#"
    #         if h+1 <H and A[h+1][w] == ".":
    #             nextQ.append( (h+1,w))
    #         if w+1 <W and A[h][w+1] == ".":
    #             nextQ.append((h,w+1))
    #         if 0<=h-1 and A[h-1][w] == ".":
    #             nextQ.append((h-1,w))
    #         if 0<=w-1 and A[h][w-1] == ".":
    #             nextQ.append((h,w-1))        
    #     ans += 1
    #     q = nextQ
        # num,h,w = q.popleft()        
        # if HMANY[h][w] > num and A[h][w] == ".":
        #     HMANY[h][w] = num
        #     A[h][w] = "#"
        #     if h+1 <H and A[h+1][w] == ".":
        #         q.append( (num+1,h+1,w))
        #     if w+1 <W and A[h][w+1] == ".":
        #         q.append((num+1,h,w+1))
        #     if 0<=h-1 and A[h-1][w] == ".":
        #         q.append((num+1,h-1,w))
        #     if 0<=w-1 and A[h][w-1] == ".":
        #         q.append((num+1,h,w-1))

    ans = 0
    for h in range(H):
        ans = max(ans, max(HMANY[h]))
    # print(ans-1)
    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from scipy import ndimage
import numpy as np

 
H, W = map(int, input().split())
 
A_array = np.array(
    [[0 if s == "#" else 1 for s in input()] for i in range(H)])
# print(A_array)
 
# print(A_array)
b = ndimage.morphology.distance_transform_cdt(
    A_array, metric="taxicab")
print(np.max(b))

Submission status: Accepted

Solution code:
import numpy as np

H,W=map(int,input().split())
max_value = H+W
matrix =[]

for _ in range(H):
    matrix.append([0 if i == '#' else max_value for i in list(input())])
matrix = np.array(matrix)

for c in range(W-1):
    matrix[:,c+1] = np.minimum(matrix[:,c]+1,matrix[:,c+1])
for c in range(W-1,0,-1):
    matrix[:,c-1] = np.minimum(matrix[:,c-1],matrix[:,c]+1)
for r in range(H-1):
    matrix[r+1,:] = np.minimum(matrix[r,:]+1,matrix[r+1,:])
for r in range(H-1,0,-1):
    matrix[r-1,:] = np.minimum(matrix[r,:]+1,matrix[r-1,:])


print(np.max(matrix))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from pprint import pprint
 
def solve(H: int, W: int, A: "List[str]"):
    count = [[H + W] * (W + 2) for _ in range(H + 2)]
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                count[i + 1][j + 1] = 0
            else:
                count[i + 1][j + 1] = min(count[i][j + 1], count[i + 1][j]) + 1
 
    #pprint(count)
    ret = 0
    for i in range(H, 0, -1):
        for j in range(W, 0, -1):
            count[i][j] = min(count[i][j], min(count[i][j + 1], count[i + 1][j]) + 1)
            ret = max(ret, count[i][j])
    #pprint(count)
    print(ret)
    return
 
 
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, A)
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# input
h, w = [int(i) for i in input().split()]
ary = []
for y in range(h):
    ary.append([None if i == '.' else 0 for i in input()])


from collections import deque

update_q = deque((y, x) for y, line in enumerate(ary) for x, elem in enumerate(line) if elem == 0)

def update(ary, update_q):
    for _ in range(len(update_q)):
        pos = update_q.popleft()
        y, x = pos
        if x > 0:
            uy, ux = y, x-1
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_q.append((uy, ux))
        if x < w-1:
            uy, ux = y, x+1
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_q.append((uy, ux))
        if y > 0:
            uy, ux = y-1, x
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_q.append((uy, ux))
        if y < h-1:
            uy, ux = y+1, x
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_q.append((uy, ux))
    return ary, update_q


black_count = len(update_q)
update_count = 0
while black_count < w * h:
    ary, update_q = update(ary, update_q)
    black_count += len(update_q)
    update_count += 1


print(update_count)

Submission status: Accepted

Solution code:
import numpy as np

H,W=map(int,input().split())
max_value = H+W
matrix =[]

for _ in range(H):
    matrix.append([0 if i == '#' else max_value for i in list(input())])
matrix = np.array(matrix)

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