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:
"""
    Author - Satwik Tiwari .
    25th Sept , 2020  - Friday
"""

#===============================================================================================
#importing some useful libraries.


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase


# from itertools import *
from heapq import *
from math import gcd, factorial,floor,ceil

from copy import deepcopy
from collections import deque


# from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
# from itertools import combinations as comb # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
# from itertools import permutations as permutate


from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect

#==============================================================================================
#fast I/O region
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")

#===============================================================================================
### START ITERATE RECURSION ###
from types import GeneratorType
def iterative(f, stack=[]):
  def wrapped_func(*args, **kwargs):
    if stack: return f(*args, **kwargs)
    to = f(*args, **kwargs)
    while True:
      if type(to) is GeneratorType:
        stack.append(to)
        to = next(to)
        continue
      stack.pop()
      if not stack: break
      to = stack[-1].send(to)
    return to
  return wrapped_func
#### END ITERATE RECURSION ####

#===============================================================================================
#some shortcuts

mod = 10**9+7
def inp(): return sys.stdin.readline().rstrip("\r\n") #for fast input
def out(var): sys.stdout.write(str(var))  #for fast output, always take string
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())
# def graph(vertex): return [[] for i in range(0,vertex+1)]
def zerolist(n): return [0]*n
def nextline(): out("\n")  #as stdout.write always print sring.
def testcase(t):
    for pp in range(t):
        solve(pp)
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def google(p):
    print('Case #'+str(p)+': ',end='')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(x, y, p) :
    res = 1     # Initialize result
    x = x % p  # Update x if it is more , than or equal to p
    if (x == 0) :
        return 0
    while (y > 0) :
        if ((y & 1) == 1) : # If y is odd, multiply, x with result
            res = (res * x) % p

        y = y >> 1      # y = y/2
        x = (x * x) % p
    return res
def ncr(n,r): return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))
def isPrime(n) :
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True

#===============================================================================================
# code here ;))
def solve(case):
    n,m = sep()
    grid = []
    for i in range(n):
        temp = list(inp())
        grid.append(temp)

    sources = []
    for i in range(n):
        for j in range(m):
            if(grid[i][j] == '#'):
                sources.append(i*m+j)

    g = [[] for i in range(n*m)]
    for i in range(n):
        for j in range(m):
            if(i>0):
                g[i*m+j].append((i-1)*m+j)
                g[(i-1)*m+j].append(i*m+j)
            if(j>0):
                g[i*m+j].append(i*m+j-1)
                g[i*m+j-1].append(i*m+j)
            if(i<n-1):
                g[i*m+j].append((i+1)*m+j)
                g[(i+1)*m+j].append(i*m+j)
            if(j<m-1):
                g[i*m+j].append(i*m+j+1)
                g[i*m+j+1].append(i*m+j)
    # print(sources)
    dist = [0]*(n*m)
    q = deque([])
    vis = [False]*(n*m)
    for i in sources:
        q.append(i)
        vis[i] = True
    while(len(q)!=0):
        curr = q.popleft()
        for i in g[curr]:
            if(not vis[i]):
                dist[i] = dist[curr]+1
                vis[i] = True
                q.append(i)

    print(max(dist))



testcase(1)
# testcase(int(inp()))

Submission status: Accepted

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

for i in range(h):
  for j in range(w):
    if i!=0:
      connection[i*w+j].append((i-1)*w+j)
    if i!=h-1:
      connection[i*w+j].append((i+1)*w+j)
    if j!=0:
      connection[i*w+j].append(i*w+j-1)
    if j!=w-1:
      connection[i*w+j].append(i*w+j+1)
    if l[i][j]=='#':
      start.append(i*w+j)
n=h*w

def bfs(l):
  distance=[-1]*n
  next=set()
  next2=set()
  visited=[-1]*n
  visitct=0
  for i in range(len(l)):
    distance[l[i]]=0
    for j in range(len(connection[l[i]])):
      next.add(connection[l[i]][j])
    visited[l[i]]=1
    visitct=+1
  next=list(next)
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

print(max(bfs(start)))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

