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 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())])
    
# print(values)
# numpy配列に
values = np.array(values)
 
# print(values)
# print()

# numpyで各次元のスライスはカンマで区切って指定する。[行について, 列について]
# 例： 3行、4列でarangeした行列 A について print(A[1:, 1:3]) とすると下記となる。
#  [[ 5  6]
#   [ 9 10]]
#
# (あるセルの値+1) と、(その右側のセルの値) のminを 右側のセルに書く作業を
# 一番左の列から右に向けてやる
for x in range(W-1):
    values[:,x+1] = np.minimum(values[:,x]+1,values[:,x+1])
#    print('case1: x = ', x)
#    print(values)

# print()
# (あるセルの値+1) と、(その左側のセルの値) のminを 左側のセルに書く作業を
# 一番右の列から左に向けてやる
for x in range(W-1,0,-1):
    values[:,x-1] = np.minimum(values[:,x-1],values[:,x]+1)
#    print('case2: x = ', x)
#    print(values)

# print()
# (あるセルの値+1) と、(その下側のセルの値) のminを 下側のセルに書く作業を
# 一番上の行から下に向けてやる
for x in range(H-1):
    values[x+1,:] = np.minimum(values[x,:]+1,values[x+1,:])
#    print('case3: x = ', x)
#    print(values)

# print()
# (あるセルの値+1) と、(その上側のセルの値) のminを 上側のセルに書く作業を
# 一番下の行から上に向けてやる
for x in range(H-1,0,-1):
    values[x-1,:] = np.minimum(values[x,:]+1,values[x-1,:])
#    print('case4: x = ', x)
#    print(values)
    
# print()
print(np.max(values))

Submission status: Accepted

Solution code:
from collections import deque
H, W = [int(n) for n in input().split()]
map = [0 for _ in range(H)]
INF = 10**8
dis = [[INF for _ in range(W)]for __ in range(H)]
Q = deque()
for i in range(H):
    map[i] = list(str(input()))
    for j in range(W):
        if map[i][j] == "#":
            Q.append((i, j))
            dis[i][j] = 0
dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans = 0
while(len(Q) != 0):
    n = Q.pop()
    for d in dxy:
        tx, ty = n[0] + d[0], n[1] + d[1]
        if(0 <= tx <= H - 1 and 0 <= ty <= W - 1 and map[tx][ty] == "."):
            map[tx][ty] = "#"
            Q.appendleft((tx, ty))
            dis[tx][ty] = dis[n[0]][n[1]] + 1
            ans = max(dis[tx][ty], ans)
print(ans)
# for i in range(H):
#     print(dis[i])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
h,w = map(int, input().split())
al = [list(input()) for _ in range(h)]
cnt = 0

q = []
for hi in range(h):
    for wi in range(w):
        if al[hi][wi]=="#":
            q.append((hi,wi))

while len(q)>0:
    nq = []
    cnt += 1
    for hi,wi in q:
        for d in [[1,0],[0,1],[-1,0],[0,-1]]:
            if h>hi+d[0]>=0 and w>wi+d[1]>=0:
                if al[hi+d[0]][wi+d[1]]==".":
                    al[hi+d[0]][wi+d[1]] = "#"
                    nq.append((hi+d[0], wi+d[1]))
    q = nq

print(cnt-1)

Submission status: Accepted

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

a = ''.join(input() + '#' for _ in range(h))
a = a.replace('.', '1').replace('#', '0')

bits = int(a, 2)

w1 = w + 1
h1 = h + 1
bits <<= w1

frame = (1 << w1) - 1
frame |= frame << h1 * w1
frame |= sum(1 << b for b in range(w1, h1 * w1, w1))

count = 0
while bits:
    count += 1
    mask = bits | frame
    #       up             down           left          right
    bits &= (mask << w1) & (mask >> w1) & (mask << 1) & (mask >> 1)
print(count)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[True]*(W+2)]
mark_matrix.extend([[True]+[x!='.' for x in input()] for _ in range(H)])
mark_matrix[H].append(True)
mark_matrix.append([True]*(W+2))

queue = []
for i in range(1,H+1):
  for j in range(1,W+1):
    if mark_matrix[i][j]:
      queue.append((i,j))
 
