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:
r,c=map(int,input().split())
meiro=[list(input()) for i in range(r)]
#迷路の黒マスを数えてキューに入れる作業
from collections import deque
quest=deque([])#最初に見る場所
#迷路の外を＃で囲む
for i in range(r):
    meiro[i].insert(c,"#")
    meiro[i].insert(0,"#")
meiro.insert(0,["#"]*(c+2))
meiro.append(["#"]*(c+2))
#print(meiro)
tesuu=[[-1]*(c+2) for i in range(r+2)]
for i in range(1,r+1):
    for j in range(1,c+1):
        if meiro[i][j]=="#":
            quest.append([i,j])
            tesuu[i][j]=0
#print(quest)

idou=[[0,1],[0,-1],[1,0],[-1,0]]
#print(tesuu)
while len(quest)!=0:
    see=quest.popleft()
    for i in idou:
        if meiro[see[0]+i[0]][see[1]+i[1]]=="#":
            continue
        if tesuu[see[0]+i[0]][see[1]+i[1]]!=-1:
            continue
        quest.append([see[0]+i[0],see[1]+i[1]])
        tesuu[see[0]+i[0]][see[1]+i[1]]=tesuu[see[0]][see[1]]+1
te=[]
for i in range(r+2):
    te.extend(tesuu[i])
print(max(te))

Submission status: Accepted

Solution code:
from collections import deque

H,W=map(int,input().split())
field=[]
spos=deque([])
for i in range(H):
  s=list(input())
  for j in range(W):
    if s[j]=="#":
      spos.append((j,i))
  field.append(s)
  

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

ans=-1
while spos:
  for _ in range(len(spos)):
    x,y=spos.popleft()
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if nx<0 or nx>=W or ny<0 or ny>=H:
        pass
      elif field[ny][nx]==".":
        field[ny][nx]="#"
        spos.append((nx,ny))
  ans+=1

print(ans)

Submission status: Accepted

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

l=[input() for _ in range(H)]


def bfs(H,W,l):
  ans=0
  que=deque()
  count=[[-1]*W for _ in range(H)]
  num=H*W
  dx=[1,-1,0,0]
  dy=[0,0,1,-1]
  for i in range(H):
    for j in range(W):
      if l[i][j]=='#':
        count[i][j]=0
        que.append([i,j])
        num-=1
  while num>0:
    x,y=que.popleft()
    for k in range(4):
      a, b=x+dx[k], y+dy[k]
      if a<0 or a>=H or b<0 or b>=W or count[a][b]!=-1:
        continue
      else:
        count[a][b]=count[x][y]+1
        que.append([a,b])
        num-=1
  for i in range(H):
    ans=max(ans,max(count[i]))
  return ans
print(bfs(H,W,l))

Submission status: Accepted

Solution code:
from scipy.ndimage import distance_transform_cdt
 
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
n = [[1 if x == "." else 0 for x in row] for row in a]
 
distance = distance_transform_cdt(n, metric='taxicab')
res = distance.max()
print(res)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
g=[]
for i in range(h):
    g.append(list(input()))
q=[]
v=[[0 for i in range(w)] for j in range(h)]
for i in range(h):
    for j in range(w):
        if g[i][j]=='#':
            q.append([i,j])
            v[i][j]=1
ans=0
while len(q)>0:
    tmp=[]
    for i in q:
        a=i[0]
        b=i[1]
        if a==0:
            hi=[1]
        elif a==h-1:
            hi=[-1]
        else:
            hi=[1,-1]
        if h==1:
            hi=[]
        if b==0:
            wi=[1]
        elif b==w-1:
            wi=[-1]
        else:
            wi=[1,-1]
        if w==1:
            wi=[]
        for c in hi:
            if v[a+c][b]==0:
                tmp.append([a+c,b])
                v[a+c][b]=1
        for d in wi:
            if v[a][b+d]==0:
                tmp.append([a,b+d])
                v[a][b+d]=1
    q=tmp
    ans+=1
print(ans-1)

Submission status: Accepted

Solution code:
from collections import deque

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

queue = deque([])
Distance = [-1]*(h*w)

for i in range(h):
    for j in range(w):
        if A[i*w+j]=='#':
            queue.append([i,j])
            Distance[i*w+j] = 0

