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 copy
#import time

h,w = map(int,input().split())
a = [input() for _ in range(h)]
b = [[False]*w for _ in range(h)]
#s = time.time()
c = []
d = [(-1,0), (1,0), (0,-1), (0,1)]
ans = 0

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            b[i][j] = True
            c.append((i,j))
#print(time.time()-s)

while True:
    tmp = []
    cnt = 0
    for i,j in c:
        for d1,d2 in d:
            if 0 <= i + d1 < h and 0 <= j + d2 < w:
                if not b[i+d1][j+d2]:
                    tmp.append((i+d1, j+d2))
                    b[i+d1][j+d2] = True
                    cnt += 1
    #print(time.time()-s)
    if cnt > 0:
        c = copy.copy(tmp)
        ans += 1
    else:
        break
    #print(time.time()-s)

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def bfs(H, W, A, dist):
    queue = deque([])
    for h in range(H):
        A_h = A[h]
        dist_h = dist[h]
        for w in range(W):
            if A_h[w] == "#":
                dist_h[w] = 0
                queue.append((h, w))
    while queue:
        h, w = queue.popleft()
        for y, x in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            next_h, next_w = h + y, w + x
            if dist[next_h][next_w] == -1:
                dist[next_h][next_w] = dist[h][w] + 1
                queue.append((next_h, next_w))


def main():
    H, W = map(int, input().split())
    A = [None] * (H + 2)
    A[0] = A[-1] = "." * (W + 2)
    for i in range(1, H + 1):
        A[i] = "".join([".", input().rstrip(), "."])

    dist = [[0] + [-1] * W + [0] for _ in range(H + 2)]
    dist[0] = dist[-1] = [0] * (W + 2)
    bfs(H + 2, W + 2, A, dist)

    ans = max(map(max, dist))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def bfs(H, W, A, dist):
    queue = deque([])
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#":
                dist[h][w] = 0
                queue.append((h, w))
    while queue:
        h, w = queue.popleft()
        for y, x in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            next_h, next_w = h + y, w + x
            if dist[next_h][next_w] == -1:
                dist[next_h][next_w] = dist[h][w] + 1
                queue.append((next_h, next_w))


def main():
    H, W = map(int, input().split())
    A = [None] * (H + 2)
    A[0] = A[-1] = "." * (W + 2)
    for i in range(1, H + 1):
        A[i] = "".join([".", input().rstrip(), "."])

    dist = [[0] + [-1] * W + [0] for _ in range(H + 2)]
    dist[0] = dist[-1] = [0] * (W + 2)
    bfs(H + 2, W + 2, A, dist)

    ans = max(map(max, dist))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

h,w = lr()
a = [list(sr()) for i in range(h)]
ans = 0
q = deque([])
visited = [[False for i in range(w)] for j in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            q.append([i,j])
dir = [[1,0], [-1,0], [0,1], [0,-1]]
while q:
    neq = deque([])
    while q:
        y,x = q.popleft()
        for dy,dx in dir:
            ny,nx = y+dy,x+dx
            if 0<=ny<h and 0<=nx<w and (not visited[ny][nx]) and a[ny][nx] == '.':
                neq.append([ny,nx])
                visited[ny][nx]  = True
                a[ny][nx] = '#'
    if neq:
        ans+=1
        q = neq
    else:
        break
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

H,W = map(int,input().split())
maze = list(list(input()) for i in range(H))
maze_s = [[-1] * W for i in range(H)]
queue = deque([])
for i,row in enumerate(maze):
  for j,value in enumerate(row):
    if value == "#":
      queue.append([i, j])
      maze_s[i][j] = 0
def bfs(maze, maze_s):
  while queue:
    y,x = queue.popleft()
    for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
      new_y,new_x= y+i,x+j
      if 0 <= new_y <= H-1 and 0<= new_x <= W-1:
        if maze[new_y][new_x] == "." and maze_s[new_y][new_x] == -1:
          maze_s[new_y][new_x] = maze_s[y][x] + 1
          queue.append([new_y,new_x])
  c = 0
  for row in maze_s:
    m = max(row)
    c = max(c,m)
  print(c)

bfs(maze,maze_s)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/agc033/tasks/agc033_a

from collections import deque
h, w = map(int, input().split())

matrix = []
for _ in range(h):
    matrix.append(list(input()))

def bfs(matrix):
    # 上、右、下、左
    dy = [-1, 0, 1, 0]
    dx = [0, 1, 0, -1]
    q = deque()
    for i in range(h):
        for j in range(w):
            if matrix[i][j] == '#':
                q.append((i, j))
    ans = 0
    next_q = deque()
    while q:
        y, x = q.popleft()
        for i in range(4):
            next_y = dy[i] + y
            next_x = dx[i] + x
            if 0 <= next_y < h and 0 <= next_x < w and matrix[next_y][next_x] == '.':
                matrix[next_y][next_x] = '#'
                next_q.append((next_y, next_x))
        if not q and next_q:
            q = next_q
            next_q = deque()
            ans += 1
    return ans

ans = bfs(matrix)
print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
lis = [[1000000007] * W for i in range(H)]
A = []
for i in range(H):
    Ain = list(input())
    A.append(Ain)
    for j in range(W):
        if A[i][j] == '#':
            lis[i][j] = 0
        else:
            lis[i][j] = min(lis[i][j],lis[i][j-1]+1)

    for j in reversed(range(W-1)):
        lis[i][j] = min(lis[i][j],lis[i][j+1]+1)
#print(lis)

for j in range(W):
    for i in range(1,H):
        lis[i][j] = min(lis[i][j],lis[i-1][j]+1)
    for i in reversed(range(H-1)):
        lis[i][j] = min(lis[i][j],lis[i+1][j]+1)

#print(lis)
ans = 0
for i in range(H):
    ans = max(ans,max(lis[i]))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int, input().split())
 
