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:
from collections import deque

h,w = map(int,input().split())
matrix = [["a" for _ in range(w+2)]] + [list("a" + input() + "a") for _ in range(h)] + [["a" for _ in range(w+2)]]

matrix_list1 = deque()
cnt = 0

#黒いタイルの位置情報を確認
for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j] == "#":
            matrix_list1.append([i,j])

#白いタイルが無くなるまで、黒いタイルを増やす
while len(matrix_list1) != 0:     
    for _ in range(len(matrix_list1)):
        x,y = matrix_list1.popleft()
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "#"
            matrix_list1.append([x+1,y])
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "#"
            matrix_list1.append([x-1,y])
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "#"
            matrix_list1.append([x,y+1])
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "#"
            matrix_list1.append([x,y-1])
    else:
        if len(matrix_list1) > 0:
            cnt += 1
    
print(cnt)

Submission status: Accepted

Solution code:
import sys
from collections import deque
H,W=map(int,input().split())
A=[[c for c in l.strip()] for l in sys.stdin]
maze=[[3000]*W for i in range(H)]
q=deque([])
start=[]
dy=[1,0,-1,0]
dx=[0,1,0,-1]
for i in range(H):
  for j in range(W):
    if(A[i][j]=="#"):
      q.append((i,j))
#print(start)
x=0
y=maze[:]

for i in q:
  maze[i[0]][i[1]]=0
while(q):
  c=q.popleft()
  for j in range(4):
    if(c[0]+dy[j]>=0 and c[0]+dy[j]<H and c[1]+dx[j]>=0 and c[1]+dx[j]<W):
      if(maze[c[0]+dy[j]][c[1]+dx[j]]==3000 and A[c[0]+dy[j]][c[1]+dx[j]]=="."):
        q.append((c[0]+dy[j],c[1]+dx[j]))
        maze[c[0]+dy[j]][c[1]+dx[j]]=maze[c[0]][c[1]]+1
        
        x=max(x,maze[c[0]+dy[j]][c[1]+dx[j]])
print(x)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [input() for _ in range(h)]
memo = [[-1 if j=="." else 0 for j in list(i)] for i in a]

q = []
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            q.append([i, j])
q = deque(q)
while q:
    x, y = q.popleft()
    for s, t in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=x+s and 0<=y+t and x+s<h and y+t<w:
            if memo[x+s][y+t]<0:
                memo[x+s][y+t]=memo[x][y]+1
                q.append([x+s,y+t])
print(max(max(i) for i in memo))

Submission status: Accepted

Solution code:
from collections import deque

def penetrate(x, y, count):
    global max_idx
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < h and 0 <= ny < w and A[nx][ny] == "." and d[nx][ny] == -1:
            d[nx][ny] = count + 1
            q.append((nx, ny, d[nx][ny]))
            max_idx = max(max_idx, d[nx][ny])


h, w = map(int, input().split())
d = [[-1] * w for _ in range(h)]

A = [[] for i in range(h)]
q = deque()

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

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
max_idx = 0

while len(q) > 0:
    idx = q.popleft()
    penetrate(idx[0], idx[1], idx[2])

print(max_idx)

Submission status: Accepted

Solution code:
from collections import deque 
import sys
input = sys.stdin.readline
q = deque([])
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
x=[[-1,0],[1,0],[0,-1],[0,1]]
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            for k in x:
                if 0<=i+k[0]<h and 0<=j+k[1]<w and a[i+k[0]][j+k[1]]==".":
                    a[i+k[0]][j+k[1]]="0"
                    q.append([i+k[0],j+k[1],1])
ans=0
while q:
    v=q.popleft()
    for k in x:
        if 0<=v[0]+k[0]<h and 0<=v[1]+k[1]<w and a[v[0]+k[0]][v[1]+k[1]]==".":
            a[v[0]+k[0]][v[1]+k[1]]="0"
            q.append([v[0]+k[0],v[1]+k[1],v[2]+1])
            ans=v[2]+1
print(ans)

Submission status: Accepted

Solution code:

import numpy as np
h,w = list(map(int,input().split()))
S = [[x for x in input()] for _ in range(h)]

s = np.zeros((h,w), dtype='int')
for i in range(h):
  for j in range(w):
    if S[i][j] == '.':
      s[i,j] = h*w

