Problem:


Score : 300 points

Problem Statement

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

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

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

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

Constraints

1 \leq H,W \leq 1000

A_{ij} is # or ..

The given grid has at least one black square.

Input

Input is given from Standard Input in the following format:

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

Output

Print the number of operations that will be performed.

Sample Input 1

3 3
...
.#.
...

Sample Output 1

2

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

Sample Input 2

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

Sample Output 2

3



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


Sample output:
2

Submission status: Accepted

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

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

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

while True:
    nl = []
    
    for x, y in l:
        for nx, ny in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
            if 0<=nx<H and 0<=ny<W and A[nx][ny]=='.':
                nl.append((nx, ny))
                A[nx][ny] = '#'
    
    if len(nl)==0:
        break
    
    l = nl
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

def input():
    return sys.stdin.readline().strip()

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

    que = deque()
    for x in range(W):
        for y in range(H):
            if A[y][x] == '#':
                que.append((x,y,0))        
    ans = 0
    while que:
        x,y,c = que.popleft()
        for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
            sx = x + dx
            sy = y + dy
            if sx < 0 or sx >= W or sy < 0 or sy >= H or A[sy][sx] == '#':
                continue
            if A[sy][sx] == '.':
                que.append((sx,sy,c+1))
                A[sy][sx] = c + 1
                ans = max(ans,c+1)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

from collections import deque
q = deque()
reach = [[False]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append([i,j,0])
            reach[i][j] = True

ans = 0
while q:
    i,j,cnt = q.popleft()
    ans = max(ans,cnt)
    for k,l in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=i+k<h and 0<=j+l<w:
            if not reach[i+k][j+l]:
                q.append([i+k,j+l,cnt+1])
                reach[i+k][j+l] = True

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

h,w=MI()
dp=[[-1]*w for i in range(h)]
Q=deque([])
for i in range(h):
    s=SI()
    for j in range(w):
        if s[j]=="#":
            dp[i][j]=0
            Q.append((i,j))
step=[(-1,0),(1,0),(0,1),(0,-1)]
while Q:
    x,y=Q.popleft()
    for i,j in step:
        if not(0<=x+i<h and 0<=y+j<w):
            continue
        if dp[x+i][y+j]<0:
            Q.append((x+i,y+j))
            dp[x+i][y+j]=dp[x][y]+1
ans=-inf
#print(dp)
for i in range(h):
    for j in range(w):
        ans=max(ans,dp[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)]
    d = [[float('inf')] * W for _ in range(H)]
    Q = deque([])
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                d[h][w] = 0
                Q.append([h,w])
    dh = [1,0,-1,0]
    dw = [0,1,0,-1]
    while Q:
        h,w = Q.popleft()
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            if 0 <= nh < H and 0 <= nw < W:
                if A[nh][nw] == '.' and d[nh][nw] == float('inf'):
                    A[nh][nw] = '#'
                    d[nh][nw] = min(d[nh][nw], d[h][w] + 1)
                    Q.append([nh,nw])

    ans = 0
    for h in range(H):
        ans = max(ans, max(d[h]))

    print(ans)
    


if __name__ == "__main__":
    main()

Submission status: Accepted

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

from collections import deque

visited = [[False] * w 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))
            visited[i][j] = True

cnt = 0
while q:
    y, x, count = q.popleft()
    cnt = max(cnt, count)
    for dy, dx in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        ny, nx = y + dy, x + dx
        if ny < 0 or ny >= h or nx < 0 or nx >= w: continue
        if visited[ny][nx]: continue
        q.append((ny, nx, count + 1))
        visited[ny][nx] = True
print(cnt)

Submission status: Accepted

Solution code:
from collections import deque
inf=float("inf")

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

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

    while len(queue)>0:
        x,y=queue.popleft()
        for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
            X,Y=x+i,y+j
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]=="white":
                    color[X][Y]="gray"
                    D[X][Y]=D[x][y]+1
                    queue.append([X,Y])
        color[x][y]="black"

    return D


h,w=map(int,input().split())
A=[list(input()) for _ in range(h)]
D=BFS()
ans=0
for i in range(h):
    ans=max(ans,max(D[i]))
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 = [(i, j) for i, a in enumerate(A) for j, b in enumerate(a) if b == '#']
    dxy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    stack = deque(B)
    colored = len(B)
    tot = h * w
    count = 0
    while colored < tot:
        next = deque([])
        while stack:
            y, x = stack.popleft()
            for dx, dy in dxy:
                X = x + dx
                Y = y + dy
                if X < 0 or X >= w or Y < 0 or Y >= h:
                    continue
                if A[Y][X] == '.':
                    next.append((Y, X))
                    A[Y][X] = '#'
        stack = next
        count += 1
        colored += len(next)
    print(count)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline #inputの際に入力が終わるまで読み続ける