ans = 0

while queue:
    x,y = queue.popleft()
    d = Distance[x*w+y]
    if x!=0 and Distance[(x-1)*w+y] == -1:
            queue.append([x-1,y])
            ans = Distance[(x-1)*w+y] = d+1
    if x!=h-1 and Distance[(x+1)*w+y] == -1:
            queue.append([x+1,y])
            ans = Distance[(x+1)*w+y] = d+1
    if y!=0 and Distance[x*w+y-1] == -1:
            queue.append([x,y-1])
            ans = Distance[x*w+y-1] = d+1
    if y!=w-1 and Distance[x*w+y+1] == -1:
            queue.append([x,y+1])
            ans = Distance[x*w+y+1] = d+1

print(ans)

Submission status: Accepted

Solution code:
def main():
    from collections import deque

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

    queue = deque([])
    Distance = [-1]*(h*w)

    for i in range(h):
        for j in range(w):
            if A[i*w+j]=='#':
                queue.append([i,j])
                Distance[i*w+j] = 0

    ans = 0

    while queue:
        x,y = queue.popleft()
        d = Distance[x*w+y]
        if x!=0 and Distance[(x-1)*w+y] == -1:
                queue.append([x-1,y])
                ans = Distance[(x-1)*w+y] = d+1
        if x!=h-1 and Distance[(x+1)*w+y] == -1:
                queue.append([x+1,y])
                ans = Distance[(x+1)*w+y] = d+1
        if y!=0 and Distance[x*w+y-1] == -1:
                queue.append([x,y-1])
                ans = Distance[x*w+y-1] = d+1
        if y!=w-1 and Distance[x*w+y+1] == -1:
                queue.append([x,y+1])
                ans = Distance[x*w+y+1] = d+1

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
# from copy import deepcopy, copy

import queue
from collections import deque



def main():
    high, width = map(int, input().split())
    data = [list(input()) for i in range(high)]
    for i in range(high):
        for j in range(width):
            if data[i][j] == '.':
                data[i][j] = 10 ** 5
            else:
                data[i][j] = 0

    for i in range(high):
        for j in range(1, width):
            data[i][j] = min(data[i][j], data[i][j - 1] + 1)

    for i in range(high):
        for j in range(width - 1)[::-1]:
            data[i][j] = min(data[i][j], data[i][j + 1] + 1)

    for j in range(width):
        for i in range(1, high):
            data[i][j] = min(data[i][j], data[i - 1][j] + 1)

    for j in range(width):
        for i in range(high - 1)[::-1]:
            data[i][j] = min(data[i][j], data[i + 1][j] + 1)


    ans = 0
    for i in range(high):
        ans = max(ans, max(data[i]))

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

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

Q = []
V = [[0] * w for i in range(h)]
D = [[0] * 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])
            V[i][j] = 1
            D[i][j] = 0


st = 0
while st < len(Q):
    for i in [[-1,0], [1,0], [0,-1], [0,1]]:
        x = Q[st][0] + i[0]
        y = Q[st][1] + i[1]
        if 0 <= x < h and 0 <= y < w and V[x][y] == 0:
            V[x][y] = 1
            Q.append([x, y, Q[st][2]+1])
            D[x][y] = Q[st][2]+1
    st += 1

print(max([max(i) for i in D]))

Submission status: Accepted