def rev():
  for i in range(1,h):
    s[i,:] = np.minimum(s[i,:], s[i-1,:]+1)
  for i in range(h-1)[::-1]:
    s[i,:] = np.minimum(s[i,:], s[i+1,:]+1)
  for i in range(1,w):
    s[:,i] = np.minimum(s[:,i], s[:,i-1]+1)
  for i in range(w-1)[::-1]:
    s[:,i] = np.minimum(s[:,i], s[:,i+1]+1)

rev()
print(np.max(s))

Submission status: Accepted

Solution code:
from collections import deque

Height, Width = map(int, input().split())
Map = [input() for _ in range(Height)]
min_step_map = [[10**6]*Width for _ in range(Height)]
research_point = deque()

# Find the minimum number of steps from all blacks.
# The maximum number of the obtained minimum steps is the answer.
def search_min_step():
    while len(research_point) > 0:
        y_now, x_now = research_point.popleft()
        
        for dy, dx in [(-1,0), (0,-1), (1,0), (0,1)]:
            y_next, x_next = y_now+dy, x_now+dx
            if (y_next <= -1 or Height <= y_next) or \
                                              (x_next <= -1 or Width <= x_next):
                continue
            
            if Map[y_next][x_next] == '#' or \
                 min_step_map[y_next][x_next] <= min_step_map[y_now][x_now] + 1:
                continue
            else:
                min_step_map[y_next][x_next] = min_step_map[y_now][x_now] + 1
                research_point.append([y_next, x_next])

for y in range(Height):
    for x in range(Width):
        if Map[y][x] == '#':
            min_step_map[y][x] = 0
            research_point.append([y, x])

search_min_step()

max_step = 0
for y in range(Height):
    max_step = max(max_step, max(min_step_map[y]))

print(max_step)

Submission status: Accepted

Solution code:

from collections import deque

H, W = map(int, input().split())
A = [input() for i in range(H)]
breadth = [[-1] * W for i in range(H)]
queue = deque()

for h in range(H):
    for w in range(W):
        if A[h][w] == "#":
            breadth[h][w] = 0
            queue.append([h, w])


def search(A, breadth):
    d = 0
    while queue:
        y, x = queue.popleft()
        d = breadth[y][x]
        for i, j in [-1, 0], [1, 0], [0, -1], [0, 1]:
            newy, newx = y + i, x + j
            if newy < 0 or newx < 0 or newy >= H or newx >= W:
                continue
            if breadth[newy][newx] == -1:
                breadth[newy][newx] = d + 1
                queue.append([newy, newx])

    return d


print(search(A, breadth))

Submission status: Accepted

Solution code:
from collections import deque

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

a = [[False] * (w + 2)]
for y in range(h):
    a.append([False] + [x != '#' for x in input()] + [False])
a.append([False] * (w + 2))

s = deque()
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if not a[i][j]:
            s.append((i, j))

ans = -1
while s:
    ns = deque()
    for i, j in s:
        if a[i - 1][j]:
            a[i - 1][j] = False
            ns.append((i - 1, j))
        if a[i + 1][j]:
            a[i + 1][j] = False
            ns.append((i + 1, j))
        if a[i][j - 1]:
            a[i][j - 1] = False
            ns.append((i, j - 1))
        if a[i][j + 1]:
            a[i][j + 1] = False
            ns.append((i, j + 1))

    s = ns
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def main():
    height, width = map(int, input().split())
    grid = []
    q = deque([])
    change_time = [[float("inf") for _ in range(width)] for _ in range(height)]
    for i in range(height):
        now = list(input())
        for j in range(width):
            if now[j] == "#":
                q.append([i, j, 0])
                change_time[i][j] = 0
        grid.append(now)
    d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    answer = 0
    while q:
        y, x, time = q.popleft()
        for dy, dx in d:
            new_y = y + dy
            new_x = x + dx
            if 0 <= new_y < height and 0 <= new_x < width and grid[new_y][new_x] == ".":
                grid[new_y][new_x] = "#"
                change_time[new_y][new_x] = change_time[y][x] + 1
                q.append([new_y, new_x, change_time[new_y][new_x]])
                answer = max(answer, change_time[new_y][new_x])
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
from sys import stdin


def main():
    height, width = map(int, stdin.readline().split())
    q = deque([])
    grid = [list(stdin.readline()) for _ in range(height)]
    distance = [[-1 for _ in range(width)] for _ in range(height)]
    for i in range(height):
        for j in range(width):
            if grid[i][j] == "#":
                q.append((i, j))
                distance[i][j] = 0
    answer = 0
    delta = ((0, 1), (1, 0), (0, -1), (-1, 0))
    while q:
        y, x = q.popleft()
        answer = distance[y][x]
        for dy, dx in delta:
            new_y = y + dy
            new_x = x + dx
            if 0 <= new_y < height and 0 <= new_x < width and grid[new_y][new_x] == ".":
                distance[new_y][new_x] = answer + 1
                grid[new_y][new_x] = "#"
                q.append((new_y, new_x))
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
from sys import stdin


