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:
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
p = [(i, j) for i in range(h) for j in range(w) if a[i][j] == '#']
d = (-1, 0), (1, 0), (0, -1), (0, 1)
r = -1
while p:
    r += 1
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if 0 <= di < h and 0 <= dj < w and a[di][dj] == '.':
                a[di][dj] = '#'
                s.append((di, dj))
    p = s
print(r)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
a = [['#'] * (w + 2)] * 2
a[1: 1] = [list('#' + input() + '#') for _ in range(h)]
p = [(i, j) for i in range(1, h + 1) for j in range(1, w + 1) if a[i][j] == '#']
d = (-1, 0), (1, 0), (0, -1), (0, 1)
r = -1
while p:
    r += 1
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if a[di][dj] == '.':
                a[di][dj] = '#'
                s.append((di, dj))
    p = s
print(r)

Submission status: Accepted

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H, W):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


H, W = read_ints()
A = read_map(H, W)

from itertools import product
from collections import deque


# 開始地点
start = []
for i, a in enumerate(A):
    for j, aa in enumerate(a):
        if aa == '#':
            start.append((i, j))


# 探索の準備
mvx = (1, 0, -1, 0)
mvy = (0, 1, 0, -1)
visited = [[False for _ in range(W)] for _ in range(H)]

n_white = W*H
que = deque([(si, sj, 0) for si, sj in start])

for si, sj in start:
    visited[si][sj] = True

# 幅優先探索
while que:
    y, x, cost = que.popleft()
    # 白マスの数の管理
    n_white -= 1
    if n_white == 0:
        ans = cost
        break

    for dy, dx in zip(mvy, mvx):
        y_new, x_new = y + dy, x + dx
        # 探索に含めない条件
        if not (-1 < y_new < H) or not (-1 < x_new < W):
            continue
        if visited[y_new][x_new]:
            continue

        # 探索に追加してあげる
        que.append((y_new, x_new, cost + 1))
        visited[y_new][x_new] = True


print(cost)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
a = [['#'] * (w + 2)] * 2
a[1: 1] = (list('#' + input() + '#') for _ in range(h))
p = [(i, j) for i in range(1, h + 1) for j in range(1, w + 1) if a[i][j] == '#']
d = (-1, 0), (1, 0), (0, -1), (0, 1)
r = -1
while p:
    r += 1
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if a[di][dj] == '.':
                a[di][dj] = '#'
                s.append((di, dj))
    p = s
print(r)

Submission status: Accepted

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

for ln in range(h):
    line = list(input().rstrip())
    data.append(line)
    for r, letter in enumerate(line):
        if letter == '#':
            que.append((ln, r))

count = 0
while len(que) > 0:
    count += 1
    next = deque()
    while len(que) > 0:
        row, col = que.popleft()
        for r, c in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
            if 0 <= r < h and 0 <= c < w and data[r][c] == '.':
                next.append((r, c))
                data[r][c] = '#'
    que = next

print(count - 1)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
rb = [['#'] * (w + 2)]
a = rb + [list('#' + input() + '#') for _ in range(h)] + rb
p = [(i, j) for i in range(1, h + 1) for j in range(1, w + 1) if a[i][j] == '#']
d = (-1, 0), (1, 0), (0, -1), (0, 1)
r = -1
while p:
    r += 1
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if a[di][dj] == '.':
                a[di][dj] = '#'
                s.append((di, dj))
    p = s
print(r)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
a = [['#'] * (w + 2)] * 2
a[1: 1] = (list('#' + input() + '#') for _ in range(h))
p = [(i, j) for i in range(1, h + 1) for j in range(1, w + 1) if a[i][j] == '#']
d = (-1, 0), (1, 0), (0, -1), (0, 1)
r = -1
while p:
    r += 1
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if a[di][dj] == '.':
                a[di][dj] = '#'
                s.append((di, dj))
    p = s
print(r)

Submission status: Accepted

Solution code:
from collections import deque

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

# input black cells
black_cells = []

for h in range(H):
    line = list(input())
    for w in range(W):
        if line[w] == "#":
            black_cells.append(h * W + w)


def r(p):
    # 追加したもののリスト
    q_list = []
    h = p // W
    w = p % W
    # 上に追加
    if h != 0:
        q_list.append(p - W)
    # 下に追加
    if h != H - 1:
        q_list.append(p + W)
    # 左に追加
    if w != 0:
        q_list.append(p - 1)
    # 右に追加
    if w != W - 1:
        q_list.append(p + 1)
    return q_list


