Problem:


Score : 300 points

Problem Statement

You are given a grid of squares with H horizontal rows and W vertical columns, where each square is painted white or black.
HW characters from A_{11} to A_{HW} represent the colors of the squares.
A_{ij} is # if the square at the i-th row from the top and the j-th column from the left is black, and A_{ij} is . if that square is white.

We will repeatedly perform the following operation until all the squares are black:

Every white square that shares a side with a black square, becomes black.

Find the number of operations that will be performed.
The initial grid has at least one black square.

Constraints

1 \leq H,W \leq 1000

A_{ij} is # or ..

The given grid has at least one black square.

Input

Input is given from Standard Input in the following format:

H W
A_{11}A_{12}...A_{1W}
:
A_{H1}A_{H2}...A_{HW}

Output

Print the number of operations that will be performed.

Sample Input 1

3 3
...
.#.
...

Sample Output 1

2

After one operation, all but the corners of the grid will be black. After one more operation, all the squares will be black.

Sample Input 2

6 6
..#..#
......
#..#..
......
.#....
....#.

Sample Output 2

3



Sample input:
3 3
...
.#.
...


Sample output:
2

Submission status: Accepted

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

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

    m = [list(map(lambda x: 1 if x=="#" else 0, input())) for _ in range(H)]
    black = [(i, j, 0) for i in range(H) for j in range(W) if m[i][j] == 1]

    # print(m)
    # print(black)

    queue = deque(black)
    queue_append = queue.append
    ans = 0
    while queue:
        p = queue.popleft()
        if ans < p[2]:
            ans += 1
        for i, j in ((-1, 0), (1, 0), (0, 1), (0, -1)):
            next_p = (p[0] + i, p[1] + j)
            if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
                if not m[next_p[0]][next_p[1]]:
                    m[next_p[0]][next_p[1]] = 1
                    queue_append((next_p[0], next_p[1], ans+1))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

m = [[0 for _ in range(W)] for _ in range(H)]
black = []
for i in range(H):
    # m.append(list(map(lambda x: 0 if x=="#" else 1, input()))）
    for j, c in enumerate(input()):
        if c == "#":
            m[i][j] = 1
            black.append((i, j, 0))

# print(m)
# print(root)

queue = deque(black)
queue_append = queue.append
ans = 0
while queue:
    p = queue.popleft()
    if ans < p[2]:
        ans += 1
    for i, j in ((-1, 0), (1, 0), (0, 1), (0, -1)):
        i_next_p, j_next_p = (p[0] + i, p[1] + j)
        if (0 <= i_next_p < H) and (0 <= j_next_p < W):
            if not m[i_next_p][j_next_p]:
                m[i_next_p][j_next_p] = 1
                queue_append((i_next_p, j_next_p, ans+1))
print(ans)

Submission status: Accepted

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

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

m = [[0 for _ in range(W)] for _ in range(H)]
black = []
for i in range(H):
    # m.append(list(map(lambda x: 0 if x=="#" else 1, input()))）
    for j, c in enumerate(input()):
        if c == "#":
            m[i][j] = 1
            black.append((i, j, 0))

# print(m)
# print(root)

queue = deque(black)
queue_append = queue.append
ans = 0
while queue:
    p = queue.popleft()
    if ans < p[2]:
        ans += 1
    for i, j in ((-1, 0), (1, 0), (0, 1), (0, -1)):
        next_p = (p[0] + i, p[1] + j)
        if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
            if not m[next_p[0]][next_p[1]]:
                m[next_p[0]][next_p[1]] = 1
                queue_append((next_p[0], next_p[1], ans+1))
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