def main():
    height, width = map(int, stdin.readline().split())
    q = deque([])
    grid = [stdin.readline() for _ in range(height)]
    distance = [[-1 for _ in range(width)] for _ in range(height)]
    for i in range(height):
        for j in range(width):
            if grid[i][j] == "#":
                q.append((i, j))
                distance[i][j] = 0
    answer = 0
    delta = ((0, 1), (1, 0), (0, -1), (-1, 0))
    while q:
        y, x = q.popleft()
        answer = distance[y][x]
        for dy, dx in delta:
            new_y = y + dy
            new_x = x + dx
            if 0 <= new_y < height and 0 <= new_x < width and distance[new_y][new_x] < 0:
                distance[new_y][new_x] = answer + 1
                q.append((new_y, new_x))
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

h, w = map(int, readline().split())
a = [input() for i in range(h)]
q = []
dist = [[False] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            q.append((i, j))
            dist[i][j] = True
test = [(0, 1), (0, -1), (1, 0), (-1, 0)]
cnt = -1
while q:
    cnt += 1
    qq = []
    for y, x in q:
        for dy, dx in test:
            yy, xx = y + dy, x + dx
            if xx < 0 or yy < 0 or xx > w - 1 or yy > h - 1 or dist[yy][xx]:
                continue
            else:
                dist[yy][xx] = True
                qq.append((yy, xx))
    q = qq
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np

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-1,:]+1,maze[i,:])
for i in range(H-2,-1,-1):
  maze[i,:]=np.minimum(maze[i+1,:]+1,maze[i,:])
for i in range(1,W):
  maze[:,i]=np.minimum(maze[:,i-1]+1,maze[:,i])
for i in range(W-2,-1,-1):
  maze[:,i]=np.minimum(maze[:,i+1]+1,maze[:,i])
  
print(int(np.max(maze)))

Submission status: Accepted

Solution code:
from collections import deque


def solve():
    H, W = map(int, input().split())
    m = [[-1]*W for _ in range(H)]
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    q = deque([])

    for i in range(H):
        s = input()
        for j in range(W):
            if s[j]=="#":
                q.append((i, j))
                m[i][j] = 0
    
    while q:
        y, x = q.popleft()
        for px, py in zip(dx, dy):
            x1, y1 = x + px, y + py
            if not (0<=x1<W and 0<=y1<H):
                continue
            if m[y1][x1] == -1:
                q.append((y1, x1))
                m[y1][x1] = m[y][x] + 1

    print(max(map(max, m)))


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import deque


def solve():
    H, W = map(int, input().split())
    m = [[-1]*W for _ in range(H)]
    l = [list(input()) for _ in range(H)]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    q = deque([])

    for i in range(H):
        for j in range(W):
            if l[i][j]=="#":
                q.append((i, j))
                m[i][j] = 0
    
    while q:
        y, x = q.popleft()

        for px, py in zip(dx, dy):
            x1, y1 = x + px, y + py
            if not (0<=x1<W and 0<=y1<H):
                continue
            if m[y1][x1] == -1:
                q.append((y1, x1))
                m[y1][x1] = m[y][x] + 1

    print(max(map(max, m)))


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import collections

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

dy = [1,0,-1,0]
dx = [0,1,0,-1]

def f(y,x):
    for i in range(4):
        newy = y + dy[i]
        newx = x + dx[i]
        if 0 <= newy and newy < h and 0 <= newx and newx < w:
            if tizu[newy][newx] == ".":
                q.append((newy,newx))
                tizu[newy][newx] = "#"
            
q = collections.deque()
for i in range(h): 
    for k in range(w):
        if tizu[i][k] == "#":
            q.append((i,k))
ans = 0
while True:
    l = len(q)
    if l == 0:
        print(ans-1)
        exit()
    for i in range(l):
        yx = q.popleft()
        f(yx[0],yx[1])
    ans += 1

Submission status: Accepted