Solution code:
def main():
    H, W = (int(i) for i in input().split())
    A = [input() for j in range(H)]
    from collections import deque
    st = deque()
    dist = [[-1]*W for i in range(H)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#': 
                st.append((h,w))
                dist[h][w] = 0
    
    def bfs():
        ans = 0
        que = st
        d = ((1,0),(0,1),(-1,0),(0,-1))

        while que:
            uy,ux = que.popleft()
            for dy, dx in d:
                next_y = uy + dy
                next_x = ux + dx
                if not(0 <= next_y < H and 0 <= next_x < W): continue
                if dist[next_y][next_x] != -1: continue
                if A[next_y][next_x] == '#': continue
                dist[next_y][next_x] = dist[uy][ux] + 1
                ans = max(ans, dist[next_y][next_x])
                que.append((next_y, next_x))
        return ans
    
    print(bfs())

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import sys
# https://atcoder.jp/contests/agc033/submissions/6021787
buf = sys.stdin.buffer
H,W = map(int,buf.readline().split())
# +1周分だけ
black = np.zeros((H+2,W+2),dtype=np.bool)
# \nがあることに注意
black[1:-1,1:] = (np.frombuffer(buf.read(H*(W+1)),dtype='S1') == b'#').reshape(H,W+1)

INF = 10 ** 4
dist = np.zeros((H,W),dtype=np.int16)
# .のところは０それ以外はINFで初期化
dist[~black[1:-1,1:-1]] = INF
# 右、左、下、上と展開させていく感じ
for n in range(1,H):
    np.minimum(dist[n-1]+1,dist[n],out=dist[n])
for n in range(H-2,-1,-1):
    np.minimum(dist[n+1]+1,dist[n],out=dist[n])
for n in range(1,W):
    np.minimum(dist[:,n-1]+1,dist[:,n],out=dist[:,n])
for n in range(W-2,-1,-1):
    np.minimum(dist[:,n+1]+1,dist[:,n],out=dist[:,n])

print(dist.max())

Submission status: Accepted

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions
from operator import itemgetter

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

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

A = []
for i in range(H):
	A.append(input())

num = [[0]*W for _ in range(H)]
black_list = deque()
for i in range(H):
	for j in range(W):
		if A[i][j] == ".":
			num[i][j] = 1000000
		else:
			black_list.append((i, j))
dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]

max_num = 0
while len(black_list) > 0:
	i, j = black_list.popleft()
	for n in range(4):
		x = i + dxy[n][0]
		y = j + dxy[n][1]
		if x < H and y < W and 0 <= x and 0 <= y:
			if num[x][y] > 10000:
				num[x][y] = num[i][j] + 1
				black_list.append((x, y))
				max_num = max(max_num, num[x][y])

print(max_num)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
a = [['*' for _ in range(w+2)]]
for _ in range(h):
    a.append(['*'] + list(input()) + ['*'])
a.append(['*' for _ in range(w+2)])

q = set()

def encode(i, j):
    return i*w + j-1

def decode(x):
    i = x // w
    j = x % w + 1
    return [i, j]

for i in range(1, h+1):
    for j in range(1, w+1):
        if a[i][j] == '#':
            q.add(encode(i, j))

for ans in range(h+w):
    nq = set()
    for x in q:
        i, j = decode(x)
        for k in [-1,1]:
            if a[i+k][j] == '.':
                nq.add(encode(i+k, j))
                a[i+k][j] = '#'
        for k in [-1,1]:
            if a[i][j+k] == '.':
                nq.add(encode(i, j+k))
                a[i][j+k] = '#'
    if len(nq) == 0:
        print(ans)
        exit()
    else:
        q = set()
        q = q | nq

Submission status: Accepted

Solution code:
h, w = [ int(v) for v in input().split() ]
field = []
search_list = []
adjust_list = ((0,1),(0,-1),(1,0),(-1,0))

for i in range(h):
    line = list(input())
    field.append(line)
    for j, v in enumerate(line):
        if v == "#":
            search_list.append((i,j))

t = 0
while search_list:
    new_search_list = []
    for i in search_list:
        for j in adjust_list:
            if 0 <= i[0]+j[0] < h and 0 <= i[1]+j[1] < w:
                if field[i[0]+j[0]][i[1]+j[1]] == ".":
                    field[i[0]+j[0]][i[1]+j[1]] = "#"
                    new_search_list.append((i[0]+j[0], i[1]+j[1]))
    search_list = new_search_list
    if search_list:
        t += 1

print(t)

Submission status: Accepted

Solution code:
from collections import deque


def bfs(h, w, board, visited):
    queue = deque([])
    for i in range(h):
        for j in range(w):
            if board[i][j] == "#":
                queue.append([i, j])
                visited[i][j] = 0
    ans = 0
    while queue:
        y, x = queue.popleft()
        for i, j in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            yn, xn = y+i, x+j
            if yn >= h or xn >= w or yn < 0 or xn < 0:
                continue
            if visited[yn][xn] == -1 and board[yn][xn] == ".":
                visited[yn][xn] = visited[y][x] + 1
                queue.append([yn, xn])
                ans = max(ans, visited[yn][xn])

    return ans