# from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
#import math
# from itertools import product, accumulate, combinations, product
#import bisect
# import numpy as np
# from copy import deepcopy
from collections import deque
# from decimal import Decimal
# from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())

def bfs(MAP, queue):

    while queue:
        turn, ci, cj = queue.popleft()
        for ii, jj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            ni = ci + ii
            nj = cj + jj
            if MAP[ni][nj] == 0:
                MAP[ni][nj] = 1
                queue.append((turn + 1, ni, nj))
    return turn


def run():
    H, W = map(int, input().split())
    queue = deque([])
    MAP = [[1] * (W+2)]
    d = {'#' : 1, '.' : 0}
    for i in range(1, H+1):
        X = input()
        S = [1]
        for j, s in enumerate(X, 1):
            S.append(d[s])
            if s == '#':
                queue.append((0, i, j))
        S.append(1)
        MAP.append(S)

    #print(queue)
    MAP.append([1] * (W+2))

    print(bfs(MAP, queue))


if __name__ == "__main__":
    #print(math.gcd(0, 10))
    run()

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
s_l = [input() for _ in range(H)]
dist = [(1, 0), (-1, 0), (0, 1), (0, -1)]
queue = deque()
results = []
for y, s in enumerate(s_l):
    result = []
    for x, p in enumerate(s):
        result.append(False if p == "." else True)
        if p == "#":
            queue.append((y, x))
    results.append(result)

count = 0
while queue:
    starts = []
    while queue:
        starts.append(queue.popleft())
    for y, x in starts:
        for dy, dx in dist:
            ny = y + dy
            nx = x + dx
            if ny < 0 or ny >= H or nx < 0 or nx >= W:
                continue
            if s_l[ny][nx] == "." and not results[ny][nx]:
                queue.append((ny, nx))
                results[ny][nx] = True
    if queue:
        count += 1

print(count)

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
h, w = map(int, input().rstrip("\n").split())
matrix = [[-1 for j in range(w)] for i in range(h)]
queue = deque()
for i in range(h):
    cells = list(input().rstrip("\n"))
    for j, cell in enumerate(cells):
        if cell == "#":
            matrix[i][j] = 0
            queue.append((i, j))
while queue:
    i, j = queue.popleft()
    for i_diff, j_diff in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
        i_current = i + i_diff
        j_current = j + j_diff
        if (
            0 <= i_current < h
            and 0 <= j_current < w
            and matrix[i_current][j_current] == -1
        ):
            matrix[i_current][j_current] = matrix[i][j] + 1
            queue.append((i_current, j_current))

max_step = max([max(row) for row in matrix])
print(max_step)

Submission status: Accepted

Solution code:
from collections import deque

def cal():
    h, w = map(int, input().split())
    q = deque()
    counts = [[True for _ in range(w+2)]]+[[True]+[False]*w+[True] for _ in range(h)]+[[True for _ in range(w+2)]]
    for i in range(h):
        a = input()
        for j in range(w):
            if a[j] == '#':
                q.append([i+1, j+1, 0])
                counts[i+1][j+1] = True

    while q:
        x, y, z = q.popleft()    
        if not counts[x+1][y]:
            counts[x+1][y] = True
            q.append([x+1, y, z+1])
        if not counts[x-1][y]:
            counts[x-1][y] = True
            q.append([x-1, y, z+1])
        if not counts[x][y+1]:
            counts[x][y+1] = True
            q.append([x, y+1, z+1])
        if not counts[x][y-1]:
            counts[x][y-1] = True
            q.append([x, y-1, z+1])
    print(z)
    

cal()

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

######################################################

H,W=mint()
A=[input() for _ in range(H)]
C=[[0]*W for _ in range(H)]
for i,j in product(range(H),range(W)):
    if A[i][j]=='.':
        C[i][j]=INF
for i,j in product(range(H),range(1,W)):
    C[i][j] = min(C[i][j],C[i][j-1]+1)
for i,j in product(range(1,H),range(W)):
    C[i][j] = min(C[i][j],C[i-1][j]+1)
for i,j in product(range(H),range(W-2,-1,-1)):
    C[i][j] = min(C[i][j],C[i][j+1]+1)
for i,j in product(range(H-2,-1,-1),range(W)):
    C[i][j] = min(C[i][j],C[i+1][j]+1)