A=[]
que=[]
done=[[-1]*W for _ in range(H)]
for h in range(H):
    a=list(input())
    A.append(a)
    for w in range(W):
        if a[w]=="#":
            que.append((h,w))
            done[h][w]=0
 
d=[(1,0),(-1,0),(0,1),(0,-1)]
que=deque(que)
ans=0
while que:
    h,w=que.popleft()
    now=done[h][w]
    for t in d:
        dh,dw=t
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if done[nh][nw]==-1:
                done[nh][nw]=now+1
                que.append((nh,nw))
                ans=max(ans, now+1)
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[input() for _ in range(h)]
visited=[[0]*w for _ in range(h)]
from collections import deque
q=deque([])
for i in range(h):
  for j in range(w):
    if a[i][j]=="#":
      q.append((i,j,0))
      visited[i][j]=1
ans=0
while q:
  i,j,count=q.popleft()
  ans=max(ans,count)
  for nxi,nxj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
    if 0<=nxi<h and 0<=nxj<w and visited[nxi][nxj]==0:
      visited[nxi][nxj]=1
      q.append((nxi,nxj,count+1))
print(ans)

Submission status: Accepted

Solution code:
import sys
#import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

class queue:
	def __init__(self):
		self.l=[0]*(1000*1000+100)
		self.f=0
		self.t=0
		
	def put(self,v):
		self.l[self.f]=v
		self.f+=1
		
	def get(self):
		self.t+=1
		return self.l[self.t-1]
		
	def empty(self):
		return self.f==self.t

def main():
	#a = int(input())
	h, w = tin()
	#s = input()
	mp = [list(input()) for _ in range(h)]
	dist=[[-1] * w for _ in range(h)]
	open_list=queue()
	for hi, l in enumerate(mp):
		for wi, c in enumerate(l):
			if c == '#':
				dist[hi][wi]=0
				open_list.put(hi*2000+wi)
				
	max_dist=0
	while not open_list.empty():
		hi_wi = open_list.get()
		hi = hi_wi // 2000
		wi = hi_wi % 2000
		d = dist[hi][wi]
		for dw, dh in [(0,1),(0,-1),(1,0),(-1,0)]:
			if -1 == wi+dw or -1 == hi + dh or w == wi+dw or h == hi + dh:
				continue
			if dist[hi+dh][wi+dw] >= 0:
				continue
			#if dist[hi+dh][wi+dw]==-2:
				
			dist[hi+dh][wi+dw]=d+1
			open_list.put(((hi+dh)*2000+wi+dw))
			max_dist=d+1
	print(max_dist)
	#for l in dist:
	#	print(l)
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
# import sys
# input = sys.stdin.readline
import itertools
import collections