# 距離のmax は1999
d = [2000] * (H * W)
for i in black_cells:
    d[i] = 0

# BFS like dijkstra
queue = deque(black_cells)
while len(queue) > 0:
    p = queue.popleft()
    for q in r(p):
        # 既存の黒の隣なら +1
        if d[q] > d[p] + 1:
            d[q] = d[p] + 1
            queue.append(q)

print(max(d))

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
INF = H * W
A = [input() for x in range(H)]
used = [[False] * W for x in range(H)]

q = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            q.append([i, j])
            used[i][j] = True

max_dist = 0
counter = 0
depth = -1
while counter != INF:
    # print(q)
    # print(counter)
    for i in range(len(q) - counter):
        item = q[counter]

        if item[0] > 0 and not used[item[0]-1][item[1]]:
            q.append([item[0] - 1, item[1]])
            used[item[0] - 1][item[1]] = True
        if item[1] > 0 and not used[item[0]][item[1] - 1]:
            q.append([item[0], item[1] - 1])
            used[item[0]][item[1] - 1] = True
        if item[0] < H - 1 and not used[item[0] + 1][item[1]]:
            q.append([item[0] + 1, item[1]])
            used[item[0] + 1][item[1]] = True
        if item[1] < W - 1 and not used[item[0]][item[1] + 1]:
            q.append([item[0], item[1] + 1])
            used[item[0]][item[1] + 1] = True
        counter += 1
    depth += 1

print(depth)

Submission status: Accepted

Solution code:
import numpy as np

def solve():
    H,W=map(int,input().split(' '))
    max_value = H+W
    values =[]
    for i in range(H):
      values.append([0 if i == '#' else max_value for i in list(input())])
    values = np.array(values)

    for x in range(W-1):
        values[:,x+1] = np.minimum(values[:,x]+1,values[:,x+1])
    for x in range(W-1,0,-1):
        values[:,x-1] = np.minimum(values[:,x-1],values[:,x]+1)
    for x in range(H-1):
        values[x+1,:] = np.minimum(values[x,:]+1,values[x+1,:])
    print('')
    for x in range(H-1,0,-1):
        values[x-1,:] = np.minimum(values[x,:]+1,values[x-1,:])
    print(np.max(values))
solve()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
rb = [['#'] * (w + 2)]
a = rb + [list('#' + input() + '#') for _ in range(h)] + rb
p = [(i, j) for i in range(1, h + 1) for j in range(1, w + 1) if a[i][j] == '#']
d = (-1, 0), (1, 0), (0, -1), (0, 1)
r = -1
while p:
    r += 1
    s = []
    for di, dj in d:
        for i, j in p:
            i += di
            j += dj
            if a[i][j] == '.':
                a[i][j] = '#'
                s.append((i, j))
    p = s
print(r)

Submission status: Accepted

Solution code:
H, W = tuple(map(int, input().split()))
func = (lambda x: 0 if x == "#" else -1)
func_in = (lambda h, w: 0 <= h < H and 0 <= w < W)
P = [[func(i) for i in input()] for i in range(H)]

queue_set = set()
zeros = set()
for h in range(H):
    for w in range(W):
        if P[h][w] == 0:
            zeros.add((h)*W+w)
            for dh, dw in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                if func_in(h+dh, w+dw) and P[h+dh][w+dw] == -1:
                    queue_set.add((h+dh)*W+w+dw)
m = 0