print(max([max(c) for c in C]))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
A=[list(input()) for i in range(h)]
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal as D  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
from fractions import Fraction as F  #F(a,b)で正確なa/b
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

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

dx=[1,0,-1,0];dy=[0,1,0,-1]
while queue:
    x,y,t=queue.pop()
    for i,j in zip(dx,dy):
        if 0<=x+i<h and 0<=y+j<w and seen[x+i][y+j]==0:
            queue.appendleft([x+i,y+j,t+1])
            seen[x+i][y+j]=1
print(t)

Submission status: Accepted

Solution code:
from collections import deque


def main():
    h, w = map(int, input().split())
    graph = [list(input()) for _ in range(h)]
    ans = 0

    dist = [[-1 for _ in range(w)] for _ in range(h)]

    black = deque()
    for r in range(h):
        for c in range(w):
            if graph[r][c] == "#":
                black.append((r, c))
                dist[r][c] = 0

    while black:
        r, c = black.popleft()
        ans = max(ans, dist[r][c])
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nr = r + dr
            nc = c + dc
            if not (0 <= nr < h and 0 <= nc < w):
                continue
            if dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                black.append((nr, nc))

    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())
D = [list(input()) for i in range(H)]
ans = 0
dist = [[-1]*W for i in range(H)]
Q = deque()
dx = [1,0,-1,0]
dy = [0,-1,0,1]

for sy in range(H):
    for sx in range(W):
        if D[sy][sx] == "#":
            Q.append((sx,sy))
            dist[sy][sx] = 0
while Q:
    x,y = Q.popleft()
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0<=nx<=W-1 and 0<=ny<=H-1 and dist[ny][nx] == -1 and D[ny][nx] == ".":
            Q.append((nx,ny))
            dist[ny][nx] = dist[y][x]+1

for y in range(H):
    for x in range(W):
        if D[y][x] == ".":
            ans = max(ans,dist[y][x])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

h,w=map(int,input().split())
INF=float('inf')
G=[]
for _ in range(h):
  s=input()
  S=[]
  for i in range(w):
    S.append(s[i])
  G.append(S)
  
dist=[[INF for i in range(w)] for j in range(h)]
Q=deque()
for i in range(h):
  for j in range(w):
    if G[i][j]=='#':
      dist[i][j]=0
      Q.append((i,j))
while Q:
  pi,pj=Q.popleft()
  for di,dj in [[-1,0],[1,0],[0,-1],[0,1]]:
    ni,nj=pi+di,pj+dj
    if 0>ni or ni>h-1:
      continue
    if 0>nj or nj>w-1:
      continue
    if G[ni][nj]=='#':
      continue
    if dist[ni][nj]>dist[pi][pj]+1:
      dist[ni][nj]=dist[pi][pj]+1
      Q.append((ni,nj))
ans=-INF
for i in range(h):
  for j in range(w):
    ans=max(ans,dist[i][j])
print(ans)

Submission status: Accepted

Solution code:
import collections
import math
import copy

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

A=[list(str(input())) for i in range(H)]
#1<=sy<=R
d=[[-1 for j in range(W)]for i in range(H)]
inf=10**6
ans=0
queue=collections.deque()
for i in range(H):
    for j in range(W):
        if A[i][j]=='#':
            queue.append([i,j])
            d[i][j]=0

moves=[[1,0],[-1,0],[0,1],[0,-1]]

nax=0
while len(queue)>0:
    now=queue.popleft()
    for i in range(4):
        ny=now[0]+moves[i][0]
        nx=now[1]+moves[i][1]
        if 0<=ny and ny<H and 0<=nx and nx<W and A[ny][nx]=='.' and d[ny][nx]==-1:
            d[ny][nx]=d[now[0]][now[1]]+1
            nax=max(nax,d[ny][nx])
            queue.append([ny,nx])


print(nax)

Submission status: Accepted

Solution code:
from collections import deque

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

