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


■考え方
以下を繰り返し、白マスがなくなった時点のカウンターが答え。
1.黒マスに隣接する白マスを黒マスに塗り替える
2.カウンターに+1する

1詳細
1-0.現在の黒マスを全てキューへ入れる
1-1.キューから取り出し、隣接マスを「黒に塗り、キューへ入れる」
1-2. 1-1を繰り返し


'''
## import
from collections import deque # キュー、スタックに利用
# import itertools
# import math # 数学的計算に利用
# import numpy as np # 行列計算などに利用
import sys

## 初期設定
# input = sys.stdin.readline
def input():
    return sys.stdin.readline().rstrip()


sys.setrecursionlimit(10**7) # 再帰関数の呼び出し上限を増やす
inf = float('inf')

is_debug = True


black_str = '#'
white_str = '.'

def paint(q,M,h,w):
    '''
    キューから黒マスの位置を取り出し、隣接マスを「黒に塗り、キューへ入れる」
    '''
    out_q = deque()
    # 探索時の移動方向（上右下左） # delta y, delta x
    deltas = [[-1,0], [0,1], [1,0], [0,-1]]
    
    while len(q) > 0:
        # 探索する頂点uを取り出し
        y, x = q.popleft()

        ## uに隣接する全ての頂点について、白い場合は黒く塗り、out_qへ追加
        for delta in deltas:
            # 移動後の位置を算出
            after_y = y+delta[0]
            after_x = x+delta[1]
            # h,wの範囲に収まっていなければスキップ
            if after_y < 0 or after_y > h-1 or after_x < 0 or after_x > w-1:
                continue

            if M[after_y][after_x] == white_str:
                M[after_y][after_x] = black_str
                # out_qに追加
                out_q.append([after_y,after_x]) # キューに追加
    
    return out_q


def main():
    '''メイン処理'''

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

    ans = 0
    # 塗るマスの位置を保持するキューを初期化
    q = deque()

    while True:
        ## 全てのマスが黒になったら終了
        # 以下の処理を入れると遅そうなのでコメントアウト
        # if white_str not in list(itertools.chain.from_iterable(M)):
        #     break

        # 各ターンで塗るマス。1=blackに塗るマス
        # paint_M = [[0]*w for _ in range(h)

        # 初回の場合、現在の黒マスを全てキューへ入れる
        if ans == 0:
            for i in range(h):
                for j in range(w):
                    if M[i][j] == black_str:
                        q.append([i,j])
        
        # キューから取り出し、隣接マスを「黒に塗り、キューへ入れる」
        q = paint(q,M,h,w)
        # 全てのマスが黒になったら終了
        if len(q) == 0:
            break

        ans += 1

    print(ans)


if __name__ == "__main__":
    # ファイル実行時に、main()関数を実行
    main()

Submission status: Accepted

Solution code:
#AGC033-A-Darker and Darker
from collections import deque

h,w = map(int,input().split())
grid = [input() for i in range(h)]

#初期の黒('#')の位置からの距離
dist = [[-1]*w for _ in range(h)]

p = deque()
d = 0
for i in range(h):
    for j in range(w):
        if grid[i][j] == '#':
            p.append((i,j))
            dist[i][j] = 0

while p:
    y,x = p.popleft()
    d = dist[y][x]
    for dy,dx in ((1,0),(0,1),(-1,0),(0,-1)):
        if 0<= x+dx < w and 0<= y+dy < h and dist[y+dy][x+dx] == -1:
            dist[y+dy][x+dx] = d+1
            p.append((y+dy,x+dx))

    
print(d)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque


class BFS():
    def __init__(self, grid_graph):
        # grid表現
        self.graph = grid_graph
        self.H = len(self.graph)
        self.W = len(self.graph[0])
        # 始点からの距離
        self.dist = [[-1]*self.W for i in range(self.H)]
        # キュー
        self.que = deque()

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

        # 初期条件(0-indexed)
        for sv in sv_arr:
            self.dist[sv[0]][sv[1]] = 0
            self.que.append(sv)

        while self.que:
            v = self.que.popleft()
            for _dx, _dy in zip(dx,dy):
                nv = [v[0]+_dx,v[1]+_dy]
                if not 0<=nv[0]<self.H: continue 
                if not 0<=nv[1]<self.W: continue
                if self.dist[nv[0]][nv[1]] != -1: continue
                self.dist[nv[0]][nv[1]] = self.dist[v[0]][v[1]] + 1
                self.que.append(nv)


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  # type:list(str)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    bfs = BFS(graph)

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

    bfs.bfs(sv_arr)
    cnt = max(max(_) for _ in bfs.dist)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np

h , w = map(int, input().split())
visited = np.zeros((h,w),dtype=int)

for y in range(h):
    _in = input()
    for x, value in enumerate(_in):
        if value == '.':
            visited[y][x] = 10**9
            
for i in range(1,h):
    visited[i,:] = np.minimum(visited[i,:],visited[i-1,:]+1)
for i in reversed(range(h-1)):
    visited[i,:] = np.minimum(visited[i,:],visited[i+1,:]+1)
for j in range(1,w):
    visited[:,j] = np.minimum(visited[:,j],visited[:,j-1]+1)
for j in reversed(range(w-1)):
    visited[:,j] = np.minimum(visited[:,j],visited[:,j+1]+1)
print(np.max(visited))

Submission status: Accepted

Solution code:
import numpy as np

H,W = map(int,input().split())
use = np.zeros((H,W),dtype=int)
for i in range(H):
    s = input()
    for j,st in enumerate(s):
        if st == ".":
            use[i][j] = 10**9

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

print(np.max(use))

Submission status: Accepted

Solution code:
import numpy as np

H,W = map(int,input().split())
use = np.zeros((H,W),dtype=int)
for i in range(H):
    s = input()
    for j,st in enumerate(s):
        if st == ".":
            use[i][j] = 10**10
        else:
            use[i][j] = 0

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

print(np.max(use))

Submission status: Accepted

Solution code:
from collections import deque

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

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

def bfs(M,dist):
    d=0
    while M:
        x,y=M.popleft()
        d=dist[x][y]
        for dx,dy in ((1,0),(0,1),(-1,0),(0,-1)):
            new_h=x+dy
            new_w=y+dx
            if new_h < 0 or H <= new_h or new_w <0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:
                dist[new_h][new_w]=d+1
                M.append((new_h,new_w))
    return d

d=bfs(M,dist)
print(d)

Submission status: Accepted

Solution code:
from collections import deque

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

black_cells=deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == "#":
            black_cells.append((h,w))
            dist[h][w]=0

def bfs(black_cells,dist):
        d=0
        while black_cells:
            h,w=black_cells.popleft()
            d=dist[h][w]
            for dx, dy in ((1,0),(0,1),(-1,0),(0,-1)):
                new_h=h+dy
                new_w=w+dx
                if new_h <0 or H <= new_h or new_w < 0 or W<=new_w:
                    continue
                if dist[new_h][new_w]==-1:
                    dist[new_h][new_w]=d+1
                    black_cells.append((new_h,new_w))
        return d

d=bfs(black_cells,dist)
print(d)

Submission status: Accepted

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

Bs = []
for i in range(H):
    for j in range(W):
        if M[i][j]=="#":
            Bs.append([i,j])

from collections import deque
memo = [[2000] * W for i in range(H)]
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
que = deque([])
que.append(Bs)
for Bi,Bj in Bs:
    memo[Bi][Bj] = 0

out = 0
while que:
    ps = que.popleft()
    next = []
    for p in ps:
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            if (0<=nx<W)and(0<=ny<H)and(memo[ny][nx]==2000):
                next.append((ny, nx))
                memo[ny][nx] = memo[p[0]][p[1]] + 1
                if memo[ny][nx]>out:
                    out=memo[ny][nx]
    if len(next)>0:
        que.append(next)

print(out)

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    m, n = map(int, input().split())
    grid = [input() for _ in range(m)]

    Q = deque()
    dist = [[INF] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '#':
                dist[i][j] = 0
                Q.append((i, j))

    D = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while Q:
        i, j = Q.popleft()
        for di, dj in D:
            ni, nj = i + di, j + dj
            if not (0 <= ni < m and 0 <= nj < n):
                continue
            if dist[ni][nj] != INF:
                continue
            dist[ni][nj] = dist[i][j] + 1
            Q.append((ni, nj))


    print(max(dist[i][j] for i in range(m) for j in range(n)))
resolve()

Submission status: Accepted

Solution code:
import numpy as np

def main():
    H,W = map(int,input().split())
    use = np.zeros((H,W),dtype=int)
    for i in range(H):
        s = input()
        for j,st in enumerate(s):
            if st == ".":
                use[i][j] = 10**10
            else:
                use[i][j] = 0
    
    for i in range(1,H):
        use[i,:] = np.minimum(use[i,:],use[i-1,:]+1)
    for i in reversed(range(H-1)):
        use[i,:] = np.minimum(use[i,:],use[i+1,:]+1)
    for j in range(1,W):
        use[:,j] = np.minimum(use[:,j],use[:,j-1]+1)
    for j in reversed(range(W-1)):
        use[:,j] = np.minimum(use[:,j],use[:,j+1]+1)
    
    print(np.max(use))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# AGC033A

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = map(int, input().split())
s = [None] * h
for i in range(h):
    s[i] = input()

r = h
c = w
ds = [[10**15]*c for _ in range(r)]
for i in range(r):
    prev = -1
    for j in range(c):
        if s[i][j]=="#":
            prev = j
        if prev>=0:
            ds[i][j] = j-prev
    prev = -1
    for j in range(c-1,-1,-1):
        if s[i][j]=="#":
            prev = j
        if prev>=0:
            ds[i][j] = min(ds[i][j], prev-j)
for j in range(c):
    prev = -1
    prevind = -1
    for i in range(r):
        if prev<0 or ds[i][j]<prev+(i-prevind):
            prev = ds[i][j]
            prevind = i
        if prev>=0:
            ds[i][j] = min(ds[i][j], prev+(i-prevind))
    prev = -1
    prevind = -1
    for i in range(r-1, -1, -1):
        if prev<0 or ds[i][j]<prev+(prevind-i):
            prev = ds[i][j]
            prevind = i
        if prev>=0:
            ds[i][j] = min(ds[i][j], prev+(prevind-i))
print(max(max(item) for item in ds))

Submission status: Accepted

Solution code:
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W = map(int, input().split())
a = [list(input())[: -1] for _ in range(H)]
dist = [[H * W] * W for _ in range(H)]
Q = dq([])
for i in range(H):
  for j in range(W):
    if a[i][j] == "#":
      Q.append((i, j))
      dist[i][j] = 0

d = [-1, 0, 1, 0]
while len(Q):
  y, x = Q.popleft()
  for k in range(4):
    u = y + d[k]
    v = x + d[-1 - k]
    if u in range(H) and (v in range(W)):
      if dist[u][v] > dist[y][x] + 1:
        dist[u][v] = dist[y][x] + 1
        Q.append((u, v))
print(max([max(dist[i]) for i in range(H)]))

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
def main():
    # from math import gcd
    def input():
        return sys.stdin.readline()[:-1]
    def ruiseki(lst):
        return [0]+list(accumulate(lst))
    mod=pow(10,9)+7
    al=[chr(ord('a') + i) for i in range(26)]
    direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

    cnt=0

    itta=[[10**9]*w for i in range(h)]

    d=deque()
    # aaa=d.append
    for i in range(h):
        for j in range(w):
            if a[i][j]=="#":
                d.append((i,j))
                itta[i][j]=0

    # print(d)
    # print(itta)

    while d:
        cnt+=1
        for l in range(len(d)):
            nh,nw=d.popleft()
            for i in range(4):
                d1,d2=direction[i]
                if 0<=nh+d1<h and 0<=nw+d2<w:
                    if itta[nh+d1][nw+d2]==10**9:
                        itta[nh+d1][nw+d2]=cnt
                        d.append((nh+d1,nw+d2))
        # print(d)

    # print(itta)
    print(cnt-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

h,w = map(int,input().split())
c = []
for i in range(h):
  a = input()
  c.append(a)
  
from collections import deque

d = [[-1] * w for i in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

que = deque([])
for i in range(h):
  for j in range(w):
    if c[i][j] == '#':
      que.append((i,j,0))
      d[i][j] = 0

ans = 0
while que:
  p = que.popleft()
  for i in range(4):
      nw = p[1] + dx[i]
      nh = p[0] + dy[i]
      if 0 <= nw < w and 0 <= nh < h and d[nh][nw]==-1:
          que.append((nh,nw,p[2]+1))
          d[nh][nw] = p[2]+1
          ans = max(ans,p[2]+1)

print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

cnt=0

itta=[[10**9]*w for i in range(h)]

d=deque()
# aaa=d.append
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            d.append((i,j))
            itta[i][j]=0

# print(d)
# print(itta)

while d:
    cnt+=1
    for l in range(len(d)):
        nh,nw=d.popleft()
        for i in range(4):
            d1,d2=direction[i]
            if 0<=nh+d1<h and 0<=nw+d2<w:
                if itta[nh+d1][nw+d2]==10**9:
                    itta[nh+d1][nw+d2]=cnt
                    d.append((nh+d1,nw+d2))
    # print(d)

# print(itta)
print(cnt-1)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

cnt=0

itta=[[10**9]*w for i in range(h)]

d=deque()
# aaa=d.append
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            d.append([i,j])
            itta[i][j]=0

# print(d)
# print(itta)

while d:
    cnt+=1
    for l in range(len(d)):
        nh,nw=d.popleft()
        for i in range(4):
            d1,d2=direction[i]
            if 0<=nh+d1<h and 0<=nw+d2<w:
                if itta[nh+d1][nw+d2]==10**9:
                    itta[nh+d1][nw+d2]=cnt
                    d.append([nh+d1,nw+d2])
    # print(d)

# print(itta)
print(cnt-1)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

cnt=0

itta=[[10**9]*w for i in range(h)]

d=deque()
aaa=d.append
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            aaa([i,j])
            itta[i][j]=0

# print(d)
# print(itta)

while d:
    cnt+=1
    for l in range(len(d)):
        nh,nw=d.popleft()
        for i in range(4):
            d1,d2=direction[i]
            if 0<=nh+d1<h and 0<=nw+d2<w:
                if itta[nh+d1][nw+d2]==10**9:
                    itta[nh+d1][nw+d2]=cnt
                    aaa([nh+d1,nw+d2])
    # print(d)

# print(itta)
print(cnt-1)

Submission status: Accepted

Solution code:
from collections import deque

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

max_d = 0
while que:
    y, x = que.popleft()
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    for i in range(4):
        ny = y+dy[i]
        nx = x+dx[i]
        if ny < 0 or ny >= h or nx < 0 or nx >= w:
            continue
        if a[ny][nx] == '#':
            continue
        if dst[ny][nx] != -1:
            continue

        dst[ny][nx] = dst[y][x] + 1
        max_d = dst[y][x] + 1
        que.append([ny, nx])
print(max_d)

Submission status: Accepted

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

arr = ["0" *(w + 2)]
for i in range(h):
    arr.append("0" + input() + "0")
arr.append("0" *(w + 2))

flg = [[-1 for i in range(w+2)] for j in range(h+2)]

ima = []
for i in range(h+2):
    for j in range(w+2):
        if arr[i][j] == "#":
            ima.append([i,j])
            flg[i][j] = 0

while len(ima) > 0:
    tugi = []
    for x,y in ima:
        if arr[x+1][y] == "." and flg[x+1][y] == -1:
            tugi.append([x+1,y])         
            flg[x+1][y] = flg[x][y] + 1
        if arr[x-1][y] == "." and flg[x-1][y] == -1:
            tugi.append([x-1,y])
            flg[x-1][y] = flg[x][y] + 1
        if arr[x][y+1] == "." and flg[x][y+1] == -1:
            tugi.append([x,y+1])
            flg[x][y+1] = flg[x][y] + 1
        if arr[x][y-1] == "." and flg[x][y-1] == -1:
            tugi.append([x,y-1])
            flg[x][y-1] = flg[x][y] + 1
    ima = tugi

ans = -1
for i in flg:
    for j in i:
        if ans < j:
            ans = j
print(ans)

Submission status: Accepted

Solution code:
# A - Darker and Darker
from collections import deque

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

queue = deque([])

for i in range(H):
    A = input()
    for j in range(W):
        if A[j]=='#':
            B[i][j] = 0
            queue.append((i,j))

ans = 0

while queue:
    I,J = queue.popleft()
    for di,dj in ((-1,0),(1,0),(0,-1),(0,1)):
        i,j = I+di,J+dj
        if 0<=i<H and 0<=j<W:
            if B[i][j]<0:
                B[i][j] = B[I][J]+1
                ans = max(ans,B[i][j])
                queue.append((i,j))

print(ans)

Submission status: Accepted

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

    q = deque()
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                q.append((h,w))
    
    q.append((-1,-1))
    ans = 0
    while len(q) > 0:
        h,w = q.popleft()
        if h == -1 and w == -1:
            if len(q) > 0:
                q.append((-1,-1))
                ans += 1
            continue

        d = ((0,1),(0,-1),(1,0),(-1,0))
        for dh, dw in d:
            if 0 <= h+dh < H and 0 <= w+dw < W and A[h+dh][w+dw] == '.':
                A[h+dh][w+dw] = '#'
                q.append((h+dh,w+dw))
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

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


# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    h, w = input_to_int_map()
    zone = [input() for i in range(h)]

    from collections import deque
    black_cell = deque()

    black_distance = [[-1] * w for i in range(h)]
    for i, row in enumerate(zone):
        for j, cell in enumerate(row):
            if cell == "#":
                black_cell.append((i, j))
                black_distance[i][j] = 0

    while black_cell:
        black_h, black_w = black_cell.popleft()
        pre_black_distance = black_distance[black_h][black_w]
        for i, j in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            move_h = black_h + i
            move_w = black_w + j
            if move_h < 0 or move_w < 0 or move_h >= h or move_w >= w:
                continue
            if black_distance[move_h][move_w] == -1:
                black_distance[move_h][move_w] = pre_black_distance + 1
                black_cell.append((move_h, move_w))

    return max(list(map(max, black_distance)))


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

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
maze = []
for _ in range(h):
    maze.append(list(input()))
import collections
black = collections.deque([])
cnt = 0
for hh in range(h):
    for ww in range(w):
        if maze[hh][ww] == "#":
            cnt += 1
            black.append([hh, ww, 0])
dh = [ 0, -1, 1, 0]
dw = [ -1, 0, 0, 1]
res = 0
allcount = h*w
res = 0
while cnt < allcount:
    #print("black:", black)
    bh, bw , bturn= black.popleft()
    #print("pop", bh, bw, bturn)
    for di in range(len(dh)):
        nh = bh + dh[di]
        nw = bw + dw[di]
        if nh < 0 or nh > (h-1) or nw < 0 or nw > (w-1):
            continue
        if maze[nh][nw] == "#":
            continue
        black.append([nh, nw, bturn+1])
        #print(nh, nw)
        maze[nh][nw] = "#"
        res = max(res, bturn+1)
        cnt += 1
print(res)

Submission status: Accepted

Solution code:
from subprocess import *
call(('pypy3','-c',"""
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    h,w=map(int,input().split())
    B=[[-1]*w for _ in range(h)]
    ans=0
    que=deque()
    for i in range(h):
        s=input()
        for j,ss in enumerate(s):
            if ss=="#":
                que.append((i,j))
                B[i][j]=0
    while que:
        qr,qc=que.popleft()
        for r,c in ((qr+1,qc),(qr-1,qc),(qr,qc+1),(qr,qc-1)):
            if r>=0 and r<=h-1 and c>=0 and c<=w-1 and B[r][c]==-1:
                B[r][c]=B[qr][qc]+1
                que.append((r,c))
    print(max([max(b) for b in B]))

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

Submission status: Accepted

Solution code:
from collections import deque

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

#右上左下
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]


ans = 0

que = deque()

num_white = H * W

paint = 0

for i in range(H):
    for j in range(W):
        if field[i][j] == "#":
            que.append((i, j))
            num_white -= 1

def check(field):
    flag = False
    for i in range(H):
        if "." in field[i]:
            flag = True

    return flag

def one_bsf():
    global paint
    global que
    global ans

    for _ in range(len(que)):
        n = que.popleft()
        ny = n[0]
        nx = n[1]

        for i in range(4):
            nny = ny + dy[i]
            nnx = nx + dx[i]

            if nny < 0 or nny >= H or nnx < 0 or nnx >= W:
                continue

            elif field[nny][nnx] == ".":
                field[nny][nnx] = "#"
                paint += 1
                que.append((nny, nnx))

    ans += 1

while num_white != paint:
    one_bsf()
    
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    H, W = map(int, rl().split())
    grid = [[] for _ in range(H)]
    que = deque()
    for i in range(H):
        grid[i] = list(rl().rstrip())
        for j in range(W):
            if grid[i][j] == '#':
                que.append((i, j))
    
    ans = -1
    while que:
        n = len(que)
        for _ in range(n):
            cy, cx = que.popleft()
            for dy, dx in ((-1, 0), (0, 1), (1, 0), (0, -1)):
                ny, nx = cy + dy, cx + dx
                if 0 <= nx < W and 0 <= ny < H:
                    if grid[ny][nx] == '.':
                        grid[ny][nx] = '#'
                        que.append((ny, nx))
        ans += 1
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    H,W = LI()
    f = [[0] * W for _ in range(H)]
    q = collections.deque()
    for i in range(H):
        for j,x in enumerate(sys.stdin.readline().rstrip()):
            if x == '#':
                f[i][j] = 1
                q.append((i,j,0))
    ans = 0
    while q:
        y,x,c = q.popleft()
        ans = max(ans,c)
        for dy,dx in ((0,1),(1,0),(-1,0),(0,-1)):
            if 0 <= x+dx < W and 0 <= y+dy < H:
                if f[y+dy][x+dx] == 0:
                    f[y+dy][x+dx] = 1
                    q.append((y+dy,x+dx,c+1))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

from collections import deque
move=[(0,1),(0,-1),(1,0),(-1,0)]

que=deque([])

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

c=0
visit=[[0]*w for _ in range(h)]
while len(que)>0:
    ni,nj,c=que.popleft()
    for di,dj in move:
        mi,mj=ni+di,nj+dj
        if 0<=mi<h and 0<=mj<w and G[mi][mj]=='.' and visit[mi][mj]==0:
            visit[mi][mj]=1
            que.append((mi,mj,c+1))
print(c)

Submission status: Accepted

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

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
dist = [[-1]*w for _ in range(h)]  # 黒ならdist[i][j]は0、白なら-1

black_cells = deque()

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

def bfs(black_cells, dist):
    d = 0
    while black_cells:
        h_black, w_black = black_cells.popleft()
        d=dist[h_black][w_black]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h_black+dy
            new_w = w_black+dx
            if new_h < 0 or h <= new_h or new_w < 0 or w <= new_w:
                continue
            if dist[new_h][new_w] == -1:
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)

Submission status: Accepted

Solution code:
from collections import deque


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

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


ans = 0
dyx = [(1,0), (0,1), (-1,0), (0,-1)]
while q:
    flag = False
    for _ in range(len(q)):
        y,x = q.popleft()
        for dy, dx in dyx:
            ny, nx = y+dy, x+dx
            if not 0 <= ny <= H-1 or not 0 <= nx <= W-1:
                continue
            if A[ny][nx] == ".":
                q.append((ny, nx))
                A[ny][nx] = "#"
                flag = True
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
 
H, W = [int(x) for x in input().split()]
cell = [list(input()) for i in range(H)]
 
painted = deque()
for h in range(H):
    for w in range(W):
        if cell[h][w] == '#':
            painted.append([h, w, 0])
 
ans = 0
while len(painted) > 0:
    blackcell = painted.popleft()
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = blackcell[0] + dy
        nw = blackcell[1] + dx
        d = blackcell[2]
        if 0 <= nh < H and 0 <= nw < W and cell[nh][nw] == '.':
            cell[nh][nw] = '#'
            painted.append([nh, nw, d + 1])
        ans = d
 
print(ans)

Submission status: Accepted

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

from collections import deque

lst = deque()

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


def chg(i, j):
    if i < 0 or j < 0 or H <= i or W <= j: return False
    if A[i][j] == '.':
        A[i][j] = '#'
        return True
    return False


ans = 0
while lst:
    h, w, v = lst.popleft()
    ans = max(v, ans)
    for i in range(-1, 2):
        for j in range(-1, 2):
            if i != 0 and j != 0: continue

            if chg(h + i, w + j):
                lst.append((h + i, w + j, v + 1))
print(ans)