Solution code:
#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    
    H,W = LMIIS()
    A = []
    for _ in range(H):
        A.append(input())
    from copy import deepcopy
    blacks = deque()
    visited = [[False]*W for _ in range(H)]
    for w in range(W):
        for h in range(H):
            if A[h][w] == '#':
                blacks.append((h,w))
                visited[h][w] = True

    count = -1
    
    while len(blacks) > 0:
        count += 1
        next_blacks = deque()
        while len(blacks) > 0:
            i,j = blacks.pop()
            if 0 <= i-1 and not visited[i-1][j]:
                next_blacks.append((i-1,j))
                visited[i-1][j] = True
            if 0 <= j-1 and not visited[i][j-1]:
                next_blacks.append((i,j-1))
                visited[i][j-1] = True
            if i+1 < H and not visited[i+1][j]:
                next_blacks.append((i+1,j))
                visited[i+1][j] = True
            if j+1 < W and not visited[i][j+1]:
                next_blacks.append((i,j+1))
                visited[i][j+1] = True
        blacks = next_blacks
    print(count)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
from collections import deque
# import queue


def resolve():
    # ★get input
    h, w = map(int, input().split())

    # ★exec
    # BFSにて最短経路を求める
    # 準備
    distance = [[-1 for i in range(w)] for j in range(h)]
    que = deque()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        line = list(input())
        for j in range(w):
            if line[j] == "#":
                que.append((i, j))
                distance[i][j] = 0

    # BFS開始
    while len(que) > 0:

        # now = que.get()
        now = que.popleft()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            target = (now[0] + move_y, now[1] + move_x)
            if not (h > target[0] >= 0 and w > target[1] >= 0):
                continue

            # 距離が設定済みなら何もしない
            if not distance[target[0]][target[1]] == -1:
                continue

            # キューに追加
            # que.put(target)
            que.append(target)
            # 最短距離を設定
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

    # 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)



class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 3
...
.#.
..."""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """6 6
..#..#
......
#..#..
......
.#....
....#."""
        output = """3"""
        self.assertIO(input, output)

if __name__ == "__main__":
    #unittest.main()
    resolve()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