# 持っているビスケットを叩き、1枚増やす
# ビスケット A枚を 1円に交換する
# 1円をビスケット B枚に交換する
def main():
    h, w = input_list()
    grids = [list(input()) for i in range(h)]
    dist = [[-1]*w for _ in range(h)]

    black_cells = collections.deque()
    for hi in range(h):
        for wi in range(w):
            if grids[hi][wi] == '#':
                black_cells.append((hi, wi))
                dist[hi][wi] = 0

    print(bfs(h, w, black_cells, dist))


def bfs(H, W, black_cells, dist):
    d = 0
    while black_cells:
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx 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


def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
from copy import copy

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def bfs_grid(H, W, s, grid):

    q = deque(s)
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    ans = 0

    while True:

        nq = deque()
        f = False
        while q:
            now = q.popleft()
            x, y = now
            for m in move:
                nx, ny = x + m[0], y + m[1]
                if 0 <= nx < W and 0 <= ny < H:
                    if grid[ny][nx]:
                        f = True
                        grid[ny][nx] = False
                        nq.append((nx, ny))

        if f:
            ans += 1
        if nq:
            q = nq
        else:
            break

    return ans


def main():

    H, W = in_nn()
    grid = in_map2(H)

    s = []
    for y in range(H):
        for x in range(W):
            if not grid[y][x]:
                s.append((x, y))

    if len(s) == H * W:
        print(0)
        exit()

    print(bfs_grid(H, W, s, grid))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from collections import deque
H,W=map(int,input().split())
maze=[]
visited=[[None]*W for _ in range(H)]
q=deque([])
for i in range(H):
    a=input().rstrip()
    maze.append(a)
    for j in range(W):
        if a[j]=="#":
            visited[i][j]=0
            q.append([i,j])
ans=0
while q:
    h,w=q.popleft()
    for nh,nw in ([h+1,w],[h-1,w],[h,w+1],[h,w-1]):
        if nh<0 or nh>H-1 or nw<0 or nw>W-1:
            continue
        if visited[nh][nw]!=None:
            continue
        visited[nh][nw]=visited[h][w]+1
        ans=max(ans,visited[nh][nw])
        q.append([nh,nw])
print(ans)

Submission status: Accepted

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

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().split()))

def pad(mxy, wall="#"):
	w = len(mxy[0])
	gp = wall*(w+2)
	re = [gp,]
	re_app = re.append
	for vx in mxy:
		re_app(wall+vx+wall)
	re_app(gp)
	return re

vD = [(0,1),(1,0),(0,-1),(-1,0)]
vQ = deque([])
vQ_app, vQ_popl = vQ.append, vQ.popleft

def main():
	H,W = linput()
	mM = [input().rstrip() for _ in [0,]*H]
	mM = pad(mM,"$")
	
	res = 0
	cnt = 0
	
	mV = [[INF,]*(W+2) for _ in [INF,]*(H+2)]
	for sr in range(1,H+1):
		for sc in range(1,W+1):
			if mM[sr][sc]==".":
				continue
			mV[sr][sc] = 0
			vQ_app((sr,sc))
	
	while vQ:
		r,c = vQ_popl()
		now_cost = mV[r][c]
		for dr,dc in vD:
			nr,nc = r+dr, c+dc
			if mM[nr][nc]=="$":
				continue
			if now_cost + 1 < mV[nr][nc]:
				vQ_app((nr,nc))
				mV[nr][nc] = now_cost + 1
				res = max(now_cost+1, res)
		
		cnt += 1
		#print(res,cnt,X,Y,H)
		if cnt>4999999: break
	
	print(res)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
#!/home/matsumotokazuho/.pyenv/shims/pypy
# import math
# from copy import deepcopy
# from operator import itemgetter
# from collections import defaultdict
# from collections import Counter
# from collections import deque
# import pprint
# import itertools
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

# q = deque()
q = []
# for i, j in itertools.product(range(H), range(W)):
for i in range(H):
    for j in range(W):
        if Board[i][j] == '#':
            # Board[i][j] = 0
            q.append((i, j))

ans = 0
while q:
    qq = []
    ans += 1
    for yx in q:
        for d in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            y = yx[0] + d[0]
            x = yx[1] + d[1]
            # y, x = [i+j for i, j in zip(yx, d)]
            if y < 0 or H - 1 < y or x < 0 or W - 1 < x:
                pass
            elif Board[y][x] == '.':
                # Board[y][x] = Board[q[0][0]][q[0][1]] + 1
                Board[y][x] = '#'
                qq.append((y, x))
    q = qq