def main():
    h, w = map(int, input().split())
    board = [input() for _ in range(h)]
    visited = [[-1 for _ in range(w)] for _ in range(h)]
    print(bfs(h, w, board, visited))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

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

def bfs(A):
    d = [[0,1],[0,-1],[1,0],[-1,0]]
    used = [[False]*W for _ in range(H)]
    q = []
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                used[i][j] = True
                q.append([i,j])
    c = 0
    while q:
        q1 = []
        count_flag = False
        for place in q:
            for move in d:
                new_x, new_y = place[0]+move[0], place[1]+move[1]
                if 0<=new_x<H and 0<=new_y<W:
                    if used[new_x][new_y]==False:
                        used[new_x][new_y] = True
                        q1.append([new_x,new_y])
                        count_flag = True
        q = q1
        if count_flag:
            c += 1
    return c

H,W = II()
A = [list(map(str, input())) for _ in range(H)]
print(bfs(A))

Submission status: Accepted

Solution code:
from collections import deque


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

    q = deque()

    arrived = [[True] * (w + 2)] + \
              [[True] + [False] * w + [True] for _ in range(h)] + \
              [[True] * (w + 2)]

    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                q.append((i+1, j+1))
                arrived[i+1][j+1] = True

    ans = 0
    while q:
        ans += 1
        pop_max = len(q)
        cnt = 0
        while cnt != pop_max:
            i, j = q.popleft()
            if not arrived[i-1][j]:
                arrived[i-1][j] = True
                q.append((i-1, j))

            if not arrived[i+1][j]:
                arrived[i+1][j] = True
                q.append((i+1, j))

            if not arrived[i][j-1]:
                arrived[i][j-1] = True
                q.append((i, j-1))

            if not arrived[i][j+1]:
                arrived[i][j+1] = True
                q.append((i, j+1))

            cnt += 1

    ans -= 1
    print(ans)


def main():
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque


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

    q = deque()

    arrived = [[True] * (w + 2)] + \
              [[True] + [False] * w + [True] for _ in range(h)] + \
              [[True] * (w + 2)]

    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                q.append([i+1, j+1])
                arrived[i+1][j+1] = True

    ans = 0
    while q:
        ans += 1
        pop_max = len(q)
        cnt = 0
        while cnt != pop_max:
            i, j = q.popleft()
            if not arrived[i-1][j]:
                arrived[i-1][j] = True
                q.append([i-1, j])

            if not arrived[i+1][j]:
                arrived[i+1][j] = True
                q.append([i+1, j])

            if not arrived[i][j-1]:
                arrived[i][j-1] = True
                q.append([i, j-1])

            if not arrived[i][j+1]:
                arrived[i][j+1] = True
                q.append([i, j+1])

            cnt += 1

    ans -= 1
    print(ans)


def main():
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from scipy.ndimage import distance_transform_cdt


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

    sq = [[1 if e == "." else 0 for e in row] for row in a]

    cnt = distance_transform_cdt(sq, metric="taxicab")

    print(cnt.max())


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import array
import itertools
from collections import defaultdict, deque


def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


def input_ints():
    return map(int, input().split())


def solve():
    def fill(queue):
        footsteps = [[None] * width for _ in range(height)]

        for x, y in queue:
            footsteps[y][x] = 0

        s = 0
        while queue:
            queue2 = deque()
            s += 1
            while queue:
                x, y = queue.popleft()

                if x > 0 and footsteps[y][x - 1] is None:
                    queue2.append((x - 1, y))
                    footsteps[y][x - 1] = s
                if x < width - 1 and footsteps[y][x + 1] is None:
                    queue2.append((x + 1, y))
                    footsteps[y][x + 1] = s
                if y > 0 and footsteps[y - 1][x] is None:
                    queue2.append((x, y - 1))
                    footsteps[y - 1][x] = s
                if y < height - 1 and footsteps[y + 1][x] is None:
                    queue2.append((x, y + 1))
                    footsteps[y + 1][x] = s

            queue = queue2

        return s - 1

    height, width = tuple(input_ints())
    field = [input() for _ in range(height)]
    queue = deque()

    for y, line in enumerate(field):
        for x, c in enumerate(line):
            if c == '#':
                queue.append((x, y))
    # queue.append((10, 10))


    return fill(queue)