def BFS(H, W, grid):
    visited = [[True for _ in range(W+2)] for _ in range(H+2)]
    que = deque()
    for i in range(H):
        visited[i+1][1:-1] = map(lambda _:_=="#", grid[i])
        for j in range(W):
            if(grid[i][j] == "#"):
                que.append((i+1, j+1, 0))
    dist = [(0, 1), (-1, 0), (0, -1), (1, 0)]
        
    while que:
        x, y, c = que.popleft()
        for dx, dy in dist:
            nx = x + dx
            ny = y + dy
            
            if(not visited[nx][ny]):
                que.append((nx, ny, c+1))
                visited[nx][ny] = True
    return c
        
print(BFS(H, W, grid))

Submission status: Accepted

Solution code:
H,W=list(map(int,input().split()))
inf=float("inf")
import numpy as np
mem=np.full((H,W),inf)
l=[list(input()) for i in range(H)]
for i in range(H):
   for j in range(W):
      if l[i][j]=="#":
         mem[i,j]=0
for i in range(W-1):
   mem[:,i+1]=np.minimum(mem[:,i]+1,mem[:,i+1])
for i in reversed(range(1,W)):
   mem[:,i-1]=np.minimum(mem[:,i-1],mem[:,i]+1)
for i in range(H-1):
   mem[i+1,:]=np.minimum(mem[i+1,:],mem[i,:]+1)
for i in reversed(range(1,H)):
   mem[i-1,:]=np.minimum(mem[i-1,:],mem[i,:]+1)
print(int(np.max(mem)))

Submission status: Accepted

Solution code:
from collections import deque
 
def solve(h, w, a):
    used = [[True] * (w+2) for _ in range(h+2)]
    que = deque()
    for r in range(h):
        used[r+1][1:-1] = map(lambda _:_=="#", a[r])
        for c in range(w):
            if a[r][c] == "#":
                que.append((r+1, c+1, 0))
    neighbors = [(1,0), (0,1), (-1,0), (0,-1)]
    while que:
        r, c, k = que.popleft()
        for dr, dc in neighbors:
            nr, nc = r+dr, c+dc
            if not used[nr][nc]:
                que.append((nr, nc, k+1))
                used[nr][nc] = True
    return k
 
h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(solve(h, w, a))

Submission status: Accepted

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

def main():
    H, W = input_list()
    grid = [input() for i in range(H)]
    dist = [[-1]*W for _ in range(H)]
    black_cells = collections.deque()
    for h in range(H):
        for w in range(W):
            if grid[h][w] == '#':
                black_cells.append((h, w))
                dist[h][w] = 0

    def bfs(black_cells, dist):
        d = 0
        while black_cells:
            h, w = black_cells.popleft()
            d = dist[h][w]
            for 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
    
    print(bfs(black_cells, dist))
    
#6 5 2 5 3 2
#1 2 3 4 5 6

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
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline().rstrip()


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 main():
    H, W = map(int, input().split())
    grid = [input() for _ in range(H)]
    dist = [[-1]*W for _ in range(H)]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