queue = [[q // W, q % W, 0] for q in queue_set]
queue_set |= zeros
idx = 0
cnt = 0
while len(queue) > idx:
    h, w, cnt = queue[idx]
    idx += 1
    cnt += 1
    P[h][w] = cnt
    a = 0
    for dh, dw in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        if func_in(h+dh, w+dw) and (h+dh)*W+w+dw not in queue_set:
            queue += [[h + dh, w + dw, cnt]]
            queue_set.add((h+dh)*W+w+dw)
print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


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


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, A):
    cost = [[-1] * W for _ in range(H)]
    bq = deque()
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                bq.append((i, j))
                cost[i][j] = 0

    while bq:
        i, j = bq.popleft()
        c = cost[i][j]
        if i > 0 and cost[i-1][j] == -1:
            cost[i-1][j] = c + 1
            bq.append((i-1, j))

        if i < H-1 and cost[i+1][j] == -1:
            cost[i+1][j] = c + 1
            bq.append((i+1, j))

        if j > 0 and cost[i][j-1] == -1:
            cost[i][j-1] = c + 1
            bq.append((i, j-1))

        if j < W-1 and cost[i][j+1] == -1:
            cost[i][j+1] = c + 1
            bq.append((i, j+1))

    return max(map(max, cost))


def main():
    H, W = read_int_n()
    A = [read_str() for _ in range(H)]
    print(slv(H, W, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
from scipy.ndimage.morphology import distance_transform_cdt

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

a = np.array([[(ai[j] != "#") for j in range(w)] for ai in a])
d = distance_transform_cdt(a, metric="taxicab").max()
print(d)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
H, W = map(int, input().split())

g = [[True] * (W+2)]
for _ in range(H):
    g.append([True] + [x == '#' for x in input()] + [True])
g.append([True] * (W+2))

l = []
for i in range(1, H+1):
    for j in range(1, W+1):
        if g[i][j]:
            l.append((i, j))

c = 0
while l:
    ll = []
    for i,j in l:
        if not g[i+1][j]:
            g[i+1][j] = True
            ll.append((i+1, j))
        if not g[i-1][j]:
            g[i-1][j] = True
            ll.append((i-1, j))
        if not g[i][j+1]:
            g[i][j+1] = True
            ll.append((i, j+1))
        if not g[i][j-1]:
            g[i][j-1] = True
            ll.append((i, j-1))
    c += 1
    l = ll

print(c-1)

Submission status: Accepted

Solution code:
from collections import deque

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

table = []
for _ in range(H):
    table.append(["k"] + list(input()) + ["k"])
    
table = [["k"]*(W+2)] + table + [["k"]*(W+2)]

q = deque()

min_memo = [[None]*(W+2) for _ in range(H+2)]

all_cnt = 0
for y, r in enumerate(table):
    for x, c in enumerate(r):
        if c == "#":
            q.append([y,x,0])
            min_memo[y][x] = 0
            all_cnt += 1

if all_cnt == H*W:
    print(0)
else:          
    while True:
        y, x, cnt = q.popleft()
        for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
            if table[y+dy][x+dx] == ".":
                if min_memo[y+dy][x+dx] == None:
                    min_memo[y+dy][x+dx] = cnt+1
                    q.append([y+dy, x+dx, cnt+1])
                    all_cnt += 1
        if all_cnt >= H*W:
            print(cnt+1)
            break

Submission status: Accepted

Solution code:
# coding: utf-8
#!/usr/bin/env python3

"""
Python の queue モジュールは遅いので使わない
deque を使おう
"""

from collections import deque

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

# direction vector
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]

# 訪れたかどうかの情報を持つ bool 値
is_visited = [ [False] * w for _ in range(h) ]

q = deque()

for x in range(w):
    for y in range(h):
        if a[y][x] == "#":
            q.append( (x, y, 0) )
            is_visited[y][x] = True

ans = 0

while q:
    # queue の先頭を取り出す
    x, y, dist = q.popleft()
    ans = max(ans, dist)
    # 4方向にループ
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0 or w <= nx or ny < 0 or h <= ny:
            continue

        if is_visited[ny][nx]:
            continue

        q.append( (nx, ny, dist+1) )
        is_visited[ny][nx] = True

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def main():
    H,W = ints_raw()
    DFST = [[-1 for i in range(W)]for i in range(H)]
    qu = deque()
    dirs = [[1,0,1],[0,1,1],[-1,0,1],[0,-1,1]]
    ans = 0
    for h in range(H):
        S = input()
        for w in range(W):
            if S[w]=="#":
                DFST[h][w]=0
                qu.append([h,w,0])
    while len(qu)!=0:
        cpos = qu.popleft()
        for dir in dirs:
            
            ny,nx,nt = [cpos[0]+dir[0],cpos[1]+dir[1],cpos[2]+dir[2]]
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if DFST[ny][nx]!=-1:
                continue
            DFST[ny][nx]=nt
            ans = max(ans,nt)
            qu.append([ny,nx,nt])
    return ans

print(main())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H,W=MAP()

que = deque()
# 右左上下  
directions = [(0,1),(0,-1),(1,0),(-1,0)]
# 四方に一回り大きいグリッドを作る
grid = list2d(H+2, W+2, '*')
for i in range(1,H+1):
    row = list(input())
    for j in range(1, W+1):
        grid[i][j] = row[j-1]
        if grid[i][j] == '#':
            que.append((i, j, 0))

# 移動距離メモ
memo=[[-1]*(W+2) for i in range(H+2)]
while len(que):
    h1,w1,cost=que.popleft()
    if memo[h1][w1]!=-1:
        continue
    memo[h1][w1]=cost
    # 4方向見る
    for direction in directions:
        h2=h1+direction[0]
        w2=w1+direction[1]
        # 壁と黒はスキップ
        if grid[h2][w2]=='*' or grid[h2][w2]=='#':
            continue
        # 白を埋める
        if grid[h2][w2]=='.':
            grid[h2][w2]='#'
            que.append((h2, w2, cost+1))
ans=0
for i in range(1, H+1):
        ans=max(ans, max(memo[i]))
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
#!/usr/bin/env python3

from collections import deque

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

# direction vector
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]

# 訪れたかどうかの情報を持つ bool 値
is_visited = [ [False for _ in range(w)] for __ in range(h) ]

q = deque()

for x in range(w):
    for y in range(h):
        if a[y][x] == "#":
            q.append( (x, y, 0) )
            is_visited[y][x] = True

while q:
    # queue の先頭を取り出す
    x, y, cnt = q.popleft()
    # 4方向にループ
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]

        if nx < 0 or w <= nx or ny < 0 or h <= ny or is_visited[ny][nx]:
            continue

        q.append( (nx, ny, cnt+1) )
        is_visited[ny][nx] = True