def main():
    print(solve())


main()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
b = [[0] * w for _ in range(h)]
q = []

for i in range(h):
    for j, m in enumerate(input()):
        if m == "#":
            q.append((i, j))
            b[i][j] = 1

cnt = -1

while q:
    nq = []
    for y, x in q:
        if y > 0:
            if not b[y-1][x]:
                b[y-1][x] = 1
                nq.append((y-1, x))
        if y < h-1:
            if not b[y+1][x]:
                b[y+1][x] = 1
                nq.append((y+1, x))
        if x > 0:
            if not b[y][x-1]: 
                b[y][x-1] = 1
                nq.append((y, x-1))
        if x < w-1:
            if not b[y][x+1]: 
                b[y][x+1] = 1
                nq.append((y, x+1))
    
    q = nq    
    cnt += 1
    
print(cnt)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,w = LI()
maze = [list(input()) for _ in range(h)]
check = [[True]*w for _ in range(h)]
dx,dy = [0,1,0,-1],[1,0,-1,0]
que = deque()
for i in range(h):
    for j in range(w):
        if maze[i][j] == '#':
            check[i][j] = False
            que.append((j,i))
res = 0
while que:
    que2 = deque(que)
    que = deque()
    flg = False
    while que2:
        x,y = que2.popleft()
        for i in range(4):
            nx,ny = x + dx[i], y + dy[i]
            if 0 <= nx < w and 0 <= ny < h:
                if check[ny][nx]:
                    check[ny][nx] = False
                    que.append((nx,ny))
                    flg = True
    if flg:
        res += 1
print(res)

Submission status: Accepted

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

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

ans=0
while q:
    nq=deque()
    while True:        
        y,x=q.popleft()
        for dy,dx in ((1,0),(-1,0),(0,1),(0,-1)):
            ny=dy+y
            nx=dx+x
            if 0<=ny<h and 0<=nx<w and a[ny][nx]!='#':
                a[ny][nx]='#'
                nq.append((ny,nx))
        if not q:
            ans+=1
            q=nq
            break
print(ans-1)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int,input().split())
graph = []
finished = [[False for _ in range(w)] for _ in range(h)]
y = [0, 0, 1,-1]
x = [1,-1, 0, 0]
q = deque([])
for i in range(h):
    a = input()
    graph.append(a)
    for j in range(w):
        if a[j] == "#":
            q.append((i,j,0))
while q:
    c = q.popleft()
    for i in range(4):
        nh = c[0]+y[i]
        nw = c[1]+x[i]
        if nh < 0 or nh >= h or nw < 0 or nw >= w or graph[nh][nw] == "#" or finished[nh][nw]:continue
        finished[nh][nw] = True
        q.append((nh,nw,c[2]+1))
print(c[2])

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
def main():
    H, W = map(int, input().split())
    m = []
    m.append([True] * (W + 2))
    for _ in range(H):
        m.append([True] + [c == '#' for c in input()] + [True])
    m.append([True] * (W + 2))
    queue = []
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if m[i][j]:
                queue.append((i, j))
    ans = -1
    while queue:
        ans += 1
        tmp = []
        for x, y in queue:
            if not m[x - 1][y]:
                m[x - 1][y] = True
                tmp.append((x - 1, y))
            if not m[x + 1][y]:
                m[x + 1][y] = True
                tmp.append((x + 1, y))
            if not m[x][y - 1]:
                m[x][y - 1] = True
                tmp.append((x, y - 1))
            if not m[x][y + 1]:
                m[x][y + 1] = True
                tmp.append((x, y + 1))
        queue = tmp
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import copy
 
def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]
 
 
    # スタート地点をqueueに追加
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])
 
    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))
 
        if nque:
            que = copy.copy(nque)
        else:
            break
 
    print(count - 1)
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# AGC033A - Darker and Darker
# https://docs.scipy.org/doc/scipy/reference/generated/scipy.ndimage.distance_transform_cdt.html
from scipy.ndimage import distance_transform_cdt as dist


def main():
    H, W, *A = open(0).read().split()
    B = [[1 if i == "." else 0 for i in a] for a in A]
    D = dist(B, metric="taxicab")
    ans = D.max()
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# AGC033A - Darker and Darker
# https://docs.scipy.org/doc/scipy/reference/generated/scipy.ndimage.distance_transform_cdt.html
from scipy.ndimage import distance_transform_cdt as dist