def main():
  H,W = map(int,input().split())
  maze = [list(input())for _ in range(H)]
  for i in range(H):
    for j in range(W):
      if maze[i][j]=="#":
        maze[i][j]=0
      else:
        maze[i][j]=float('INF')
  maze = np.array(maze)
  for i in range(1,H):
    maze[i,:]=np.minimum(maze[i,:],maze[i-1,:]+1)
  for i in range(H-2,-1,-1):
    maze[i,:]=np.minimum(maze[i,:],maze[i+1,:]+1)
  for i in range(1,W):
    maze[:,i]=np.minimum(maze[:,i],maze[:,i-1]+1)
  for i in range(W-2,-1,-1):
    maze[:,i]=np.minimum(maze[:,i],maze[:,i+1]+1)
  print(int(np.max(maze)))
main()

Submission status: Accepted

Solution code:
import numpy
import sys
input = sys.stdin.readline
H,W = map(int,input().split())
INF = H * W
S = numpy.array([[INF if i == '.' else 0 for i in input().strip()] for _ in range(H)])

for h in range(1, H):
    S[h, :] = numpy.minimum(S[h,:],S[h-1,:] + 1)
for h in range(H - 2, -1, -1):
    S[h, :] = numpy.minimum(S[h,:],S[h+1,:] + 1)
for w in range(1, W):
    S[:, w] = numpy.minimum(S[:,w],S[:,w-1] + 1)
for w in range(W - 2, -1, -1):
    S[:, w] = numpy.minimum(S[:,w],S[:,w+1] + 1)

print(numpy.max(S))

Submission status: Accepted

Solution code:
from collections import deque

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

for y in range(H):
    for x, v in enumerate(input()):
        if v == '#':
            data.append((y, x))

ans = [[-1 for _ in range(W)] for __ in range(H)]

for v in data:
    ans[v[0]][v[1]] = 0

"""
BFSまとめ

0. 
現在位置、履歴、アクション数の3要素が必要.
処理をLIFOでなく、FIFOでやる
そのため、collection.dequeを使う
更にソートしつつ、FIFOしたい場合は、heapqを使う

1. 
更新する, アクション数を加算する

2. 
条件を一致しているか、履歴に入っていないかを確認

3. 
popをループ
"""

d = 0
while len(data):
    y, x = data.popleft()
    d = ans[y][x]

    for i, j in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        new_y = y + i
        new_x = x + j
        if new_y < 0 or H <= new_y or new_x < 0 or W <= new_x:
            continue
        if ans[new_y][new_x] == -1:
            ans[new_y][new_x] = d + 1
            data.append((new_y, new_x))

print(max([a for aa in ans for a in aa]))

Submission status: Accepted

Solution code:
from collections import deque

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

m = [[0 for _ in range(W)] for _ in range(H)]
root = []
for i in range(H):
    # m.append(list(map(lambda x: 0 if x=="#" else 1, input()))）
    for j, c in enumerate(input()):
        if c == "#":
            m[i][j] = 1
            root.append((i, j))

# print(m)
# print(root)

queue = deque(root)
visited = deque(root)
visited_extend = visited.extend
ans = 0
while len(visited) < H*W:
    # print(visited)
    ans += 1
    new_queue = deque([])
    while queue:
        p = queue.popleft()
        for i, j in ([-1, 0], [1, 0], [0, 1], [0, -1]):
            next_p = (p[0] + i, p[1] + j)
            if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
                if not m[next_p[0]][next_p[1]]:
                    m[next_p[0]][next_p[1]] = 1
                    new_queue.append(next_p)
    visited_extend(new_queue)
    queue = new_queue
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

def main():
  H,W = map(int,input().split())
  maze = np.array([[0 if x == "#" else float('INF') for x in input()]for _ in range(H)])
  for i in range(1,H):
    maze[i,:]=np.minimum(maze[i,:],maze[i-1,:]+1)
  for i in range(H-2,-1,-1):
    maze[i,:]=np.minimum(maze[i,:],maze[i+1,:]+1)
  for i in range(1,W):
    maze[:,i]=np.minimum(maze[:,i],maze[:,i-1]+1)
  for i in range(W-2,-1,-1):
    maze[:,i]=np.minimum(maze[:,i],maze[:,i+1]+1)
  print(int(np.max(maze)))