# ans = max(list(itertools.chain.from_iterable(Board)))
# ans = max(itertools.chain.from_iterable(Board))
# pprint.pprint(Board)
print(ans-1)

Submission status: Accepted

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


#-------------------------------------------------------------------------
#白から黒に変えていく

def search() :
    H,W=map(int,input().split())
    pos=deque([])

    D= [[True]*(W+2)]                                  #True True True True
    D+=[[True]+[False]*W+[True] for i in range(H)]     #True FalseFalseTrue
    D.append([True]*(W+2))                             #True True True True

    for i in range(H) :
        maze=input()
        for j in range(W) :
            if maze[j]=="#" :
                pos.append([i+1,j+1,0])
                D[i+1][j+1]=True
 
    while len(pos)>0 :                             #forではなく各if構文だと通った…
        h,w,depth=pos.popleft()
        if not D[h+1][w] :
            pos.append([h+1,w,depth+1])
            D[h+1][w]=True

        if not D[h-1][w] :
            pos.append([h-1,w,depth+1])
            D[h-1][w]=True

        if not D[h][w+1] :
            pos.append([h,w+1,depth+1])
            D[h][w+1]=True

        if not D[h][w-1] :
            pos.append([h,w-1,depth+1])
            D[h][w-1]=True

    return depth            

print(search())

Submission status: Accepted

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


#-------------------------------------------------------------------------
#白から黒に変えていく

def search() :
    H,W=map(int,input().split())
    pos=deque([])

    D= [[True]*(W+2)]                                  #True True True True
    D+=[[True]+[False]*W+[True] for i in range(H)]     #True FalseFalseTrue
    D.append([True]*(W+2))                             #True True True True

    for i in range(H) :
        maze=input()
        for j in range(W) :
            if maze[j]=="#" :
                pos.append([i+1,j+1,0])
                D[i+1][j+1]=True
 
    while len(pos)>0 :
        h,w,depth=pos.popleft()
        if not D[h+1][w] :
            pos.append([h+1,w,depth+1])
            D[h+1][w]=True

        if not D[h-1][w] :
            pos.append([h-1,w,depth+1])
            D[h-1][w]=True

        if not D[h][w+1] :
            pos.append([h,w+1,depth+1])
            D[h][w+1]=True

        if not D[h][w-1] :
            pos.append([h,w-1,depth+1])
            D[h][w-1]=True

    return depth            

print(search())

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    H, W = read_values()
    F = [input().strip() for _ in range(H)]
    A = [False] * (H * W)
    Q = deque() 

    for h in range(H):
        for w in range(W):
            if F[h][w] == "#":
                Q.append((h, w, 0))
                A[h * W + w] = True

    res = V(max)
    while Q:
        h, w, d = Q.popleft()
        res.ud(d)

        for hh, ww in ((h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)):
            if 0 <= hh < H and 0 <= ww < W:
                if A[hh * W + ww]:
                    continue
                Q.append((hh, ww, d + 1))
                A[hh * W + ww] = True
    
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    H, W = map(int, input().split())
    A = [input() for _ in range(H)]
    adj = [[] for _ in range(W*H)]
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    
    # 黒のマスからbfsする
    queue = deque()
    visit = [-1] * (W*H)

    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                queue.append(W*i + j)
                visit[W*i + j] = 0
            for k in range(4):
                y = i + dy[k]
                x = j + dx[k]
                if 0 <= y < H and 0 <= x < W:
                    adj[W*i + j].append(W*y + x)
    
    while queue:
        now = queue.popleft()
        for u in adj[now]:
            if visit[u] < 0:
                queue.append(u)
                visit[u] = visit[now] + 1
    print(max(visit))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(4100000)