max_value = 0
while(True):
  if len(queue) == 0:
    break
  
  new_queue = []
  for i,j in queue:
  
    if not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      new_queue.append((i-1,j))
    if not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      new_queue.append((i+1,j))
    if not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      new_queue.append((i,j-1))
    if not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      new_queue.append((i,j+1))
 
  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
print(max_value)

Submission status: Accepted

Solution code:
def f(h, w):
    t = []
    for _ in range(h):
        t += [[0 if c == "#" else 3000 for c in input()]]
    for ti in t:
        for j in range(1, w):
            if ti[j - 1] + 1 < ti[j]:
                ti[j] = ti[j - 1] + 1
        for j in range(w - 2, -1, -1):
            if ti[j + 1] + 1 < ti[j]:
                ti[j] = ti[j + 1] + 1
    for j in range(w):
        for i in range(1, h):
            if t[i - 1][j] + 1 < t[i][j]:
                t[i][j] = t[i - 1][j] + 1
        for i in range(h - 2, -1, -1):
            if t[i + 1][j] + 1 < t[i][j]:
                t[i][j] = t[i + 1][j] + 1

    print(max(max(ti) for ti in t))


h, w = map(int, input().split())
f(h, w)

Submission status: Accepted

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


h, w = map(int, input().split())
f(h, w)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    tosearch = deque()

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

    grid = [[-1 for _ in range(W + 2)]]
    for i in range(H):
        grid.append([-1] + [0 if char == "#" else -2 for char in input()] + [-1])
    grid.append([-1 for _ in range(W + 2)])

    for i, line in enumerate(grid):
        for j, char in enumerate(line):
            if char == 0:
                tosearch.append((i, j))

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

    while tosearch:
        y, x = tosearch.popleft()

        for move in movement:
            ny, nx = y + move[0], x + move[1]

            if grid[ny][nx] == -2:
                grid[ny][nx] = grid[y][x] + 1
                tosearch.append((ny, nx))

    ans = 0
    for line in grid:
        ans = max(ans, max(line))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

h,w=list(map(int,input().split()))
a=[input() for _ in range(h)]
#a[h][w]
direction=[[-1,0],[1,0],[0,-1],[0,1]]
visited=[[-1]*w for _ in range(h)]
q=collections.deque()

#全ての黒マスをキューに入れる
for hi in range(h):
  for wi in range(w):
    if a[hi][wi]=="#":
      q.append([hi,wi])
      visited[hi][wi]=0

while len(q)>0:
  ch,cw=q.popleft()
  for d in direction:
    nh=ch+d[0]
    nw=cw+d[1]
    #端からはみでない、まだ見てない白マス
    if nh>=0 and nw>=0 and nh<h and nw<w and visited[nh][nw]==-1:
      q.append([nh,nw])
      visited[nh][nw]=visited[ch][cw]+1

ans=0
for hi in range(h):
  tmp=max(visited[hi])
  if tmp > ans:
    ans=tmp
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
 
#%% Smart Solution
 
input = sys.stdin.readline
 
H, W = map(int, input().split())
 
status = np.full((H, W), H*W, dtype=int)
for i in range(H):
    for j, c in enumerate(input()):
        if c == "#":
            status[i,j] = 0
 
 
for h in range(1, H):
    status[h, :] = np.minimum(status[h, :], status[h-1, :] + 1)
for h in range(0, H-1)[::-1]:
    status[h, :] = np.minimum(status[h, :], status[h+1, :] + 1)
for w in range(1, W):
    status[:, w] = np.minimum(status[:, w], status[:, w-1] + 1)
for w in range(0, W-1)[::-1]:
    status[:, w] = np.minimum(status[:, w], status[:, w+1] + 1)
 
print(np.max(status))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Apr 13 09:53:12 2019

@author: Owner
"""

#import numpy as np
"""
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect
"""

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

"""
H, W = list(map(int, input().split()))
# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
A = [""]*H 
#INF = np.Inf
INF = 2000

#D = np.zeros((H, W))
D = [[0]*W for h in range(H)]
for h in range(H):
    A[h] = input()
    for w in range(W):
        if A[h][w] == '.':
            D[h][w] = INF