main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)
inf=10**7


def BFS():
    color=[["white" for _ in range(w+2)] for _ in range(h+2)]
    D=[[inf for _ in range(w+2)] for _ in range(h+2)]

    queue=deque([])
    for i in range(1,h+1):
        for j in range(1,w+1):
            if A[i][j]=="#":
                queue.append([i,j])
                D[i][j]=0
                color[i][j]="gray"

    cnt=0
    while len(queue)!=0:
        a,b=queue.popleft()
        for c,d in ((1,0),(0,1),(-1,0),(0,-1)):
            X,Y=a+c,b+d
            if A[X][Y]=="." and color[X][Y]=="white":
                color[X][Y]="gray"
                D[X][Y]=D[a][b]+1
                cnt=max(cnt,D[X][Y])
                queue.append([X,Y])
        color[a][b]="black"

    return cnt


h,w=map(int,input().split())
A=[["#"]+list(input())+["#"] for _ in range(h)]
A.insert(0,["#"]*(w+2))
A.append(["#"]*(w+2))
print(BFS())

Submission status: Accepted

Solution code:
import numpy as np
h,w=map(int,input().split())
maze = []
for i in range(h):
  maze.append([0 if x=="#" else float('INF') for x in list(input())])
maze = np.array(maze)

for i in range(1,h):
  maze[i,:] = np.minimum(maze[i,:],maze[i-1,:]+1)
for j in range(h-2,-1,-1):
  maze[j,:] = np.minimum(maze[j,:],maze[j+1,:]+1)
for k in range(1,w):
  maze[:,k] = np.minimum(maze[:,k],maze[:,k-1]+1)
for l in range(w-2,-1,-1):
  maze[:,l] = np.minimum(maze[:,l],maze[:,l+1]+1)


print(int(np.max(maze)))

Submission status: Accepted

Solution code:
DX = [0,0,-1,1]
DY = [-1,1,0,0]

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

# 番兵法 (#を外周に設置する)
visited = [[True] * (W + 2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True] * (W + 2))

# #の位置をqに格納
q = []
for i in range(1,H+1):
    for j in range(1,W+1):
        if visited[i][j]:
            q.append((i,j))

# dx,dyを使用せずにBFS 
# 定数倍改善
ans = 0
while q:
    qq = []

    # 新たに#となった地点をqqに格納
    for y,x in q:
        for dy,dx in zip(DY,DX):
            if not visited[y+dy][x+dx]:
                visited[y+dy][x+dx] = True
                qq.append((y+dy,x+dx))

    if not qq:
        break
    
    ans += 1
    q = qq

print(ans)

Submission status: Accepted

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

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

    # 番兵法 (#を外周に設置する)
    visited = [[True]*(W+2)]
    visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
    visited.append([True]*(W+2))

    # #の位置をqに格納
    q = []
    for i in range(1,H+1):
        for j in range(1,W+1):
            if visited[i][j]:
                q.append((i,j))

    # dx,dyを使用せずにBFS 
    # 定数倍改善
    ans = -1
    while q:
        qq = []
        # 新たに#となった地点をqqに格納
        for x,y in q:
            if not visited[x-1][y]:
                visited[x-1][y] = True
                qq.append((x-1,y))
            if not visited[x+1][y]:
                visited[x+1][y] = True
                qq.append((x+1,y))
            if not visited[x][y-1]:
                visited[x][y-1] = True
                qq.append((x,y-1))
            if not visited[x][y+1]:
                visited[x][y+1] = True
                qq.append((x,y+1))
        q = qq
        ans += 1
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

r, c = list(map(int, input().split()))
sy, sx = [0, 0]
gy, gx = [r-1, c-1]

s = [list(map(str, list(input()))) for i in range(r)]

