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

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

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

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

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

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

Submission status: Accepted

Solution code:
import collections

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

black = collections.deque()
for i in range(h):
    for j in range(w):
        if field[i][j] == "#":
            black.append((i,j))
            
ans = 0
dx = [1,0,-1,0]
dy = [0,1,0,-1]

def bfs(y,x):
    for k in range(4):
        newy = y + dy[k]
        newx = x + dx[k]
        if 0<= newy < h and 0<= newx < w:
            if field[newy][newx] == ".":
                black.append((newy,newx))
                field[newy][newx] = "#"

while black:
    l = len(black)
    for i in range(l):
        s = black.popleft()
        y,x = s[0],s[1]
        bfs(y,x)
    ans += 1

print(ans-1)

Submission status: Accepted

Solution code:
# Review problem
from collections import deque
H, W = map(int, input().split())
D = [list(input()) for i in range(H)]

visited = [[False for i in range(W)] for j in range(H)]
dis = [[0 for i in range(W)] for j in range(H)]

black = deque()
dif = [(-1, 0), (1, 0), (0, 1), (0, -1)]
for i in range(H):
    for j in range(W):
        if D[i][j] == "#":
            visited[i][j] = True
            black.append((i, j))

while black:
    x, y = black.popleft()
    for dx, dy in dif:
        if 0 <= dx+x < H and 0 <= dy+y < W and visited[dx+x][dy+y] == False:
            visited[dx+x][dy+y] = True
            dis[dx+x][dy+y] = dis[x][y]+1
            black.append((dx+x, dy+y))
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, dis[i][j])
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 18:01 -> 18:36 (give up. TLE)
from collections import deque

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

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

A = []
black_deque = deque()

for i in range(H):
    A.append(list(input()))
    black_deque.extend([(i,j) for j in range(W) if A[i][j] == '#'])

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

for x,y in black_deque:
    A[x][y] = 0

while len(black_deque) != 0:
    x,y = black_deque.popleft()
    depth = A[x][y]
    for k in range(4):
        new_x = x+dx[k]
        new_y = y+dy[k]
        if 0 <= new_x < H and \
           0 <= new_y < W and \
           A[new_x][new_y] == '.':
            black_deque.append((new_x, new_y))
            A[new_x][new_y] = depth+1

print(depth)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
A = [["#"]*(w+2)] + [["#"] + [s for s in input()] + ["#"]
                     for _ in range(h)] + [["#"]*(w+2)]


def main():
    step = 0
    Q = set([])
    for hh in range(1, h + 1):
        for ww in range(1, w + 1):
            if A[hh][ww] == "#":
                if A[hh - 1][ww] == ".":
                    Q.add((hh - 1, ww))
                if A[hh][ww - 1] == ".":
                    Q.add((hh, ww - 1))
                if A[hh + 1][ww] == ".":
                    Q.add((hh + 1, ww))
                if A[hh][ww + 1] == ".":
                    Q.add((hh, ww + 1))
    while len(Q) > 0:
        step += 1
        new = set([])
        for hh, ww in Q:
            A[hh][ww] = "#"
        while len(Q) > 0:
            hh, ww = Q.pop()
            if A[hh - 1][ww] == ".":
                A[hh-1][ww] = "#"
                new.add((hh - 1, ww))
            if A[hh][ww - 1] == ".":
                A[hh][ww-1] = "#"
                new.add((hh, ww - 1))
            if A[hh + 1][ww] == ".":
                A[hh+1][ww] = "#"
                new.add((hh + 1, ww))
            if A[hh][ww + 1] == ".":
                A[hh][ww + 1] = "#"
                new.add((hh, ww + 1))
        Q = new.copy()
    print(step)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

from collections import deque
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     # 動ける場所の候補


def debug(start, goal, p, t):
    player = p
    debug_grid = list(list(grid[h]) for h in range(H))
    if start != (None, None):
        debug_grid[start[0]][start[1]] = "S"
    if goal != (None, None):
        debug_grid[goal[0]][goal[1]] = "G"
    debug_grid[player[0]][player[1]] = "P"
    print("~~~~~~~~~ t = " + str(t+1) + "  ~~~~~~~~")
    for debug_h in range(H):
        print("".join(str(debug_grid[debug_h][debug_w]) for debug_w in range(W)))


def bfs(grid, next_set, goal, visit):
    visit[start[0]][start[1]] = 1               # スタート地点はすでに訪れている
    while next_set:                             # p = [] になったら止める
        p, t = next_set.popleft()               # 要素を消去して、消去した要素を出力
        h, w = p
        for dh, dw in move:                     # 頂点 p から進める経路の候補から一つ選ぶ
            q = (h + dh, w + dw)
            if q[0] < 0 or q[0] >= H or q[1] < 0 or q[1] >= W:
                continue
            if grid[q[0]][q[1]] == wall:         # 壁があったら進まない
                continue
            if visit[q[0]][q[1]] == 1:           # 一度訪れていた場合は進まない
                continue
            #### (debug code) ######
            # debug(start, goal, q, t)
            ########################
            if q == goal:                       # ゴールがあるならば、ここで判定
                return t + 1                    # 経路の長さは t + 1 で与えられる
            visit[q[0]][q[1]] = 1               # 頂点 q に一度訪れた事をメモ (for の前に書くと、ここで選ばれた q が最短であるはずなのに、違う経路でvisit = Trueを踏んでしまう可能性がある)
            next_set.append((q, t + 1))         # p から q へと移動。時刻を 1 進める
    return t