##入力例1
# 3 3
# ...
# .#.
# ...
def search():
    H, W = map(int, input().split()) ##H=3,W=3
    pos = deque([])

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

    for i in range(H):
        maze = input() #inputの際に入力が終わるまで読み続ける
        for j in range(W):
            if maze[j] == "#":
                pos.append([i + 1, j + 1, 0]) #pos = ([2, 2, 0])
                D[i + 1][j + 1] = True
    ## T T T T T
    ## T F F F T
    ## T F T F T
    ## T F F F T
    ## T T T T T

    while len(pos) > 0:
        h, w, depth = pos.popleft()
        ##上下左右の座標に同時進行で同じ操作を行う

        if not D[h + 1][w]: #([2, 2, 0])の一つ上の座標([3, 2, 0])がNot True(False)の場合
            pos.append([h + 1, w, depth + 1]) #その座標([3, 2, 1])をpopに追加
                                              #deathは黒を白に変更した回数を記録していく
            D[h + 1][w] = True #その座標([3, 2, 0])を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
    ##最終的なdeath(白を黒に変更した回数)を出力
    return depth


print(search())

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    R,C = NMI()
    #sy, sx = NMI()
    #gy, gx = NMI()
    board = [list(input()) for _ in range(R)]
    
    ans = 0

    #移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    #すべての点をINFで初期化
    INF = R*C*2
    distance = [[INF for _ in range(C)] for _ in range(R)]

    #地点を保存するqueを作成
    que = deque([])
    
    #スタート地点を取り出す
    for r in range(R):
        for c in range(C):
            if board[r][c] == '#':
                que.append((r,c))
                #スタート地点の距離は0
                distance[r][c] = 0

                
    cnt = 0
    
    #queが空になるまでループ
    while len(que) != 0:
        #取り出してきた状態
        pop = que.popleft()
        
        #移動4方向をループ
        for i in range(len(dx)):
            #移動した後の点をny,nxとする
            ny = pop[0]+dy[i]
            nx = pop[1]+dx[i]

            #nyが0以上R未満   nxが0以上C未満   まだ訪れたことがない
            if 0<= ny < R and 0 <= nx < C and distance[ny][nx] == INF:
                #つまり移動可能でまだ行ったことがなければqueへ入れる
                que.append((ny,nx))
                #その距離をもとのpopの最短距離+1でdistanceに記録
                distance[ny][nx] = distance[pop[0]][pop[1]]+1
                if ans < distance[ny][nx]:
                    ans = distance[ny][nx]
                
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
grid = []
d = deque()
next_d = deque()
for i in range(H):
    grid.append(list(input()))
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            d.append((i,j))
dx = [0,-1,0,1]
dy = [1,0,-1,0]
ans = -1
while d:
    ans += 1
    while d:
        y,x = d.pop()
        for i in range(4):
            next_y = y+dy[i]
            next_x = x+dx[i]
            if next_y >= 0 and next_y < H and next_x >= 0 and next_x < W:
                if grid[next_y][next_x] == '.':
                    grid[next_y][next_x] = '#'
                    next_d.append((next_y,next_x))
    d = next_d
    next_d = deque()
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
grid = [["#"] * (W+2)]
for _ in range(H):
    grid.append(list("#" + sys.stdin.readline().strip() + "#"))
grid.append(["#"] * (W+2))
# print(grid)

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

ans = 0
while q:
    x, y, count = q.popleft()
    for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        if grid[y+dy][x+dx] != ".":
            continue
        grid[y+dy][x+dx] = count + 1
        ans = count + 1
        q.append((x+dx, y+dy, count + 1))

# print(grid)
print(ans)

Submission status: Accepted

Solution code:
import sys 
from collections import deque
 
h, w = map(int, sys.stdin.readline().split())
grid = []
for _ in range(h):
    grid.append(list(sys.stdin.readline().strip()))
 
q = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            q.append((0, i, j))
 
while q:
    count, y, x = q.popleft()
    for dy, dx in ((-1, 0), (1, 0), (0, 1), (0, -1)):
        if 0 <= y+dy < h and 0 <= x+dx < w:
            if grid[y+dy][x+dx] == "#":
                continue
            else:
                grid[y+dy][x+dx] = "#"
                q.append((count+1, y+dy, x+dx))
 