N = r*c
G = [[] for _ in range(N)]
dist = [-1]*N
que = deque()
for i in range(r):
    for j in range(c):
        if s[i][j] == '#':
            que.append(i*c+j)
            dist[i*c+j] = 0


while que:
    v = que.popleft()
    d = dist[v]
    for x, y in ([0, 1], [0, -1], [1, 0], [-1, 0]):
        if 0 <= v//c+y <= r-1 and 0 <= (v % c)+x <= c-1:
            w = v+y*c+x
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            que.append(w)

ans = max(dist)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,w = [int(x) for x in input().split()]
meiro = [list(input()) for _ in range(h)]
ans = [[float("INF")]*w for _ in range(h)]
mina=-1
for i in range(h):
    for j in range(w):
        if meiro[i][j]=="#":
            ans[i][j]=0
        else:
            if j!=0:
                ans[i][j]=min(ans[i][j-1]+1,ans[i][j])
for i in range(h):
    for j in range(w-1,-1,-1):
        if meiro[i][j]=="#":
            ans[i][j]=0
        else:
            if j!=w-1:
                ans[i][j]=min(ans[i][j+1]+1,ans[i][j])
for j in range(w):
    for i in range(h):
        if meiro[i][j]=="#":
            ans[i][j]=0
        else:
            if i!=0:
                ans[i][j]=min(ans[i-1][j]+1,ans[i][j])
for j in range(w):
    for i in range(h-1,-1,-1):
        if meiro[i][j]=="#":
            ans[i][j]=0
        else:
            if i!=h-1:
                ans[i][j]=min(ans[i+1][j]+1,ans[i][j])
for i in range(h):
    for j in range(w):
        mina = max(mina,ans[i][j])
print(mina)

Submission status: Accepted

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

    used = [True]*(h*w)

    p = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                p.append(i*w+j)
                used[i*w+j] = False


    
    res = 0
    while p:
        tank = []
        for e in p:
            if e>w-1 and used[e-w]:
                tank.append(e-w)
                used[e-w] = False
            if e%w > 0 and used[e-1]:
                tank.append(e-1)
                used[e-1] = False
            if e<(h-1)*w and used[e+w]:
                tank.append(e+w)
                used[e+w] = False
            if e%w<w-1 and used[e+1]:
                tank.append(e+1)
                used[e+1] =  False
        p = tank
        res += 1
    print(res-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
A = [input().strip() for _ in range(H)]
B = [[-1 for j in range(W)] for i in range(H)]
que = deque([])
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            B[i][j] = 0
            que.append((i,j,0))
bmax = 0
while que:
    i,j,d = que.popleft()
    bmax = max(bmax,d)
    if j+1<W and B[i][j+1]<0:
        B[i][j+1] = d+1
        que.append((i,j+1,d+1))
    if i-1>=0 and B[i-1][j]<0:
        B[i-1][j] = d+1
        que.append((i-1,j,d+1))
    if j-1>=0 and B[i][j-1]<0:
        B[i][j-1] = d+1
        que.append((i,j-1,d+1))
    if i+1<H and B[i+1][j]<0:
        B[i+1][j] = d+1
        que.append((i+1,j,d+1))
print(bmax)

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

    H, W = map(int, input().split())
    edge = ['#'] * (W + 2)
    field = [edge]
    q = deque()

    for i in range(H):
        line = input()
        field.append(['#'] + list(line) + ['#'])
        for j in range(W):
            if line[j] == '#':
                q.append((i + 1, j + 1, 0))
    field.append(edge)
    res = 0

    while q:
        y, x, lv = q.popleft()
        if lv > res:
            res = lv

        if field[y + 1][x] == '.':
            field[y + 1][x] = '#'
            q.append((y + 1, x, lv + 1))

        if field[y - 1][x] == '.':
            field[y - 1][x] = '#'
            q.append((y - 1, x, lv + 1))

        if field[y][x + 1] == '.':
            field[y][x + 1] = '#'
            q.append((y, x + 1, lv + 1))

        if field[y][x - 1] == '.':
            field[y][x - 1] = '#'
            q.append((y, x - 1, lv + 1))

    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
H, W = map(int, input().split())
S = [input() for _ in range(H)]
def f():
    q = collections.deque()
    dist = [[float("inf")] * W for _ in range(H)]
    for i in range(H):
        for k in range(W):
            if S[i][k] == '#':
                q.append((i,k))
                dist[i][k] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if dist[h2][w2] == float("inf"):
                    dist[h2][w2] = d+1
                    q.append((h2, w2))
    return dist
ans = 0
dist = f()
for i in range(H):
    for k in range(W):
        ans = max(ans,dist[i][k])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
Black = deque([])
Black_grid = [[-1 for _ in range(w)] for _ in range(h)]

for i in range(h):
    a = str(input())
    for j in range(w):
        if a[j] == '#':
            Black.append([j,i])
            Black_grid[i][j] = 0

Move = [[-1,0],[1,0],[0,-1],[0,1]]

while Black:
    now = Black.popleft()
    x = now[0]
    y = now[1]
    for move in Move:
        x_next = x + move[0]
        y_next = y + move[1]
        if x_next < 0 or x_next >= w or y_next < 0 or y_next >= h:
            continue
        elif Black_grid[y_next][x_next] >= 0:
            continue
        else:
            Black.append([x_next, y_next])
            Black_grid[y_next][x_next] = Black_grid[y][x] + 1

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

Submission status: Accepted

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

#上下左右のマスを黒くしていく
#BFS
from collections import deque
def bfs():
    dx=[0,1,0,-1]
    dy=[1,0,-1,0]
    log=[[-1]*w for i in range(h)]

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

    while que:
        #queの先頭を取り出す
        p=que.popleft()
        for i in range(4):
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]

            if not(0<=nx<h and 0<=ny<w):continue
            if log[nx][ny]!=-1:continue
            que.append((nx,ny))
            log[nx][ny]=log[p[0]][p[1]]+1

    return log