def main():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    Q = deque([])
    visited = [[float('inf')] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                Q.append((h,w))
                visited[h][w] = 0
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    ans = 0
    while Q:
        y, x = Q.popleft()
        now = visited[y][x]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < W and 0 <= ny < H:
                if visited[ny][nx] == float('inf'):
                    visited[ny][nx] = now + 1
                    Q.append((ny,nx))
                    ans = max(ans, now + 1)

    print(ans)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

def bfs(que,d): #幅優先探索
  #いつもはここで定義
  #入力のグラフを初期化
  #d = [[float("inf")] * w for i in range(h)] 
  #que = deque([])
  #que.append((sx,sy))
  #d[sx][sy] = 0
  
  dx = [-1,0,0,1]
  dy = [0,-1,1,0]
  
  while que:
    lead_h,lead_w = que.popleft()
    lead = d[lead_h][lead_w]
    #lead == queの先頭にある要素を取り出す
    for i in range(4):
      nx = lead_w + dx[i]
      ny = lead_h + dy[i]
      if ny<0 or h<=ny or nx<0 or w<=nx:
        #範囲外の場合
        continue
      if d[ny][nx]==float("inf"):
        d[ny][nx] = lead + 1
        que.append((ny,nx))
  return lead

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

#多点スタートなのでbfs()内で定義して初期化しない
d = [[float("inf")] * w for i in range(h)] 

#キューも同様
que = deque([])
for i in range(h):
  for j in range(w):
    if maze[i][j] == "#":
      que.append((i,j))
      #各"#"を入れる
      d[i][j] = 0

#print(bfs())
lead = bfs(que,d)
print(lead)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(que,d): #幅優先探索
  #入力のグラフを初期化
  #d = [[float("inf")] * w for i in range(h)] 
  #d == mazeリストの"."を"inf"に変えたリスト
  lead = 0
  dx = [-1,0,0,1]
  dy = [0,-1,1,0]
  
  #que = deque([])
  #que.append((sx,sy))
  #d[sx][sy] = 0
  
  while que:
    lead_h,lead_w = que.popleft()
    lead = d[lead_h][lead_w]
    #lead == queの先頭にある要素を取り出す
    for i in range(4):
      nx = lead_w + dx[i]
      ny = lead_h + dy[i]
      if ny<0 or h<=ny or nx<0 or w<=nx:
        continue
      if d[ny][nx]==float("inf"):
        d[ny][nx] = lead + 1
        que.append((ny,nx))
  return lead

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

d = [[float("inf")] * w for i in range(h)] 

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

#print(bfs())
lead = bfs(que,d)
print(lead)

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
from collections import deque
def main(H, W, A):
    dist = [[-1] * W for _ in range(H)]
    q = deque()
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                dist[i][j] = 0
                q.append((i, j, 0))

    ans = 0
    while q:
        i, j, d = q.popleft()
        ans = max(ans, d)
        for ni, nj in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
            if not (0 <= ni < H and 0 <= nj < W): continue
            if dist[ni][nj] >= 0: continue
            dist[ni][nj] = d + 1
            q.append((ni, nj, d + 1))
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [input().rstrip() for _ in range(H)]
    main(H, W, A)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
from decimal import *

H, W = MAP()
A = [input() for _ in range(H)]
cnt = [[-1]*W for _ in range(H)]
q = deque()

for y in range(H):
    for x in range(W):
        if A[y][x] == "#":
            cnt[y][x] = 0
            q.append((y, x))

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

while q:
    y, x = q.popleft()
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < H and 0 <= nx < W and cnt[ny][nx] == -1:
            cnt[ny][nx] = cnt[y][x] + 1
            q.append((ny, nx))

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
from decimal import *

H, W = MAP()
A = [input() for _ in range(H)]
cnt = [[0]*W for _ in range(H)]
q = deque()

for y in range(H):
    for x in range(W):
        if A[y][x] == "#":
            q.append((y, x))

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

while q:
    y, x = q.popleft()
    for Dy, Dx in zip(dy, dx):
        ny = y + Dy
        nx = x + Dx
        if 0 <= ny < H and 0 <= nx < W and cnt[ny][nx] == 0 and A[ny][nx] == ".":
            cnt[ny][nx] = cnt[y][x] + 1
            q.append((ny, nx))

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
from decimal import *

H, W = MAP()
A = [input() for _ in range(H)]
cnt = [[-1]*W for _ in range(H)]
q = deque()

for y in range(H):
    for x in range(W):
        if A[y][x] == "#":
            cnt[y][x] = 0
            q.append((y, x))

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

while q:
    y, x = q.popleft()
    for Dy, Dx in zip(dy, dx):
        ny = y + Dy
        nx = x + Dx
        if 0 <= ny < H and 0 <= nx < W and cnt[ny][nx] == -1 and A[ny][nx] == ".":
            cnt[ny][nx] = cnt[y][x] + 1
            q.append((ny, nx))

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