print(count)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W = mapint()
As = [list(input()) for _ in range(H)]

from collections import deque
Q = deque()
dist = [[10**18]*W for _ in range(H)]
for h in range(H):
    for w in range(W):
        if As[h][w]=='#':
            Q.append((h, w))
            dist[h][w] = 0

dirc = ((0, 1), (0, -1), (1, 0), (-1, 0))
while Q:
    y, x = Q.popleft()
    for dy, dx in dirc:
        ny, nx = y+dy, x+dx
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if dist[ny][nx]>dist[y][x]+1:
            dist[ny][nx] = dist[y][x]+1
            Q.append((ny, nx))
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, dist[h][w])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]

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

MAP = []

for _ in range(H):
    MAP.append(list(input()))

d = deque()

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

ans = 0

while len(d) != 0:
    x, y, cnt = d.popleft()
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] == '.':
            MAP[nx][ny] = '#'
            d.append([nx, ny, cnt + 1])
            ans = max(ans, cnt + 1)

print(ans)

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    d = [[inf]*w for i in range(h)]

    dy = [0, 1, 0, -1] 
    dx = [1, 0, -1, 0]
 
    que = deque([])
    for i in range(h):
        for j in range(w):
            if s[i][j] == '#':
                que.append((i, j))
                d[i][j] = 0

    ans = 0
    while que:
        p = que.popleft()
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
 
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != '#' and d[ny][nx] == inf:
                que.append((ny,nx))
                d[ny][nx] = d[p[0]][p[1]] + 1
                ans = max(ans, d[ny][nx]) 
    return ans

h, w = MAP()
s = []
for i in range(h):
    s.append(input())
print(bfs())

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


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

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

    while queue:
        h, w = queue.popleft()
        d = dist[h][w]
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            y, x = h + i, w + j
            if dist[y][x] == -1:
                dist[y][x] = d + 1
                queue.append((y, x))

    res = max(map(max, dist))
    return res


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(), "."))

    ans = solve(H, W, A)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def solve(H, W, A):
    WALL = - 10 ** 7
    dist = [[WALL] + [-1] * W + [WALL] for _ in range(H + 2)]
    dist[0] = dist[-1] = [WALL] * (W + 2)

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

    while queue:
        h, w = queue.popleft()
        d = dist[h][w]
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            y, x = h + i, w + j
            if dist[y][x] == -1:
                dist[y][x] = d + 1
                queue.append((y, x))

    res = max(map(max, dist))
    return res


def main():
    H, W = map(int, input().split())
    A = [None] * H
    for i in range(H):
        A[i] = list(input().rstrip())

    ans = solve(H, W, A)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
def bfs(al, h, w):
    q = deque([])
    visited = [ [-1]*w for _ in range(h) ]
    for i in range(h):
        for j in range(w):
            if al[i][j] == '#': 
                q.append((i,j))
                visited[i][j] = 0

    while q:
        i, j = q.popleft()
        for ver, hor in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            ni, nj = i+ver, j+hor
            if ni >= h or nj >= w or ni < 0 or nj < 0:
                continue
            if al[ni][nj] == '.' and visited[ni][nj] == -1:
                visited[ni][nj] = visited[i][j] + 1
                q.append((ni,nj))
    return visited


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

    visited = bfs(al,h,w)
    ans = 0
    for v in visited:
        ans = max(max(v),ans)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
wall = '/'
grid = [[wall] * (w + 2)]
wn = 0

q = deque()
for y in range(1, h+1):
    grid.append([wall] + [c for c in input()] + [wall])
    for x in range(1, w+1):
        if grid[y][x] == '.':
            wn += 1
        if grid[y][x] == '#':
            q.append((y, x, 0))
grid.append([wall] * (w + 2))

move = [(-1, 0), (1, 0), (0, -1), (0, 1)]

while q:
    y, x, i = q.popleft()
    grid[y][x] = '#'
    for dy, dx in move:
        if grid[y + dy][x + dx] == '.':
            grid[y + dy][x + dx] = '#'
            q.append((y + dy, x + dx, i + 1))
    
print(i)

Submission status: Accepted

Solution code:
from collections import deque

h,w=list(map(int,input().split()))
a=[[c for c in input()] for _ in range(h)]
visit=[[0]*w for _ in range(h)]
q=deque()

for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            deque.appendleft(q,(i,j,0))
            visit[i][j]=1