G=bfs()
ans=0
for i in range(h):
    for j in range(w):
        if ans<G[i][j]:
            ans=G[i][j]
print(ans)
#print(*G,sep='\n')

Submission status: Accepted

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

#上下左右のマスを黒くしていく
#BFS
from collections import deque
def bfs():
    dx=[0,1,0,-1]
    dy=[1,0,-1,0]
    log=[[0]*w for i in range(h)]

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

    while que:
        #queの先頭を取り出す
        p=que.popleft()
        for i in range(4):
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]

            if not(0<=nx<h and 0<=ny<w):continue
            if a[nx][ny]=='#':continue
            que.append((nx,ny))
            log[nx][ny]=log[p[0]][p[1]]+1
            a[nx][ny]='#'

    return log

G=bfs()
ans=0
for i in range(h):
    for j in range(w):
        if ans<G[i][j]:
            ans=G[i][j]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

dyx = [(0, 1), (0, -1), (1, 0), (-1, 0)]
H, W = map(int, input().split())
edge = ['#']*(W+2)
field = [edge]
q = deque()

for i in range(H):
    field.append(['#'] + list(input()) + ['#'])
    for j in range(W):
        if field[i+1][j+1] == '#':
            q.append((i+1, j+1, 0))
field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()
    res = max(lv, res)

    for dy, dx in dyx:
        if field[y+dy][x+dx] == '.':
            field[y+dy][x+dx] = '#'
            q.append((y+dy, x+dx, lv+1))

print(res)

Submission status: Accepted