print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import numpy as np
# from time import perf_counter


def main():
    h, w = map(int, input().split())
    max_value = h + w
    gridmap = []

    for y in range(h):
        gridmap.append([0 if v == '#' else max_value for v in input().strip()])

    values = np.array(gridmap)

    for x in range(w - 1):
        values[:, x + 1] = np.minimum(values[:, x] + 1, values[:, x + 1])

    for x in range(w - 1, 0, -1):
        values[:, x - 1] = np.minimum(values[:, x] + 1, values[:, x - 1])

    for y in range(h - 1):
        values[y + 1, :] = np.minimum(values[y, :] + 1, values[y + 1, :])

    for y in range(h - 1, 0, -1):
        values[y - 1, :] = np.minimum(values[y, :] + 1, values[y - 1, :])

    print(np.max(values))


if __name__ == '__main__':
    # st = perf_counter()
    main()
    # ed = perf_counter()
    # print(ed - st)

Submission status: Accepted

Solution code:
import sys
from collections import deque

H,W=map(int, raw_input().split())
A=[ list( sys.stdin.readline().strip())  for i in range(H) ]


D=[ (-1,0),(1,0),(0,1),(0,-1) ]
K=[ [ float("inf") for j in range(W) ] for i in range(H)  ]  #Kyori

q=deque()

for i in range(H):
	for j in range(W):
		if A[i][j]=="#":
			q.append( (i,j) )
			K[i][j]=0


while q:
	h,w=q.popleft()
	for dx,dy in D:
		if 0<=h+dx<H and 0<=w+dy<W and K[h+dx][w+dy]>K[h][w]+1:
				K[h+dx][w+dy]=K[h][w]+1
				q.append( (h+dx,w+dy) )	

ans=0
for x in K:
	ans=max(ans, max(x) )
print ans

Submission status: Accepted

Solution code:
# coding:utf-8

Black = "#"
White = "."

dir_x = [1, 0, -1, 0]
dir_y = [0, 1, 0, -1]