road, wall = ".", "#"                         # (進行可能を意味する記号, 進行不可を意味する記号)

H,W = map(int,input().split())                # 左上は(h,w)=(0,0)、右下は(h,w)=(H-1,W-1)

grid = []
next_set = deque()
visit = [[0]*W for _ in range(H)]
for h in range(H):
    grid.append(input())
    for w, a in enumerate(grid[-1]):
        if a == "#":
            start = (h, w)
            next_set.append((start,0))
            visit[start[0]][start[1]] = 1

print(bfs(grid, next_set, (None,None), visit))

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
q = deque()
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
x = ((-1, 0), (1, 0), (0, -1), (0, 1))
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            for k in x:
                if 0 <= i + k[0] < h and 0 <= j + k[1] < w and a[i + k[0]][j + k[1]] == ".":
                    a[i + k[0]][j + k[1]] = "0"
                    q.append([i + k[0], j + k[1], 1])
ans = 0
while q:
    u, v, res = q.popleft()
    for k in x:
        if 0 <= u + k[0] < h and 0 <= v + k[1] < w and a[u + k[0]][v + k[1]] == ".":
            a[u + k[0]][v + k[1]] = "0"
            q.append((u + k[0], v + k[1], res + 1))
            ans = res + 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque 
import sys
input = sys.stdin.readline
q = deque([])
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
x=[[-1,0],[1,0],[0,-1],[0,1]]
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            for k in x:
                if 0<=i+k[0]<h and 0<=j+k[1]<w and a[i+k[0]][j+k[1]]==".":
                    a[i+k[0]][j+k[1]]="0"
                    q.append([i+k[0],j+k[1],1])
ans=0
while q:
    v=q.popleft()
    for k in x:
        if 0<=v[0]+k[0]<h and 0<=v[1]+k[1]<w and a[v[0]+k[0]][v[1]+k[1]]==".":
            a[v[0]+k[0]][v[1]+k[1]]="0"
            q.append((v[0]+k[0],v[1]+k[1],v[2]+1))
            ans=v[2]+1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque 
import sys
input = sys.stdin.readline
q = deque([])
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
x=[[-1,0],[1,0],[0,-1],[0,1]]
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            for k in x:
                if 0<=i+k[0]<h and 0<=j+k[1]<w and a[i+k[0]][j+k[1]]==".":
                    a[i+k[0]][j+k[1]]="0"
                    q.append([i+k[0],j+k[1],1])
ans=0
while q:
    v=q.popleft()
    for k in x:
        if 0<=v[0]+k[0]<h and 0<=v[1]+k[1]<w and a[v[0]+k[0]][v[1]+k[1]]==".":
            a[v[0]+k[0]][v[1]+k[1]]="0"
            q.append([v[0]+k[0],v[1]+k[1],v[2]+1])
            ans=v[2]+1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

while q:
    y, x = q.popleft()
    ans = q.popleft() + 1
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        ny, nx = dy + y, dx + x
        if ny < 0 or nx < 0 or ny >= h or nx >= w:
            continue
        if a[ny][nx] == '.':
            a[ny][nx] = '#'
            q.append([ny, nx])
            q.append(ans)

print(ans-1)

Submission status: Accepted

Solution code:
from collections import deque
def main():
    H, W = map(int,input().split())
    s = [list(map(str,input())) for _ in range(H)]
    dist = [[-1]*W for _ in range(H)]
    
    q = deque([])
    for i in range(H):
        for j in range(W):
            if s[i][j] == "#":
                dist[i][j] = 0
                q.append((i, j))
    
    ans = 0
    while q:
        x, y = q.popleft()
        dx = [1, -1, 0, 0]
        dy = [0, 0, 1, -1]
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if (0 <= nx < H and 0 <= ny < W and dist[nx][ny] == -1 and s[nx][ny] == '.'):
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))
                ans = max(ans, dist[nx][ny])
                
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

A=[]
que=[]
done=[[-1]*W for _ in range(H)]
for h in range(H):
    a=list(input())
    A.append(a)
    for w in range(W):
        if a[w]=="#":
            que.append((h,w))
            done[h][w]=0

d=[(1,0),(-1,0),(0,1),(0,-1)]
que=deque(que)
ans=0
while que:
    h,w=que.popleft()
    now=done[h][w]
    for t in d:
        dh,dw=t
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if done[nh][nw]==-1:
                done[nh][nw]=now+1
                que.append((nh,nw))
                ans=max(ans, now+1)



print(ans)

Submission status: Accepted

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