Solution code:
def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        a = input()
        A.append(a)
    bl = []
    wl = set()
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                bl.append((i, j))
            else:
                wl.add((i, j))
    r = 0
    while wl:
        bln = []
        for i in bl:
            if (i[0] + 1, i[1]) in wl:
                wl.remove((i[0] + 1, i[1]))
                bln.append((i[0] + 1, i[1]))
            if (i[0] - 1, i[1]) in wl:
                wl.remove((i[0] - 1, i[1]))
                bln.append((i[0] - 1, i[1]))
            if (i[0], i[1] + 1) in wl:
                wl.remove((i[0], i[1] + 1))
                bln.append((i[0], i[1] + 1))
            if (i[0], i[1] - 1) in wl:
                wl.remove((i[0], i[1] - 1))
                bln.append((i[0], i[1] - 1))
        bl = bln
        r += 1
    return r
print(main())

Submission status: Accepted

Solution code:
def main():
    H, W = list(map(int, input().split()))
    A = [[i for i in input()] for _ in range(H)]
    cur = []
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                cur.append((h, w))
    r = 0
    while cur:
        nxt = []
        for ch, cw in cur:
            for x, y in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
                nh, nw = ch + x, cw + y
                if 0 <= nh < H and 0 <= nw < W and A[nh][nw] == '.':
                    A[nh][nw] = '#'
                    nxt.append((nh, nw))
        cur = nxt
        r += 1
    return r - 1

print(main())

Submission status: Accepted