ans=0
while len(q)>0:
    i,j,cnt=deque.pop(q)

    ans=max(ans,cnt)

    for di,dj in [(-1,0),(1,0),(0,-1),(0,1)]:
        ni=i+di
        nj=j+dj
        if 0<=ni<h and 0<=nj<w and visit[ni][nj]==0:
            visit[ni][nj]=1
            deque.appendleft(q,(ni,nj,cnt+1))

print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W = mapint()
As = [list(input()) for _ in range(H)]
dist = [[10**18]*W for _ in range(H)]
dirc = ((-1, 0), (1, 0), (0, -1), (0, 1))

from collections import deque
def bfs(start_lis):
    Q = deque()
    for sy, sx in start_lis:
        dist[sy][sx] = 0
        Q.append((sy, sx))
    while Q:
        y, x = Q.popleft()
        for dy, dx in dirc:
            ny, nx = y+dy, x+dx
            if ny>=H or ny<0 or nx>=W or nx<0:
                continue
            if dist[ny][nx]>dist[y][x]+1:
                dist[ny][nx] = dist[y][x]+1
                Q.append((ny, nx))

start_lis = []
for h in range(H):
    for w in range(W):
        if As[h][w]=='#':
            start_lis.append((h, w))
bfs(start_lis)
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, dist[h][w])
print(ans)

Submission status: Accepted

Solution code:
# 白色マスで４方向のマスに黒マスが一つ以上存在するものを黒にかえる。
# 何回の操作でマスが全て黒マスになるか？
H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
black_list = []
for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            black_list.append((h, w))

count = 0
move = ((0, 1), (1, 0), (-1, 0), (0, -1))
# 広がり方は一点の黒から一定なのでそれを行うことで、計算量を改善できる？
while black_list:
    n_pl = []
    for b in black_list:
        for m in move:
            n_p = (b[0] + m[0], b[1] + m[1])
            if not(n_p[0] < 0 or n_p[1] < 0 or n_p[0] >= H or n_p[1] >= W) and field[n_p[0]][n_p[1]] == ".":
                field[n_p[0]][n_p[1]] = "#"
                n_pl.append(n_p)
    black_list = n_pl
    count += 1
print(count-1)

Submission status: Accepted

Solution code:
from collections import deque
INF=10**18
h,w=map(int,input().split())
e=[input() for _ in range(h)]
d=[[INF]*w for _ in range(h)]
q=deque([])
for i in range(h):
  for j in range(w):
    if e[i][j]=='#':
      q.append((i,j))
      d[i][j]=0
dx=[-1,0,1,0]
dy=[0,-1,0,1]
ans=0
while q:
  x,y=q.popleft()
  for i in range(4):
    nx=x+dx[i]
    ny=y+dy[i]
    if 0<=nx<h and 0<=ny<w and e[nx][ny]=='.' and d[nx][ny]==INF:
      q.append((nx,ny))
      d[nx][ny]=d[x][y]+1
      ans=max(d[nx][ny],ans)
print(ans)

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    H, W = read_ints()
    table = []
    for _ in range(H):
        table.append(list(input()))
    frontier = []
    whites = H*W
    for i in range(H):
        for j in range(W):
            if table[i][j] == '#':
                frontier.append((i, j))
                whites -= 1
    count = 0
    while whites != 0:
        new_frontier = []
        for i, j in frontier:
            for i0, j0 in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                if 0 <= i0 < H and 0 <= j0 < W and table[i0][j0] == '.':
                    table[i0][j0] = '#'
                    whites -= 1
                    new_frontier.append((i0, j0))
        frontier = new_frontier
        count += 1
    return count


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
# 壁あり
A = [['#'] * (W + 2)] +  [['#'] + list(input()) + ['#'] for _ in range(H)] + [['#'] * (W + 2)]

visited = [[True] * (W + 2) for _ in range(H + 2)]
for h in range(1, H + 1):
    for w in range(1, W + 1):
        if A[h][w] == '.':
            visited[h][w] = False

que = []
for h in range(1, H + 1):
    for w in range(1, W + 1):
        if visited[h][w]:
            que.append((h, w))

res = -1
while que:
    q = []
    res += 1
    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        for x, y in que:
            nx, ny = x + dx, y + dy
            if not visited[nx][ny]:
                visited[nx][ny] = True
                q.append((nx, ny))
    que = q

print(res)

Submission status: Accepted

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

task = deque([])
visited = [[0 for _ in range(W)] for _ in range(H)]
cost = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
  for j in range(W):
    if A[i][j] == "#":
      task.append(((i,j),0))
      visited[i][j] = 1
      