H,W=map(int,input().split())
A=[input() for i in range(H)]
b=[]
l=[[0]*W for i in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            l[i][j]=1
            b.append((i,j))
c=0
while 1:
    a=[]
    for i in b:
        if i[0]>0 and not l[i[0]-1][i[1]]:
            a.append((i[0]-1,i[1]))
            l[i[0]-1][i[1]]=1
        if i[1]>0 and not l[i[0]][i[1]-1]:
            a.append((i[0],i[1]-1))
            l[i[0]][i[1]-1]=1
        if i[0]<H-1 and not l[i[0]+1][i[1]]:
            a.append((i[0]+1,i[1]))
            l[i[0]+1][i[1]]=1
        if i[1]<W-1 and not l[i[0]][i[1]+1]:
            a.append((i[0],i[1]+1))
            l[i[0]][i[1]+1]=1
    if not a:
        break
    b=a
    c+=1
print(c)

Submission status: Accepted

Solution code:
from collections import deque

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

visited = [ [0]*w for _ in range(h) ]
q = deque()

for j in range(h):
    for i in range(w):
        a = field[j][i]
        if a=="#":
            q.append([j,i,0])
            visited[j][i] = 1
        else:
            pass

m = 0
while q:
    y,x,d = q.popleft()
    for j,i in ([1,0],[0,-1],[-1,0],[0,1]):
        ny = y + j
        nx = x + i
        if ny==-1 or nx==-1 or ny==h or nx==w:
            pass
        elif visited[ny][nx]==0:
            visited[ny][nx] = 1
            q.append([ny,nx,d+1])
            m = max(m,d+1)   
print(m)

Submission status: Accepted

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

from collections import deque

v=[[0]*w for i in range(h)]
m=[[-1,0],[0,-1],[1,0],[0,1]]
que=deque([])
for i in range(h):
    for  j in range(w):
        if a[i][j]=='#':
            v[i][j]=1
            que.append([i,j,0])
            #print(que)

while len(que)>0:
    n=que.popleft()
    for i in m:
        ni,nj=i[0]+n[0],i[1]+n[1]
        if ni>=0 and nj>=0 and ni<h and nj<w:
            if v[ni][nj]==0:
                v[ni][nj]=1
                que.append([ni,nj,n[2]+1])
print(n[2])

Submission status: Accepted

Solution code:
import numpy as np

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(1,W):
	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(W-2,-1,-1):
	maze[:,i]=np.minimum(maze[:,i],maze[:,i+1]+1)
print(int(np.max(maze)))

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
from decimal import Decimal
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

dx = (0,1,0,-1); dy = (1,0,-1,0)
h,w = inpl()
s = []
res = [[0] * w for _ in range(h)]
q = deque()
for i in range(h):
    s.append(list(input()))
    for j in range(w):
        if s[i][j] == '#':
            q.append((i,j))
mx = 0
while q:
    ny,nx = q.popleft()
    for di in range(4):
        y = ny + dy[di]
        x = nx + dx[di]
        if 0 <= y < h and 0 <= x < w:
            if s[y][x] == '.':
                res[y][x] = res[ny][nx] + 1
                mx = max(mx, res[y][x])
                s[y][x] = '#'
                q.append((y,x))
print(mx)

Submission status: Accepted

Solution code:
def resolve():

    from collections import deque

    H, W = map(int, input().split())
    maze = [input() for i in range(H)]
    start_list=[]
    for i in range(H):
        for j in range(W):
            if maze[i][j]=='#':
                start_list.append([i,j])
    INF = 10 ** 20

    visited = [[INF] * W for j in range(H)]


    def bfs(maze):
        queue = deque()
        for [i,j] in start_list:
            queue.append([i,j])
            visited[i][j]=0
        while queue:
            y, x = queue.popleft()
            cnt=0
            for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                ny, nx = y + j, x + k
                if 0 <= ny < H and 0 <= nx < W and \
                        maze[ny][nx] == "." and visited[ny][nx]==INF:
                        visited[ny][nx] = visited[y][x] + 1
                        queue.append([ny, nx])
        return visited


    bfs(maze)
    ans=0
    for i in range(H):
        for j in range(W):
            ans=max(ans,visited[i][j])

    print(ans)


resolve()

Submission status: Accepted

Solution code:
import collections

h,w = map(int,input().split())
area = []
q = collections.deque()

for i in range(h):
    area.append(list(input()))
    ls = [(i,j,0) for j in range(w) if area[-1][j] =="#"]
    q.extend(ls)
d = [[-1,0],[0,-1],[1,0],[0,1]]
co = 0
while q:
    y,x,c = q.popleft()
    for dy,dx in d:
        if (0<=y+dy<h) and (0<=x+dx <w):
            if area[y+dy][x+dx] == ".":
                area[y+dy][x+dx] = "#"
                co = max(c+1,co)
                q.append((y+dy,x+dx,c+1))
print(co)

Submission status: Accepted

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

#dp[i][j]=最も近い黒マスまでの最小マンハッタン距離
INF=10**9
dp = [[INF] * W for _ in range(H)]

#右
for i in range(H):
    c = INF
    for j in range(W):
        if A[i][j] == '#': c = 0
        elif j>=1: c = dp[i][j-1] + 1
        dp[i][j] = min(dp[i][j], c)

#下
for j in range(W):
    c = INF
    for i in range(H):
        if A[i][j] == '#': c = 0
        elif i>=1: c = dp[i-1][j] + 1
        dp[i][j] = min(dp[i][j], c)

#左
for i in range(H):
    c = INF
    for j in range(W-1,-1,-1):
        if A[i][j] == '#': c = 0
        elif j<W-1: c = dp[i][j+1] + 1
        dp[i][j] = min(dp[i][j], c)

#上
for j in range(W):
    c = INF
    for i in range(H-1,-1,-1):
        if A[i][j] == '#': c = 0
        elif i<H-1: c = dp[i+1][j] + 1
        dp[i][j] = min(dp[i][j], c)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
dydx4 = ((-1,0),(0,-1),(0,1),(1,0))

h,w = map(int,input().split())
A = [list(input()) for i in range(h)]
dis = [[inf] * w for i in range(h)]
import heapq
def bfs(start_set):
  que = collections.deque()
  for si,sj in start_set:
    que.append((0,si,sj))
    dis[si][sj] = 0
  while que:
    cost,i,j =que.popleft()
    if dis[i][j] < cost: continue
    for di,dj in dydx4:
      ni = i + di
      nj = j + dj
      if not (0 <= ni < h and 0 <= nj < w):continue
      if A[ni][nj] == "#":continue
      # if A[ni][nj] == "#" and dis[ni][nj] == inf:
      #   dis[ni][nj] = 0
      #   heapq.heappush(que,(0,ni,nj))
      if cost + 1 < dis[ni][nj]: 
        dis[ni][nj] = cost+1
        que.append((cost+1,ni,nj))

start_set = []
for i in range(h):
  for j in range(w):
    if A[i][j] == "#":
      start_set.append((i,j))
bfs(start_set)
      
print(max(map(max,dis)))

Submission status: Accepted

Solution code:
from collections import deque

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

minDist = [[10**10] * W for _ in range(H)]
que = deque([])
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            que.append((h, w, 0))
            minDist[h][w] = 0

while que:
    h, w, d = que.popleft()

    if minDist[h][w] < d:
        continue
    minDist[h][w] = d

    for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        if 0 <= dh + h < H and 0 <= dw + w < W:
            if minDist[dh + h][dw + w] > d + 1:
                que.append((dh + h, dw + w, d + 1))
                minDist[dh + h][dw + w] = d + 1

ans = max(max(d) for d in minDist)
print(ans)

Submission status: Accepted

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

A = [str(input()) for _ in range(h)]

from collections import deque
q = deque()
visit = [[-1]*w for _ in range(h)]

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

while q:
    y, x = q.popleft()
    for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
        ny, nx = y+dy, x+dx
        if 0 <= ny <= h-1 and 0 <= nx <= w-1 and visit[ny][nx] == -1:
            visit[ny][nx] = visit[y][x]+1
            q.append((ny, nx))
#print(max(visit))
max_ = -1
for i in range(h):
    for j in range(w):
        max_ = max(visit[i][j], max_)
print(max_)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

h, w = MAP()
a = [STR() for _ in range(h)]
b = [[inf for _ in range(w)] for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            b[i][j] = 0
        else:
            for k in range(4):
                ny = i + dy[k]
                nx = j + dx[k]
                if 0 <= ny < h and 0 <= nx < w:
                    b[i][j] = min(b[ny][nx] + 1, b[i][j])
for i in reversed(range(h)):
    for j in reversed(range(w)):
        if a[i][j] == '#':
            b[i][j] = 0
        else:
            for k in range(4):
                ny = i + dy[k]
                nx = j + dx[k]
                if 0 <= ny < h and 0 <= nx < w:
                    b[i][j] = min(b[ny][nx] + 1, b[i][j])
ans = 0
for i in range(h):
    ans = max(ans, max(b[i]))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
a = []
d = []
que = deque()
for i in range(h):
    a.append(list(input()))
    d.append([1e100]*w)
    for j in range(w):
        if a[i][j] == '#':
            que.append([i,j])
            d[i][j] = 0
di = [-1,0,1,0]
dj = [0,1,0,-1]
ans = 0

while que:
    i,j = que.popleft()
    for k in range(4):
        ni = i + di[k]
        nj = j + dj[k]
        if 0 <= ni < h and 0 <= nj < w and d[ni][nj] == 1e100:
            d[ni][nj] = d[i][j] + 1
            ans = max(ans, d[ni][nj])
            que.append([ni,nj])
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from collections import deque


H, W = map(int,input().split()) 
graph = [input() for i in range(H)]#graphの作成
dist = [[-1]*W for i in range(H)]
que = deque()#queueの作成（今回は、初期値が#のところからスタート）

#スタート位置の読み込み（＃の位置）
for h in range(H):
    for w in range(W):
        if graph[h][w] == "#":
            que.append([h, w])
            dist[h][w] = 0 #黒は0、白は-1（なんでもOK）
            
def bfs(que, dist):
    cnt = 0 #黒に塗った回数
    while que:
        y, x = que.popleft()#先に入れたものを出すので最短経路になる
        cnt = dist[y][x] #
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):#上下左右に動かす
            new_y, new_x = y+j, x+k
            if new_y < 0 or H <= new_y or new_x < 0 or W <= new_x:#端っこはスルー
                continue
            elif dist[new_y][new_x] == -1:#セルが白やったら
                dist[new_y][new_x] = cnt+1 #黒からの距離をcnt+1にして
                que.append([new_y, new_x]) #黒にしたので、queに加える
    return cnt #黒のセルをすべて調べたら（結局すべて黒になるが）終わり

print(bfs(que,dist))

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
gridgraph = [list(input()) for _ in range(H)]
distance = [[50000]*W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        if gridgraph[i][j] == "#":
            q.append([i, j])
            distance[i][j] = 0
adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while len(q):
    cy, cx = q.popleft()
    for dy, dx in adjacent:
        ny, nx = cy+dy, cx+dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        if distance[ny][nx] != 50000:
            continue
        distance[ny][nx] = distance[cy][cx] + 1
        q.append([ny, nx])
ans = 0
for d in distance:
    ans = max(ans, max(d))
print(ans)