def main():
    H, W = map(int, input().split())
    step = 0
    count = W*H
    memo = [[-1]*W for i in range(H)]
    steplist = []

    for y in range(H):
        temp_in = input()
        for x in range(W):
            if temp_in[x] == Black:
                memo[y][x] = 0
                count -= 1
                steplist.append([y, x])

    while count > 0:
        step += 1
        next_list = []
        for l_yx in steplist:
            for i in range(4):
                temp_x = l_yx[1] + dir_x[i]
                temp_y = l_yx[0] + dir_y[i]
                if temp_x >= 0 and temp_x < W and temp_y >= 0 and temp_y < H:
                    if memo[temp_y][temp_x] < 0:
                        memo[temp_y][temp_x] = step
                        count -= 1
                        next_list.append([temp_y, temp_x])
        steplist = next_list
    print(step)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    rem = H * W
    visited = [True] * ((W+2) * (H+2))
    for i in range(W+2):
        visited[i] = False
        visited[(W + 2) * (H + 1) + i] = False
    for i in range(H+2):
        visited[(W + 2) * i] = False
        visited[(W + 2) * i + (W + 1)] = False

    for i in range(H):
        l = A[i]
        for j in range(W):
            if l[j] == '#':
                queue.append((i+1, j+1, 0))
                k = i * (W + 2) + j
                visited[k] = False

    ret = 0
    while queue:
        i, j, n = queue.popleft()
        k = i * (W + 2) + j
        if not visited[k] and 0 < n:
            continue
        visited[k] = False
        ret = n
        rem -= 1

        if rem == 0:
            break

        if visited[k - 1]:
            queue.append((i, j - 1, n + 1))
        if visited[k + 1]:
            queue.append((i, j + 1, n + 1))

        if visited[k - (W + 2)]:
            queue.append((i - 1, j, n + 1))
        if visited[k + (W + 2)]:
            queue.append((i + 1, j, n + 1))
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    result = solve(H, W, A)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy

def main():
    h, w = map(int, input().split())
    max_value = h + w
    gridmap = []

    for y in range(h):
        gridmap.append([0 if v == '#' else max_value for v in input().strip()])

    values = numpy.array(gridmap)

    for x in range(w - 1):
        values[:, x + 1] = numpy.minimum(values[:, x] + 1, values[:, x + 1])

    for x in range(w - 1, 0, -1):
        values[:, x - 1] = numpy.minimum(values[:, x] + 1, values[:, x - 1])

    for y in range(h - 1):
        values[y + 1, :] = numpy.minimum(values[y, :] + 1, values[y + 1, :])

    for y in range(h - 1, 0, -1):
        values[y - 1, :] = numpy.minimum(values[y, :] + 1, values[y - 1, :])

    print(numpy.max(values))


main()

Submission status: Accepted

Solution code:
H,W = list(map(int,input().split()))
A = [list(str(input())) for i in range(H)]
 
black = []
 
cnt = 0
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
 
length = len(black)
            
while (length < H*W):
    gray = []
    for l in black:
        if l[1] != 0:
            c1 = (l[0],l[1]-1)
            if A[c1[0]][c1[1]] == ".":
                gray.append(c1)
                A[c1[0]][c1[1]] = "#"
        if l[1] != W-1:
            c2 = (l[0],l[1]+1)
            if  A[c2[0]][c2[1]] == ".":
                gray.append(c2)
                A[c2[0]][c2[1]] = "#"
        if l[0] != 0:
            c3 = (l[0]-1,l[1])
            if  A[c3[0]][c3[1]] == ".":
                gray.append(c3)
                A[c3[0]][c3[1]] = "#"
        if l[0] != H-1:
            c4 = (l[0]+1,l[1])
            if  A[c4[0]][c4[1]] == ".":
                gray.append(c4)
                A[c4[0]][c4[1]] = "#"
    
    gray = list(set(gray))
    black = [l for l in gray]
    
    cnt += 1
    length += len(black)
    
print(cnt)

Submission status: Accepted

Solution code:
import sys
H, W, *A = sys.stdin.read().split()
H = int(H); W = int(W)

rW = range(W)
rrW = range(W-1, -1, -1)
rH = range(H)

INF = 4000
dist = [[INF]*W for i in rH]
S = []
push = S.append
for di, Ai in zip(dist, A):
    chg = 0
    for j, a in enumerate(Ai):
        if a == '#':
            di[j] = 0
            chg = 1
    if chg:
        push(di)
for di in S:
    cur = INF
    for j in rW:
        if not di[j]:
            cur = -j
        else:
            di[j] = cur+j
    cur = INF
    for j in rrW:
        if not di[j]:
            cur = j
        elif cur-j < di[j]:
            di[j] = cur-j
for j in rW:
    cur = INF
    for di in dist:
        if cur+1 < di[j]:
            di[j] = cur = cur+1
        else:
            cur = di[j]
    cur = INF
    for di in reversed(dist):
        if cur+1 < di[j]:
            di[j] = cur = cur+1
        else:
            cur = di[j]
sys.stdout.write("%d\n" % max(max(di) for di in dist))

Submission status: Accepted

Solution code:
from collections import deque

drc = ((0, 1), (0, -1), (1, 0), (-1, 0))