def main():
    d_max = 0 
    for h in range(1,H):
        for w in range(1,W):
            D[h][w] = min(D[h][w], D[h-1][w]+1, D[h][w-1]+1, D[h-1][w-1]+2)
    #print(D)
    
    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                pass
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
            d_max = max(D[H-h-1][W-w-1], d_max)
    #print(D)
    #print(int(np.amax(D)))
    print(int(d_max))
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

q=[]
for h in range(1,H+1):
    for w in range(1,W+1):
        if board[h][w]:
            q.append((h,w))

cnt=0
while q:
    nq=[]
    for h,w in q:
        if not board[h+1][w]:
            board[h+1][w]=True
            nq.append((h+1,w))
        if not board[h-1][w]:
            board[h-1][w]=True
            nq.append((h-1,w))
        if not board[h][w+1]:
            board[h][w+1]=True
            nq.append((h,w+1))
        if not board[h][w-1]:
            board[h][w-1]=True
            nq.append((h,w-1))

    q=nq
    cnt+=1

print(cnt-1)

Submission status: Accepted

Solution code:
from collections import deque

h,w = map(int, input().split())
# 場外を追加
A = [['*']*(w+2)] + [['*']+[s for s in input()]+['*'] for _ in range(h)] + [['*']*(w+2)]
visited = [[0]*(w+2) for _ in range(h+2)]

dq = deque()
n=0
directions = [[0,1],[1,0],[0,-1],[-1,0]]
# 初期配置の黒をキューに追加
for hi in range(1,h+1):
    for wi in range(1,w+1):
        if A[hi][wi] == '#':
            dq.append([hi,wi,n])
            visited[hi][wi] = 1
# キューが空になるまで
while dq:
    hi,wi,n = dq.popleft()

    for d in directions:
        new_hi, new_wi = hi+d[0],wi + d[1]
        # 「黒くしてない白マス」をキューに追加
        if visited[new_hi][new_wi] == 0 and A[new_hi][new_wi] == '.':
            dq.append([new_hi,new_wi,n+1])
            visited[new_hi][new_wi] = 1
print(n)

Submission status: Accepted

Solution code:
import collections #deque

h,w = [int(i) for i in input().split()]
board = [input() for j in range(h)] # 縦「n」行

dx4=[0, 1, 0,-1]
dy4=[1, 0,-1, 0]
#dx8=[0, 1, 0,-1,1,-1,1,-1]
#dy8=[1, 0,-1, 0,1,1,-1,-1]

#memo: 負なら未確認、0以上なら最短距離
memo = [[-1]*w for _ in range(h)]

q = collections.deque()
#初期状態をキューに入れる-----------------------------------------------------
#キューに入れる時点で使用したかどうかのmemoを更新-----------------------------
for i in range(h):
    for j in range(w):
        if board[i][j] == "#":
            q.append((i,j)) #初期状態をキューに入れる
            memo[i][j] = 0 #初期状態を訪問済みにする

while len(q) != 0:
    x,y = q.popleft() #キューから情報を取り出す
    #foreach (x,y)のお隣さん に対して処理-------------------------------------
    for i in range(4):
        nx = x + dx4[i]
        ny = y + dy4[i]
        #範囲外ならスキップ---------------------------------------------------
        if nx < 0 or nx>=h or ny <0 or ny>=w: continue
        #壁ならスキップ-------------------------------------------------------
        #if board[nx][ny] == "#": continue
        #(nx,ny)が確認済みならスキップ----------------------------------------
        if memo[nx][ny] >= 0: continue
        #(nx,ny)が未確認のとき、確認済みにしてキューに入れる------------------
        memo[nx][ny] = memo[x][y]+1
        q.append((nx,ny))
        #経路復元が必要なとき-------------------------------------------------
        # prev[nx][ny] = [x,y]

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

print(ans)

Submission status: Accepted

Solution code:
H, W = map(int,input().split())
A = [input() for i in range(H)]
q1 = []
q2 = []
visit = [[False]*W for i in range(H)]
cnt = 0

for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            q1.append([i,j])
            visit[i][j] = True