maze=[list(input()) for i 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 maze[i][j]=='#':
      Q.append((i,j,0))


while Q:
  x,y,z=Q.popleft()
  for i in range(4):
    nx=x+dx[i]
    ny=y+dy[i]

    if 0<=nx<h and 0<=ny<w and maze[nx][ny]=='.':
      Q.append((nx,ny,z+1))
      maze[nx][ny]='#'


print(z)

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    h,w = map(int,ipt().split())
    dq = deque()
    a = [input()+"#" for i in range(h)] + ["#"*(w+1)]
    d = [[-1]*(w+1) for i in range(h+1)]
    for i in range(h):
        d[i][w] = 0
    for i in range(w):
        d[h][i] = 0

    for i in range(h):
        ai = a[i]
        for j in range(w):
            if ai[j] == "#":
                d[i][j] = 0
                for dx,dy in dir:
                    nx = i+dx
                    ny = j+dy
                    if a[nx][ny] == "." and d[nx][ny] == -1:
                        dq.append((nx,ny))
                        d[nx][ny] = 1

    while dq:
        qx,qy = dq.popleft()
        nd = d[qx][qy]
        for dx,dy in dir:
            nx = qx+dx
            ny = qy+dy
            if a[nx][ny] == "." and d[nx][ny] == -1:
                dq.append((nx,ny))
                d[nx][ny] = nd+1

#    print(d)
    ma = 0
    for i in d:
        for j in i:
            if ma < j:
                ma = j

    print(ma)




    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

q = deque()

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

while q:
    y, x, d = q.popleft()
    if a[y][x] == '#':
        for xdx, ydy in zip((x, x, x+1, x-1), (y+1, y-1, y, y)):
            if (0 <= xdx < w) and (0 <= ydy < h):
                if a[ydy][xdx] == '.':
                    a[ydy][xdx] = '#'
                    q.append((ydy, xdx, d+1))
print(d)

Submission status: Accepted

Solution code:
from collections import deque

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

ds = [[-1,0],[1,0],[0,-1],[0,1]]
q = deque([])

cnt = 0

for i in range(H):
  for j in range(W):
    if mp[i][j] == '#':
      q.append((i,j,0))
      cnt += 1

if cnt == H*W:
  print(0)
  exit()

while q:
  t = q.popleft()
  for d in ds:
    ny = t[0]+d[0]
    nx = t[1]+d[1]
    if 0 <= ny < H and 0<= nx < W:
      if mp[ny][nx] == '.':
        mp[ny][nx] = '#'
        q.append((ny,nx,t[2]+1))
        cnt += 1
        if cnt == H*W:
          print(t[2]+1)
          exit()

Submission status: Accepted

Solution code:
from collections import deque

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

for i in range(1,H+1):
    A[i]="*"+input()+"*"

inf=float("inf")
Dist=[[inf]*(W+2) for _ in range(H+2)]
Q=deque()

for x in range(1,H+1):
    for y in range(1,W+1):
        if A[x][y]=="#":
            Dist[x][y]=0
            Q.append((x,y))

E=[(-1,0),(1,0),(0,-1),(0,1)]
while Q:
    (x,y)=Q.popleft()
    for (a,b) in E:
        if A[x+a][y+b]=="." and Dist[x+a][y+b]==inf:
            Dist[x+a][y+b]=Dist[x][y]+1
            Q.append((x+a,y+b))

Ans=0
for x in range(1,H+1):
    for y in range(1,W+1):
        Ans=max(Ans,Dist[x][y])
print(Ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
a = []
for _ in range(H):
    a.append(input())
queue = deque([])
dist = [[-1 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if a[i][j] == "#":
            queue.append([i, j])
            dist[i][j] = 0
dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]
while queue:
    now = queue.popleft()
    h = now[0]
    w = now[1]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        if dist[nh][nw] == -1:
            dist[nh][nw] = dist[h][w] + 1
            queue.append([nh, nw])
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, dist[i][j])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    h, w = map(int,input().split())
    A = [list(input()) for _ in range(h)]
    B = []

    for i,a in enumerate(A):
        for j,b in enumerate(a):
            if b == "#":
                B.append((i,j))

    dxy = [[1,0],[-1,0],[0,1],[0,-1]]

    stack = deque(B)
    darked = len(stack)
    targetd = h*w
    count = 0

    while darked < targetd:
        nextd = deque([])

        while stack:
            x, y = stack.popleft()
            for dx,dy in dxy:
                X = x + dx
                Y = y + dy
                if not(0 <= X < h) or not(0 <= Y < w):
                    continue
                if A[X][Y]==".":
                    A[X][Y]="#"
                    nextd.append((X,Y))
        count += 1
        stack = nextd
        darked += len(stack)
    print(count)
    
main()

Submission status: Accepted

Solution code:
from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [[-1] * w for _ in range(h)]  # 前処理
    que = deque()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i][j] = 0
                que.append((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if 0 <= i < h and 0 <= j < w and dist[i][j] < 0:
                dist[i][j] = dist[x][y] + 1
                que.append((i, j))
    return max(max(ans) for ans in dist)


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

Submission status: Accepted

Solution code:
from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [[-1] * w for _ in range(h)]  # 前処理
    que = deque()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i][j] = 0
                que.append((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if 0 <= i < h and 0 <= j < w and dist[i][j] < 0:
                dist[i][j] = dist[x][y] + 1
                que.append((i, j))
    return dist[x][y]


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