H, W = map(int, input().split())
a = tuple(input() for _ in range(H))
visited = [[False] * W for _ in range(H)]
# 重複探索を避けるため、訪問済みフラグを用意

q = deque()
for r in range(H):
    for c in range(W):
        if a[r][c] == '#':
            q.append((r, c, 0))
            visited[r][c] = True
            # BFS の起点となる座標と黒からの距離を deque に入れる
            # deque に入れたら訪問済みフラグを True にする
            # もし、座標(r, c) が pop された時点で visited とすると、
            # それまでに (r, c) が複数 deque に入れられてしまう恐れがある

while q:
    r, c, d = q.popleft()
    for dr, dc in drc:
        nr = r + dr
        if not (0 <= nr < H): continue
        nc = c + dc
        if not (0 <= nc < W): continue
        # 座標がセルからはみ出ていないか？
        if visited[nr][nc]: continue
        # 訪問済みか
        # 座標チェック前に訪問済みチェックをすると、IndexError
        q.append((nr, nc, d + 1))
        visited[nr][nc] = True
        # deque に入れたら訪問済みフラグを True にする

print(d)
# 最後に pop した距離 d が一番黒色から遠いセルになる

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np


def solve(H: int, W: int, A: "List[str]"):
    dist = np.full((H, W), np.inf)
    for h in range(H):
        for w in range(W):           
            if A[h][w] == '#':
                dist[h][w] = 0

    for h in range(H-1):
        dist[h+1, :] = np.minimum(dist[h, :] + 1, dist[h+1, :])
    for w in range(W-1):
        dist[:, w+1] = np.minimum(dist[:, w] + 1, dist[:, w+1])
    for h in range(H-1, 0, -1):
        dist[h-1, :] = np.minimum(dist[h, :] + 1, dist[h-1, :])
    for w in range(W-1, 0, -1):
        dist[:, w-1] = np.minimum(dist[:, w] + 1, dist[:, w-1])

    print(int(np.max(dist)))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from scipy.ndimage import*
print(maximum(morphology.distance_transform_cdt([[t>'#'for t in s[:-1]]for s in open(0)][1:],'taxicab')))

Submission status: Accepted

Solution code:
# 参考

import numpy

H, W = map(int, input().split())
values = [None] * H

for y in range(H):
    values[y] = [0 if v == "#" else H + W for v in input()]
values = numpy.array(values)

for x in range(W - 1):
    values[:, x + 1] = numpy.minimum(values[:, x] + 1, values[:, x + 1])

for x in range(W - 1, 0, -1):
    values[:, x - 1] = numpy.minimum(values[:, x] + 1, values[:, x - 1])

for y in range(H - 1):
    values[y + 1, :] = numpy.minimum(values[y, :] + 1, values[y + 1, :])

for y in range(H - 1, 0, -1):
    values[y - 1, :] = numpy.minimum(values[y, :] + 1, values[y - 1, :])

print(numpy.max(values))

Submission status: Accepted

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

l = []

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

def a(l):
    n = []
    d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for y, x in l:
        for dy, dx in d:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and B[ny][nx] == '.':
                B[ny][nx] = '#'
                n.append((ny, nx))
    return n

ans = 0
while len(l) != 0:
    l = a(l)
    ans += 1
print(ans-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H,W=MAP()

que = deque()
# 右左上下  
directions = [(0,1),(0,-1),(1,0),(-1,0)]
# 四方に一回り大きいグリッドを作る
grid = list2d(H+2, W+2, '*')
for i in range(1,H+1):
    row = list(input())
    for j in range(1, W+1):
        grid[i][j] = row[j-1]
        if grid[i][j] == '#':
            que.append((i, j, 0))

# 移動距離メモ
memo=[[-1]*(W+2) for i in range(H+2)]
while len(que):
    cur=que.popleft()
    if memo[cur[0]][cur[1]]!=-1:
        continue
    memo[cur[0]][cur[1]]=cur[2]
    # 4方向見る
    for direction in directions:
        x=cur[0]+direction[0]
        y=cur[1]+direction[1]
        # 壁と黒はスキップ
        if grid[x][y]=='*' or grid[x][y]=='#':
            continue
        # 白を埋める
        if grid[x][y]=='.':
            grid[x][y]='#'
            que.append((x, y, cur[2]+1))
ans=0
for i in range(1, H+1):
        ans=max(ans, max(memo[i]))
print(ans)