while q1:
    while q1:
        index = q1.pop()
        for i in [-1,1]:
            for j in [-1,1]:
                if index[0]+i >= 0 and index[0]+i < H:
                    if not visit[index[0]+i][index[1]]:
                        visit[index[0]+i][index[1]] = True
                        q2.append([index[0]+i,index[1]])
                if index[1]+j >= 0 and index[1]+j < W:
                    if not visit[index[0]][index[1]+j]:
                        visit[index[0]][index[1]+j] = True
                        q2.append([index[0],index[1]+j])
    q1 = q2[:]
    q2 = []
    cnt += 1
    
print(cnt-1)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
grid = [["#"] * (W + 2)] + [list("#" + input() + "#")
                            for i in range(H)] + [["#"]*(W+2)]
# print(grid)
stack = deque()
for h in range(1, H+1):
    for w in range(1, W+1):
        # 黒ならスタックにpush
        if grid[h][w] == "#":
            stack.append([h, w])

for i in range(h + w + 3):
    tmp = deque()
    while stack:
        h, w = stack.pop()
        for dh, dw in ([0, 1], [0, -1], [1, 0], [-1, 0]):
            if grid[h + dh][w + dw] == ".":
                grid[h + dh][w + dw] = "#"
                tmp.append([h + dh, w + dw])
    stack = tmp
    if not stack:
        print(i)
        break

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
grid = [["#"] * (W + 2)] + [list("#" + input() + "#")
                            for i in range(H)] + [["#"]*(W+2)]
# print(grid)
stack = deque()
for h in range(1, H+1):
    for w in range(1, W+1):
        # 黒ならスタックにpush
        if grid[h][w] == "#":
            stack.append([h, w])

for i in range(h + w + 3):
    tmp = deque()
    while stack:
        h, w = stack.pop()
        for dh, dw in ([0, 1], [0, -1], [1, 0], [-1, 0]):
            if grid[h + dh][w + dw] == ".":
                grid[h + dh][w + dw] = "#"
                tmp.append([h + dh, w + dw])
    stack = tmp
    if not stack:
        print(i)
        break

Submission status: Accepted

Solution code:
import functools
@functools.lru_cache(maxsize=None)

def main():
    from collections import deque
    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
                    grid[my+y][mx+x]="#"
                    tmp.append([my+y,mx+x])
        stack=tmp
        if not tmp:
            print(i)
            break
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    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
                    grid[my+y][mx+x]="#"
                    tmp.append([my+y,mx+x])
        stack=tmp
        if not tmp:
            print(i)
            break
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())
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
                grid[my+y][mx+x]="#"
                tmp.append([my+y,mx+x])
    stack=tmp
    if not tmp:
        print(i)
        break

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    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 not tmp:
            print(i)
            break
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())
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 not tmp:
        print(i)
        break

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 not tmp:
        print(i)
        break

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[True]*(W+2)]
mark_matrix.extend([[True]+[x!='.' for x in input()] for _ in range(H)])
mark_matrix[H].append(True)
mark_matrix.append([True]*(W+2))

queue = []
for i in range(1,H+1):
  for j in range(1,W+1):
    if mark_matrix[i][j]:
      queue.append((i,j))
 
max_value = 0
while(True):
  if len(queue) == 0:
    break
  
  new_queue = []
  for i,j in queue:
  
    if not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      new_queue.append((i-1,j))
    if not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      new_queue.append((i+1,j))
    if not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      new_queue.append((i,j-1))
    if not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      new_queue.append((i,j+1))
 
  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
print(max_value)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[True]*(W+2)]
#mark_matrix.extend([[True]+[False]*(W)+[True] for _ in range(H)])
mark_matrix.extend([[True]+[x!='.' for x in input()] for _ in range(H)])
mark_matrix[H].append(True)
mark_matrix.append([True]*(W+2))
#queue = []
queue = deque()
for i in range(1,H+1):
  for j in range(1,W+1):
    if mark_matrix[i][j]:
      queue.append((i,j))