def main():
    """
    distance_transform_cdt:
        orig     taxicab / chessboard
        1 1 1     2 1 2      1 1 1
        1 0 1 ->  1 0 1      1 0 1
        1 1 1     2 1 2      1 1 1
    """
    H, W, *A = open(0).read().split()
    B = [[1 if i == "." else 0 for i in a] for a in A]
    D = dist(B, metric="taxicab")
    ans = D.max()
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

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

    INF = int(1e7)
    a = np.array([list(map(lambda x: 0 if x=="#" else INF, list(input().strip()))) for i in range(H)])

    for i in range(H-1):
        a[i+1] = np.minimum(a[i] + 1, a[i+1])
    for i in range(H-1, 0, -1):
        a[i-1] = np.minimum(a[i] + 1, a[i-1])
    
    for i in range(W-1):
        a[:, i+1] = np.minimum(a[:, i] + 1, a[:, i+1])
    for i in range(W-1, 0, -1):
        a[:, i-1] = np.minimum(a[:, i] + 1, a[:, i-1])

    print(np.max(a))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

H,W = map(int, input().split())
check = []
b = [[True]*(W+2)]

for i in range(H):
    s = input().strip()
    b.append([True] + [False]*W + [True])
    for j,c in enumerate(s):
        if c == '#':
            check.append((i+1,j+1))
            b[i+1][j+1] = True
b.append([True]*(W+2))

t = 0
while check:
    tmp = []
    for i,j in check:
        if not b[i-1][j]:
            b[i-1][j] = True
            tmp.append((i-1,j))
        if not b[i][j-1]:
            b[i][j-1] = True
            tmp.append((i,j-1))
        if not b[i][j+1]:
            b[i][j+1] = True
            tmp.append((i,j+1))
        if not b[i+1][j]:
            b[i+1][j] = True
            tmp.append((i+1,j))
    check = tmp
    t += 1

print(t-1)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
A = []
for i in range(H):
  A.append(input())
#print(A)

INF = 10000
S = [[INF for _ in range(W)] for _ in range(H)]
for i in range(H):
  flag = False
  for j in range(W):
    if A[i][j] == '#':
      flag  = True
      d = 0
      S[i][j] = 0
    if flag and A[i][j] == '.':
      d += 1
      S[i][j] = min(d,S[i][j])
  flag = False
  for j in range(W-1,-1,-1):
    if A[i][j] == '#':
      flag  = True
      d = 0
      S[i][j] = 0
    if flag and A[i][j] == '.':
      d += 1
      S[i][j] = min(d,S[i][j])
for j in range(W):
  flag = False
  for i in range(H):
    if S[i][j] < INF:
      flag = True
    if flag and i > 0 and A[i][j] == '.':
      S[i][j] = min(S[i][j],S[i-1][j]+1)
  flag = False
  for i in range(H-1,-1,-1):
    if S[i][j] < INF:
      flag = True
    if flag and i < H-1 and A[i][j] == '.':
      S[i][j] = min(S[i][j],S[i+1][j]+1)
#print(S)

ans = 0
for s in S:
  ans = max(ans,max(s))
print(ans)

Submission status: Accepted

Solution code:
def gen():
    print("1000 1000")
    print("#"+"."*999)
    for i in range(1000-1):
        print("."*1000)

def main():
    from collections import deque
    import sys
    from heapq import heappush, heappop
    input = sys.stdin.readline
    H, W = map(int, input().split())
    D = [None]*H
    Q = deque()
    for h in range(H):
        D[h] = [10e10]*W
        l = input()
        for w in range(W):
            if l[w] == "#":
                D[h][w] = 0
                Q.append((h, w))
    m = 0
    while Q:
        h, w = Q.popleft()
        alt = D[h][w] + 1
        for dx, dy in [(-1,0), (1,0), (0,-1), (0, +1)]:
            h1, w1 = h+dx, w+dy
            if 0 <= h1 < H and 0 <= w1 < W:
                if D[h1][w1] > alt:
                    D[h1][w1] = alt
                    m = max(m, alt)
                    Q.append((h1, w1))

    print(m)
main()