black = 0#黒点個数
ans = 0
while task:
  p, c = task.popleft()
  cost[p[0]][p[1]] = c
  ans = max(ans,c)
  i = p[0]
  j = p[1]
  black += 1
  if i > 0 and visited[i-1][j] == 0 and A[i-1][j] == ".":
    task.append(((i-1,j),c+1))
    visited[i-1][j] = 1
  if j > 0 and visited[i][j-1] == 0 and A[i][j-1] == ".":
    task.append(((i,j-1),c+1))
    visited[i][j-1] = 1
  if i < H-1 and visited[i+1][j] == 0 and A[i+1][j] == ".":
    task.append(((i+1,j),c+1))
    visited[i+1][j] = 1
  if j < W-1 and visited[i][j+1] == 0 and A[i][j+1] == ".":
    task.append(((i,j+1),c+1))
    visited[i][j+1] = 1
#print(cost)    
print(ans if black == H*W else -1)

Submission status: Accepted

Solution code:
from collections import deque

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

d = deque()
dist = [[-1] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            d.append([i, j])
            dist[i][j] = 0

dy = [-1, 0, 1, 0]
dx = [0, -1, 0, 1]
while d:
    x1, y1 = d.popleft()

    for i in range(4):
        x2 = x1 + dx[i]
        y2 = y1 + dy[i]

        if 0 <= x2 < h and 0 <= y2 < w and dist[x2][y2] == -1:
            d.append([x2, y2])
            dist[x2][y2] = dist[x1][y1] + 1

print(max(list(map(lambda x: max(x), dist))))

Submission status: Accepted

Solution code:
from collections import deque
H, W = list(map(int, input().split()))

g = []

for _ in range(H):
    g.append(list(input()))

dist = [[-1 for _ in range(W)] for _ in range(H)]
queue = deque()

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

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

while len(queue) > 0:
    now_x, now_y = queue.popleft()

    for dx_, dy_ in zip(dx, dy):
        adj_x = now_x + dx_
        adj_y = now_y + dy_

        if (not 0 <= adj_x < W) or (not 0 <= adj_y < H):
            continue

        if g[adj_y][adj_x] == "#" :
            continue

        if g[adj_y][adj_x] == ".":
            g[adj_y][adj_x] = "#"
            queue.append((adj_x, adj_y))
            dist[adj_y][adj_x] = dist[now_y][now_x] + 1

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

h,w = MI()
a = [list(input()) for i in range(h)]
d = deque()
dx = [1,-1,0,0]
dy = [0,0,1,-1]
dist = [[-1]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            d.append([i,j])
            dist[i][j] = 0
while d:
    s = d.popleft()
    x= s[0]
    y= s[1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= h or ny >= w:
            continue
        else:
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                d.append([nx,ny])
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 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

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque

    h, w = map(int, readline().split())
    que = deque()
    grid = [[] for _ in range(h + 2)]
    grid[0] = ["#"] * (w + 2)
    grid[-1] = ["#"] * (w + 2)

    for row in range(1, h + 1):
        s = input()
        for col, c in enumerate(s, 1):
            if c == "#":
                que.append((row, col, 0))
        grid[row] = ["#"] + list(s) + ["#"]

    cnt = 0

    while que:
        cr, cc, cnt = que.popleft()
        if grid[cr + 1][cc] == ".":
            que.append((cr + 1, cc, cnt + 1))
            grid[cr + 1][cc] = "#"
        if grid[cr - 1][cc] == ".":
            que.append((cr - 1, cc, cnt + 1))
            grid[cr - 1][cc] = "#"
        if grid[cr][cc + 1] == ".":
            que.append((cr, cc + 1, cnt + 1))
            grid[cr][cc + 1] = "#"
        if grid[cr][cc - 1] == ".":
            que.append((cr, cc - 1, cnt + 1))
            grid[cr][cc - 1] = "#"
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque, defaultdict

    h, w = map(int, readline().split())
    que = deque()
    grid = [["#"] * (w + 2)]

    for row in range(1, h + 1):
        s = input()
        for col, c in enumerate(s, 1):
            if c == "#":
                que.append((row, col, 0))
        grid.append(["#"] + list(s) + ["#"])

    grid.append(["#"] * (w + 2))
    direction = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    cnt = 0

    while que:
        cr, cc, cnt = que.popleft()
        for mr, mc in direction:
            nr, nc = cr + mr, cc + mc
            if grid[nr][nc] == ".":
                que.append((nr, nc, cnt + 1))
                grid[nr][nc] = "#"

    print(cnt)


if __name__ == '__main__':
    main()