#  line = input()
#  for j,ch in enumerate(line):
#    if ch == "#":
#      mark_matrix[i+1][j+1] = True
#      queue.append((i+1,j+1))
#for i in range(1,H+1):
#  mark_matrix[i][0] = True
#  mark_matrix[i][W+1] = True
#for j in range(W+2):
#  mark_matrix[0][j] = True
#  mark_matrix[H+1][j] = True
#print(mark_matrix)
 
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  new_queue = deque()
  for i,j in queue:
  
    if not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      #queue.append((i-1,j))
      new_queue.append((i-1,j))
    if not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      #queue.append((i+1,j))
      new_queue.append((i+1,j))
    if not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      #queue.append((i,j-1))
      new_queue.append((i,j-1))
    if not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      #queue.append((i,j+1))
      new_queue.append((i,j+1))
 
  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
#print(cnt)
#print(dist_matrix)
print(max_value)

Submission status: Accepted

Solution code:
H, W = (int(_) for _ in input().split())
grid = []
black = []
nextb = []
count = 0
total = 0
white = True
for i in range (H):
    line = input()
    for j in range(W):
        if line[j] == '#':
            black.append([i,j])
            total += 1
    grid.append([line[j] for j in range(W)])

if H == 1 and W == 1:
    print(0)
else:
    if total == H*W:
        print(0)
        exit()
    while white:
        for coord in black:
            y = coord[0]
            x = coord[1]
            if y > 0:
                if grid[y-1][x] == '.':
                    grid[y-1][x] = '#'
                    nextb.append([y-1, x])
                    total += 1
            if y <= H-2:
                if grid[y+1][x] == '.':
                    grid[y+1][x] = '#'
                    nextb.append([y+1, x])
                    total += 1
            if x > 0:
                if grid[y][x-1] == '.':
                    grid[y][x-1] = '#'
                    nextb.append([y, x-1])
                    total += 1
            if x <= W-2:
                if grid[y][x+1] == '.':
                    grid[y][x+1] = '#'
                    nextb.append([y, x+1])
                    total += 1
        black = nextb
        nextb = []
        count += 1
        if total == H*W:
            white = False
        
    print(count)

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_lte():
    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)

import numpy as np
from scipy import ndimage

def main_scipy():
    H, W = i2nn()
    A = ii2ss(H)
    A = [[0 if s == '#' else -1 for s in line] for line in A]
    B = ndimage.morphology.distance_transform_cdt(A, metric='taxicab')
    n = np.max(B)
    print(n)

def main():
    main_scipy()

main()

Submission status: Accepted

Solution code:
import math
import time
import pprint
import sys
from collections import deque
pp = pprint.PrettyPrinter(width = 30)
sys.setrecursionlimit(10**7)
INF = 10 ** 18
def MI(): return map(int, sys.stdin.readline().split())
def IS(): return input()
def bfs(q):
    # かかる歩数
    require = [[0 for i in range(w)] for j in range(h)]
    # 訪れたかどうか
    check = [[0 for i in range(w)] for j in range(h)]
    x_diff = [-1, 0, 1, 0]
    y_diff = [0, 1, 0, -1]
    while len(q) != 0:
        tmp_y, tmp_x = q.popleft()
        # print(tmp_y, tmp_x)
        for i in range(4):
            next_y = tmp_y + y_diff[i]
            next_x = tmp_x + x_diff[i]
            if ( 0 <= next_x <= w-1 
                    and 0 <= next_y <= h-1 
                    and check[next_y][next_x] == 0 
                    and a[next_y][next_x] != '#'):
                check[next_y][next_x] = 1 
                require[next_y][next_x] = require[tmp_y][tmp_x] + 1
                q.append([next_y, next_x])
                # pp.pprint(check)
    return require


h, w = MI()
a = [IS() for _ in range(h)]
# start = time.time()
# h, w = 1000, 1000
# a = ['#.#.' * (w//4) for _ in range(h)]
out = 0
que = deque()

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            que.append([i,j])
# print(que)

ans = bfs(que)

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

# print(time.time() - start)
print(out)

Submission status: Accepted

Solution code:
from collections import deque
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=deque()
    c=0
    for i in range(h):
        for j in range(w):
            if a[i][j]==0:
                q.append((i,j))
    while(len(q)>0):
        cur=q.popleft()
        i,j=cur
        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:
                c=a[i][j]+1
                a[i+di][j+dj]=c
                q.append((i+di,j+dj))
    return(c)

print(bfs())