from collections import deque
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     # 動ける場所の候補


def debug(start, goal, p, t):
    player = p
    debug_grid = list(list(grid[h]) for h in range(H))
    if start != (None, None):
        debug_grid[start[0]][start[1]] = "S"
    if goal != (None, None):
        debug_grid[goal[0]][goal[1]] = "G"
    debug_grid[player[0]][player[1]] = "P"
    print("~~~~~~~~~ t = " + str(t+1) + "  ~~~~~~~~")
    for debug_h in range(H):
        print("".join(str(debug_grid[debug_h][debug_w]) for debug_w in range(W)))


def search(grid, next_set, goal=(None,None), visit=set()):
    visit.add(start)                            # スタート地点はすでに訪れている
    while next_set:                             # p = [] になったら止める
        p, t = next_set.popleft()               # 要素を消去して、消去した要素を出力
        h, w = p
        for dh, dw in move:                     # 頂点 p から進める経路の候補から一つ選ぶ
            q = (h + dh, w + dw)
            if q[0] < 0 or q[0] >= H or q[1] < 0 or q[1] >= W:
                continue
            if grid[q[0]][q[1]] == wall:         # 壁があったら進まない
                continue
            if q in visit:                      # 一度訪れていた場合は進まない
                continue
            #### (debug code) ######
            # debug(start, goal, q, t)
            ########################
            if q == goal:                       # ゴールがあるならば、ここで判定
                return t + 1                    # 経路の長さは t + 1 で与えられる
            visit.add(q)                        # 頂点 q に一度訪れた事をメモ (for の前に書くと、ここで選ばれた q が最短であるはずなのに、違う経路でvisit = Trueを踏んでしまう可能性がある)
            next_set.append((q, t + 1))         # p から q へと移動。時刻を 1 進める
    return t



road, wall = ".", "#"                         # (進行可能を意味する記号, 進行不可を意味する記号)

H,W = map(int,input().split())                # 左上は(h,w)=(0,0)、右下は(h,w)=(H-1,W-1)

grid = []
next_set = deque()
visit = set()
for h in range(H):
    grid.append(input())
    for w, a in enumerate(grid[-1]):
        if a == "#":
            start = (h, w)
            next_set.append((start,0))
            visit.add(start)

print(search(grid, next_set, goal=(None,None), visit=visit))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

H, W = LI()
A = [[] for i in range(H)]
for i in range(H):
    a = list(str(input()))
    A[i] = a
# 複数のスタート地点が存在してもqueに突っ込むことで同様の効果が得られる．
visited = [[-1 for i in range(W)] for j in range(H)]

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

moves = [[0,1],[1,0],[-1,0],[0,-1]]
cnt = 0
while len(d) > 0:
    X, Y = d.popleft()
    cnt = visited[X][Y]
    for x, y in moves:
        n_X = X + x
        n_Y = Y + y
        if 0 <= n_X < H and 0 <= n_Y< W:
            if visited[n_X][n_Y] == -1:
                visited[n_X][n_Y] = cnt + 1
                d.append((n_X, n_Y))
print(cnt)

Submission status: Accepted

Solution code:
from collections import deque

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

S = [None]*W
S = [list(input()) for i in range(H)]
light = []
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            light.append((i,j))

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

not_visited = [[-1]*W for i in range(H)]
stack = deque()
for k in range(len(light)):
    stack.append(light[k])
    i,j = light[k]
    not_visited[i][j] = 0

while stack != deque([]):
    y,x = stack.popleft()
    for i in range(4):
        if 0<= x+dx[i] <W and 0<= y+dy[i] <H and not_visited[y+dy[i]][x+dx[i]] == -1:
            not_visited[y+dy[i]][x+dx[i]] =  not_visited[y][x] + 1
            stack.append((y+dy[i],x+dx[i]))

ans = -1
for i in range(H):
    ans = max(ans,max(not_visited[i]))

print(ans)

Submission status: Accepted

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

INF = 1 << 21


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

  blacks = deque()
  whites = []
  d = [[INF]*W for _ in range(H)]
  for i in range(H):
    for j in range(W):
      if M[i][j] == '#':
        blacks.append((i, j))
        d[i][j] = 0
      elif M[i][j] == '.':
        whites.append((i, j))

  def bfs(q, d):
    is_visited = [[0]*W for _ in range(H)]
    while len(q):
      ur, uc = q.popleft()
      d_ur = d[ur]
      for vr, vc in [(ur+1, uc), (ur-1, uc), (ur, uc-1), (ur, uc+1)]:
        if 0 <= vr < H and \
           0 <= vc < W:

          d_vr = d[vr]
          is_visited_vr = is_visited[vr]
          if not(is_visited_vr[vc]) and not(M[vr][vc] == '#') and \
             (d_vr[vc] > d_ur[uc] + 1):

            d_vr[vc] = d_ur[uc] + 1
            is_visited_vr[vc] = True
            q.append((vr, vc))
    return d_ur[uc]

  print(bfs(blacks, d))


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