Solution code:
def main():
  num_r,num_c = map(int,input().split())
  field = [input() for i in range(num_r)]
  q = []
  seen = [0]*(num_c*num_r)
  count = 0
 
  for i in range(num_r):
    for j in range(num_c):
      if field[i][j] == "#":
        seen[i*num_c+j] = 1
        q.append([i,j])
      
  while q:
    tank = []
    for i in q:
      r = i[0]
      c = i[1]
      if (0<=r-1) and (seen[(r-1)*num_c+c] == 0):
        tank.append([r-1,c])
        seen[(r-1)*num_c+c] = 1
      if (r+1<num_r) and (seen[(r+1)*num_c+c] == 0):
        tank.append([r+1,c])
        seen[(r+1)*num_c+c] = 1
      if (0<=c-1) and (seen[r*num_c+(c-1)] == 0):
        tank.append([r,c-1])
        seen[r*num_c+(c-1)] = 1
      if (c+1<num_c) and (seen[r*num_c+(c+1)] == 0):
        tank.append([r,c+1])
        seen[r*num_c+(c+1)] = 1
 
    count = count + 1
    q = tank
 
  print(count-1)
  
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    h,w = map(int,input().split())
    a = []
    for i in range(h):
        a.append(input())
 
    used = [True]*(h*w)
 
    p = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                p.append(i*w+j)
                used[i*w+j] = False
 
 
    
    res = 0
    while p:
        tank = []
        for e in p:
            if (e-w)>=0 and used[e-w]:
                tank.append(e-w)
                used[e-w] = False
            if e%w-1 >= 0 and used[e-1]:
                tank.append(e-1)
                used[e-1] = False
            if e+w<w*h and used[e+w]:
                tank.append(e+w)
                used[e+w] = False
            if e%w+1<w and used[e+1]:
                tank.append(e+1)
                used[e+1] =  False
        p = tank
        res += 1
    print(res-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    h,w = map(int,input().split())
    a = []
    for i in range(h):
        a.append(input())
 
    used = [True]*(h*w)
 
    p = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                p.append(i*w+j)
                used[i*w+j] = False
 
 
    
    res = 0
    while p:
        tank = []
        for e in p:
            if e>w-1 and used[e-w]:
                tank.append(e-w)
                used[e-w] = False
            if e%w > 0 and used[e-1]:
                tank.append(e-1)
                used[e-1] = False
            if e<(h-1)*w and used[e+w]:
                tank.append(e+w)
                used[e+w] = False
            if e%w<w-1 and used[e+1]:
                tank.append(e+1)
                used[e+1] =  False
        p = tank
        res += 1
    print(res-1)
 
if __name__ == '__main__':
    main()

Submission status: Accepted

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

    used = [True]*(h*w)

    p = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                p.append(i*w+j)
                used[i*w+j] = False


    
    res = 0
    while p:
        tank = []
        for e in p:
            if e>w-1 and used[e-w]:
                tank.append(e-w)
                used[e-w] = False
            if e%w > 0 and used[e-1]:
                tank.append(e-1)
                used[e-1] = False
            if e<(h-1)*w and used[e+w]:
                tank.append(e+w)
                used[e+w] = False
            if e%w<w-1 and used[e+1]:
                tank.append(e+1)
                used[e+1] =  False
        p = tank
        res += 1
    print(res-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

while len(q) != 0:
    ans += 1
    qq = []
    while len(q) != 0:
        t = q.popleft()
        i,j = t[0],t[1]
        if i > 0 and A[i-1][j] == '.':
            qq.append((i-1,j))
            A[i-1][j] = '#'
        if j > 0 and A[i][j-1] == '.':
            qq.append((i,j-1))
            A[i][j-1] = '#'
        if i < H-1 and A[i+1][j] == '.':
            qq.append((i+1,j))
            A[i+1][j] = '#'
        if j < W-1 and A[i][j+1] == '.':
            qq.append((i,j+1))
            A[i][j+1] = '#'
    q = deque(qq)

print(ans)

Submission status: Accepted

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

has_visited = [[True]*(W+2)]
has_visited += [[True] + [m == "#" for m in input().rstrip()] + [True] for _ in range(H)]
has_visited += [[True]*(W+2)]

search_que = []
for y in range(1, H+1):
    for x in range(1, W+1):
        if has_visited[y][x]:
            search_que.append((y, x))

count = -1
while search_que:
    count += 1
    next_que = []
    for y, x in search_que:
        if not has_visited[y+1][x]:
            has_visited[y+1][x] = True
            next_que.append((y+1, x))
        if not has_visited[y-1][x]:
            has_visited[y-1][x] = True
            next_que.append((y-1, x))
        if not has_visited[y][x+1]:
            has_visited[y][x+1] = True
            next_que.append((y, x+1))
        if not has_visited[y][x-1]:
            has_visited[y][x-1] = True
            next_que.append((y, x-1))
    search_que = next_que

print(count)

Submission status: Accepted

Solution code:
import copy
from collections import deque

####入力
H,W = map(int,input().split())

#gridの定義
grid = []
for i in range(H):
  S = input()
  grid.append( [S[i] for i in range(W) ])
####入力終了

#distの設定
dist = [[0 for i in range(W)] for j in range(H)]

#l_blackの設定
l_black = deque([])
for i in range(H):
  for j in range(W):
    if grid[i][j] == "#":
      l_black.append( [i,j] ) # [行,列]

#探索
max_d = 0

while len(l_black) > 0:
  #vは黒マスの座標 
  while len(l_black) > 0:
    v = l_black.popleft()
    #iはvの上下左右のマスの座標[行,列]
    for i in [ [v[0]+1,v[1]] , [v[0],v[1]+1] , [v[0]-1,v[1]] ,[v[0],v[1]-1] ]:
      #場外アウトの場合はスルー
      if (i[1]<0 or i[0] <0 or i[0]>=H or i[1] >= W ):
        continue
      #移動先がもう黒マスの場合スルー
      if grid[i[0]][i[1]] == "#":
        continue
      #移動先が白マスならばそこの座標を黒マスにして距離を記録する
      if grid[i[0]][i[1]] == ".":
        #黒マスにする
        grid[i[0]][i[1]] = "#"
        #新たに黒鱒となった座標をl_blackに追加
        l_black.append(i)
        #距離の記録
        dist[i[0]][i[1]] = dist[v[0]][v[1]] + 1
        max_d = max(max_d,dist[i[0]][i[1]])
print(max_d)

Submission status: Accepted

Solution code:
from collections import deque

h,w = [int(x) for x in input().split()]
m = []
for _ in range(h):
    m.append(list(input()))

q = deque()
d = [[-1]*w for x in range(h)]

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

aa = 0
while q:
    v = q.popleft()
    for i in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny = v[0] + i[0]
        nx = v[1] + i[1]
        if (0<=ny<h and 0<=nx<w and m[ny][nx] == "."):
            m[ny][nx] = "#"
            q.append([ny,nx])
            d[ny][nx] = d[v[0]][v[1]] + 1
            aa = max(aa,d[ny][nx])

######
print(aa)

Submission status: Accepted

Solution code:
from collections import deque

H,W = map(int,input().split())
c =[]
c.append(['×' for _ in range(W+2)])
ans = []
ans.append([0 for _ in range(W+2)])
q = deque()
for i in range(H):
    tmp = list('×'+input()+'×')
    ans_tmp = []
    for j in range(W+2):
        if tmp[j] == '#':
            ans_tmp.append(0)
            q.append([j,i+1])
        elif tmp[j] == '×':
            ans_tmp.append(0)
        else:
            ans_tmp.append(10**4)
    c.append(tmp)
    ans.append(ans_tmp)

c.append(['×' for _ in range(W+2)])
ans.append([0 for _ in range(W+2)])


def bfs(q):
    while q:
        x,y = q.popleft()
        if c[y][x-1] == '.':
            q.append([x-1,y])
            ans[y][x-1] = ans[y][x] + 1
            c[y][x-1] = '#'
        if c[y][x+1] == '.':
            q.append([x+1,y])
            ans[y][x+1] = ans[y][x] + 1
            c[y][x+1] = '#'
        if c[y-1][x] == '.':
            q.append([x,y-1])
            ans[y-1][x] = ans[y][x] + 1
            c[y-1][x] = '#'
        if c[y+1][x] == '.':
            q.append([x,y+1])
            ans[y+1][x] = ans[y][x] + 1
            c[y+1][x] = '#'

bfs(q)
max_ans = 0
for i in range(H+2):
    #print(ans[i])
    max_ans = max(max_ans,max(ans[i]))

print(max_ans)

Submission status: Accepted

Solution code:
from subprocess import call
call (('pypy3', '-c', """
from collections import deque

H,W = map(int,input().split())
c =[]
c.append(['×' for _ in range(W+2)])
ans = []
ans.append([0 for _ in range(W+2)])
q = deque()
for i in range(H):
    tmp = list('×'+input()+'×')
    ans_tmp = []
    for j in range(W+2):
        if tmp[j] == '#':
            ans_tmp.append(0)
            q.append([j,i+1])
        elif tmp[j] == '×':
            ans_tmp.append(0)
        else:
            ans_tmp.append(10**4)
    c.append(tmp)
    ans.append(ans_tmp)

c.append(['×' for _ in range(W+2)])
ans.append([0 for _ in range(W+2)])


def bfs(q):
    while q:
        x,y = q.popleft()
        if c[y][x-1] == '.':
            q.append([x-1,y])
            ans[y][x-1] = ans[y][x] + 1
            c[y][x-1] = '#'
        if c[y][x+1] == '.':
            q.append([x+1,y])
            ans[y][x+1] = ans[y][x] + 1
            c[y][x+1] = '#'
        if c[y-1][x] == '.':
            q.append([x,y-1])
            ans[y-1][x] = ans[y][x] + 1
            c[y-1][x] = '#'
        if c[y+1][x] == '.':
            q.append([x,y+1])
            ans[y+1][x] = ans[y][x] + 1
            c[y+1][x] = '#'

bfs(q)
max_ans = 0
for i in range(H+2):
    #print(ans[i])
    max_ans = max(max_ans,max(ans[i]))

print(max_ans)
"""))

Submission status: Accepted

Solution code:
from scipy.ndimage import distance_transform_cdt
H,W = map(int,input().split())
S = list(list(input()) for h in range(H))
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            S[h][w] = 0
        else:
            S[h][w] = 1
print(distance_transform_cdt(S, metric='taxicab').max())