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: Time Limit Exceeded

Solution code:
import numpy as np
import heapq
import sys
sys.setrecursionlimit(10**6)

H,W = map(int,input().split())
INF = 10**18
q = []

d = np.full((H,W),INF,dtype=np.int64) # '#'からの距離

for i in range(H):
  txt = input()
  for j,c in enumerate(txt):
    if c == '#':
      d[i,j] = 0
      heapq.heappush(q,(0,i,j))

while q:
  dv,x,y = heapq.heappop(q)
  for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
    xx = x+dx
    yy = y+dy
    if xx == -1 or xx == H:
      continue
    if yy == -1 or yy == W:
      continue
    if d[xx,yy] >= dv+1:
      d[xx,yy] = dv+1
      heapq.heappush(q,(dv+1,xx,yy))

ans = d.max()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map( int, input().split())
A = [ input() for _ in range(H)]
B = [ [-1]*W for _ in range(H)]
q = []
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            B[i][j] = 0
            q.append((i,j))
while q:
    h, w = q.pop(0)
    #left
    if h > 0:
        if B[h-1][w] == -1:
            B[h-1][w] = B[h][w]+1
            q.append((h-1,w))
    if h < H-1:
        if B[h+1][w] == -1:
            B[h+1][w] = B[h][w] + 1
            q.append((h+1,w))
    if w > 0:
        if B[h][w-1] == -1:
            B[h][w-1] = B[h][w] + 1
            q.append((h,w-1))
    if w < W-1:
        if B[h][w+1] == -1:
            B[h][w+1] = B[h][w] + 1
            q.append((h,w+1))
C = [ max(B[i]) for i in range(H)]
print( max(C))

Submission status: Time Limit Exceeded

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

H,W=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

from collections import deque
QUE=deque()

for i in range(H):
    for j in range(W):

        if MAP[i][j]=="#":
            QUE.append([i,j,0])

ANS=[[-1]*W for i in range(H)]

while QUE:
    NQUE=deque()
    while QUE:
        x,y,z=QUE.pop()
        ANS[x][y]=z

        for nx,ny in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:
            if nx<0 or ny<0 or nx>=H or ny>=W:
                continue

            if ANS[nx][ny]!=-1:
                continue

            NQUE.append([nx,ny,z+1])

    QUE=NQUE

            
print(max([max(ANS[i]) for i in range(H)]))

Submission status: Time Limit Exceeded

Solution code:
import heapq, sys
F = sys.stdin
H, W = map(int, F.readline().strip("\n").split())
Q = []
heapq.heapify(Q)
maxlength = 0
search = [(-1, 0), (1, 0), (0, -1), (0, 1)]

visited = [[False for w in range(W)] for h in range(H)]
for h in range(H):
    a = F.readline().strip("\n")
    for w in range(W):
        if a[w] == "#":
            heapq.heappush(Q, (0, h, w))
            
while Q:
    nowlength, nowh, noww = heapq.heappop(Q)
    if not visited[nowh][noww]:
        maxlength = nowlength
        visited[nowh][noww] = True
        for sh, sw in search:
            if 0 <= nowh + sh < H and 0 <= noww + sw < W:
                if not visited[nowh+sh][noww+sw]:
                    heapq.heappush(Q, (nowlength+1, nowh+sh, noww + sw))
print(maxlength)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = list(map(int, input().split()))
board = [list(input()) for i in range(h)]
q = deque()
for i in range(h):
    for j in range(w):
        if board[i][j] == "#":
            q.append((i,j, 0))
            board[i][j] = "."

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

while q:
    i,j,cnt = q.popleft()
    if board[i][j] != ".":
        continue
    board[i][j] = cnt
    for x, y in zip(dx,dy):
        if 0<=i+x<h and 0<=j+y<w:
            q.append((i+x, j+y, cnt+1))
ans = 0
for i in range(h):
    ans = max(ans, max(board[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
H, W = map(int, input().split())
Q = []
heapq.heapify(Q)
maxlength = 0
search = [(-1, 0), (1, 0), (0, -1), (0, 1)]

visited = [[False for w in range(W)] for h in range(H)]
for h in range(H):
    a = input()
    for w in range(W):
        if a[w] == "#":
            heapq.heappush(Q, (0, h, w))
            
while Q:
    nowlength, nowh, noww = heapq.heappop(Q)
    if not visited[nowh][noww]:
        maxlength = nowlength
        visited[nowh][noww] = True
        for sh, sw in search:
            if 0 <= nowh + sh < H and 0 <= noww + sw < W:
                if not visited[nowh+sh][noww+sw]:
                    heapq.heappush(Q, (nowlength+1, nowh+sh, noww + sw))
print(maxlength)

Submission status: Time Limit Exceeded

Solution code:
# encoding: utf-8
import sys
# input = sys.stdin.readline
inf = 10 ** 18

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

from collections import deque

field = [[None] * W for _ in range(H)]
q = deque([])
cnt = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            field[i][j] = 0
            q.append((i, j, 0))
            cnt += 1

tblr = ((-1, 0), (1, 0), (0, -1), (0, 1))
while cnt < H * W:
    y, x, d = q.popleft()
    for dy, dx in tblr:
        if y + dy < 0: continue
        if x + dx < 0: continue
        if y + dy >= H: continue
        if x + dx >= W: continue
        if field[y + dy][x + dx] != None: continue
        #
        field[y + dy][x + dx] = d + 1
        q.append((y + dy, x + dx, d + 1))
        cnt += 1

print(max([max(field[i]) for i in range(H)]))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

H, W = map(int, input().split())
#B = [input() for _ in range(H)]
Close = set()
Open = []

Dx = [0,1,0,-1]
Dy = [1,0,-1,0]

for y in range(H):
    b = input()
    for x, c in enumerate(b):
        if c=="#":
            Open.append((y, x))
            Close.add((y, x))
ans = -1
while len(Open)>0:
    Open_ = []
    for y, x in Open:
        for dx, dy in zip(Dx, Dy):
            x_ = x+dx
            y_ = y+dy
            if 0<=x_<W and 0<=y_<H and (y_, x_) not in Close:
                Open_.append((y_, x_))
                Close.add((y_, x_))
    Open = Open_
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque

h,w = li()
a = [list(lc()) for _ in range(h)]

que = deque()

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

for i, ai in enumerate(a):
    for j, aij in enumerate(ai):
        if aij == "#":
            que.append((0, (i, j)))
            dist[i][j] = 0
        
drs = [0,1,0,-1]
dcs = [1,0,-1,0]

while que:
    cur, (r,c) = que.popleft()
    dist[r][c] = cur
    
    for dr, dc in zip(drs, dcs):
        if 0 <= r+dr < h and 0 <= c+dc < w:
            if dist[r+dr][c+dc] == -1:
                dist[r+dr][c+dc] = cur + 1
                que.append((cur+1, (r+dr, c+dc)))
                
ans = 0
for di in dist:
    for dij in di:
        ans = max(ans, dij)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
e = [[False for _ in range(W)] for _ in range(H)]
cnt = 0
for r in range(H):
    a = input()
    for c in range(W):
        if a[c] == '#':
            cnt += 1
            e[r][c] = True

ans = 0
while cnt < H * W:
    st = set()
    for r in range(H):
        for c in range(W):
            if e[r][c]:
                for dr, dc in (-1, 0), (1, 0), (0, -1), (0, 1):
                    nr = r + dr
                    if not (0 <= nr < H): continue
                    nc = c + dc
                    if not (0 <= nc < W): continue
                    if e[nr][nc]: continue
                    st.add((nr, nc))
    for nr, nc in st:
        e[nr][nc] = True
        cnt += 1
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = list(map(int, input().split()))
f = []
q = deque()
for i in range(h):
    l = input()
    for j, c in enumerate(l):
        if c == '#':
            q.append((0, i, j))
    f.append(l)
visited = [[False] * w for _ in [0] * h]
ans = 0
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]

while q:
    d, i, j = q.popleft()
    if visited[i][j]:
        continue
    ans = d
    visited[i][j] = True
    for di, dj in move:
        ni, nj = i + di, j + dj
        if ni < 0 or h <= ni or nj < 0 or w <= nj:
            continue
        if visited[ni][nj]:
            continue
        q.append((d + 1, ni, nj))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
T = [[] for i in range(H)]
d = []
for i in range(H):
    a = list(input())
    T[i] = a
    for j in range(W):
        if a[j] == '#':
            d.append((i, j, 0))

ma = 0
while len(d) > 0:
    x, y, k = d.pop(0)
    ma = max(ma, k)
    for dx, dy in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W and T[nx][ny] == '.':
            T[nx][ny] = '#'
            d.append((nx, ny, k + 1))

print(ma)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
#B = [input() for _ in range(H)]
Close = set()
Open = []

Dx = [0,1,0,-1]
Dy = [1,0,-1,0]

for y in range(H):
    b = input()
    for x, c in enumerate(b):
        if c=="#":
            Open.append((y, x))
            Close.add((y, x))
ans = -1
while len(Open)>0:
    Open_ = []
    for y, x in Open:
        for dx, dy in zip(Dx, Dy):
            x_ = x+dx
            y_ = y+dy
            if 0<=x_<W and 0<=y_<H and (y_, x_) not in Close:
                Open_.append((y_, x_))
                Close.add((y_, x_))
    Open = Open_
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

H, W = map(int, input().split())
m = [["#"] * (W+2)] + [["#"] + list(input()) + ["#"] for _ in range(H)] + [["#"] * (W+2)]
q = deque()
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

step = [[float("inf") for _ in range(W+2)] for _ in range(H+2)]

for h in range(1, H+1):
	for w in range(1, W+1):
		if m[h][w] == "#":
			q.appendleft([h, w])
			step[h][w] = 0

while q:
	label = q.pop()

	for i in range(4):
		h, w = label[0] + dx[i], label[1] + dy[i]
		if m[h][w] != "#" and step[h][w] > step[label[0]][label[1]] + 1:
			q.appendleft([h, w])
			step[h][w] = step[label[0]][label[1]] + 1

ans = 0
for h in range(1, H+1):
	for w in range(1, W+1):
		ans = max(ans, step[h][w])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import heapq
import sys
sys.setrecursionlimit(10**6)

H,W = map(int,input().split())
INF = 10**18
q = []

d = np.full((H,W),INF,dtype=np.int64) # '#'からの距離

for i in range(H):
  txt = input()
  for j,c in enumerate(txt):
    if c == '#':
      d[i,j] = 0
      heapq.heappush(q,(0,i,j))

while q:
  dv,x,y = heapq.heappop(q)
  for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
    xx = x+dx
    yy = y+dy
    if xx == -1 or xx == H:
      continue
    if yy == -1 or yy == W:
      continue
    if d[xx,yy] > dv+1:
      d[xx,yy] = dv+1
      heapq.heappush(q,(dv+1,xx,yy))

ans = d.max()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

def completed(A,H,W):
    for h in range(H):
        if '.' in A[h]:
            return False
    return True

def run(A,H,W):
    B = copy.deepcopy(A)
    for h in range(H):
        for w in range(W):
            if A[h][w] == '.':
                d = 0
                if (h > 0 and A[h-1][w] == '#') or \
                   (w > 0 and A[h][w-1] == '#') or \
                   (h < H-1 and A[h+1][w] == '#') or \
                   (w < W-1 and A[h][w+1] == '#'):
                   B[h][w] = '#'
    return B

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

    ans = 0
    while not completed(A,H,W):
        A = run(A,H,W)
        ans += 1
    return ans

print(solve())

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int, input().split())
a = [list(input()) for _ in range(h)]
dark = []
white = []
for i in range(h):
  for j in range(w):
    if a[i][j] == ".":
      white.append((i,j))
    else:
      dark.append((i,j))
ml = 0
for w,x in white:
  cl = 10000
  for y,z in dark:
    t = abs(w-y) + abs(x-z)
    cl = min(cl,t)
  ml = max(ml,cl)
print(ml)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10000)
INF = float('inf')

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


def is_white(h, w):
    return 0 <= h < H and 0 <= w < W and A[h][w] == '.'


que = deque()
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            if is_white(h + 1, w):
                que.append((h + 1, w))
            if is_white(h - 1, w):
                que.append((h - 1, w))
            if is_white(h, w + 1):
                que.append((h, w + 1))
            if is_white(h, w - 1):
                que.append((h, w - 1))

ans = 0
while len(que) > 0:
    ans += 1
    nextq = deque()
    while len(que) > 0:
        h, w = que.pop()
        A[h][w] = '#'
        if is_white(h + 1, w):
            nextq.append((h + 1, w))
        if is_white(h - 1, w):
            nextq.append((h - 1, w))
        if is_white(h, w + 1):
            nextq.append((h, w + 1))
        if is_white(h, w - 1):
            nextq.append((h, w - 1))
    que = nextq
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    h, w = map(int, raw_input().split())
    s = [raw_input().strip() for _ in xrange(h)]
    q = deque()
    a = [100000] * (h * w)
    for i, r in enumerate(s):
        for j, c in enumerate(r):
            if c == '#':
                q.append((i, j))
                a[i*w+j] = 0
    dd = ((0, -1), (0, 1), (1, 0), (-1, 0))
    while q:
        x, y = q.popleft()
        z = a[x*w+y] + 1
        for dx, dy in dd:
            nx, ny = x + dx, y + dy
            if 0 <= nx < h and 0 <= ny < w and a[nx*w+ny] > z:
                a[nx*w+ny] = z
                q.append((nx, ny))
    print max(a)
main()

Submission status: Time Limit Exceeded

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

from collections import deque
import copy
QUE=deque()

for i in range(H):
    for j in range(W):

        if MAP[i][j]=="#":
            QUE.append([i,j,0])

ANS=[[-1]*W for i in range(H)]

while QUE:
    NQUE=deque()
    while QUE:
        x,y,z=QUE.pop()
        ANS[x][y]=z

        for nx,ny in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:
            if nx<0 or ny<0 or nx>=H or ny>=W:
                continue

            if ANS[nx][ny]!=-1:
                continue

            NQUE.append([nx,ny,z+1])

    QUE=NQUE

            
print(max([max(ANS[i]) for i in range(H)]))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


fin = sys.stdin.readline
H, W = [int(elem) for elem in fin().split()]
A_list = [list(fin().rstrip("\n")) for _ in range(H)]
assert len(A_list[0]) == W

distances = [[float('inf')] * W for _ in range(H)]
que = deque((i, j, 0) for i in range(H) for j in range(W) if A_list[i][j] == "#")
max_dist = 0
while que:
    i, j, dist = que.popleft()
    for next_i, next_j in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
        if not (0 <= next_i < H and 0 <= next_j < W):
            continue
        elif distances[next_i][next_j] < float('inf'):
            continue
        elif A_list[next_i][next_j] == "#":
            continue
        else:
            que.append((next_i, next_j, dist + 1))
            distances[next_i][next_j] = dist + 1
            max_dist = max(max_dist, dist + 1)
print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
from collections import*
h,w=map(int,input().split())
c=eval('list(input()),'*h)
q=deque()
for i in range(h):
    for j in range(w):
        if c[i][j]=='#':
            q.append((i,j,0))
ans=0
while q:
    y,x,v=q.popleft()
    ans=max(ans,v)
    for i,j in((y,x-1),(y,x+1),(y-1,x),(y+1,x)):
        if h>i>=0 and w>j>=0 and c[i][j]=='.':
            c[i][j]='#'
            q.append((i,j,v+1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)

def main():
    h,w = LI()
    a = [S() for _ in range(h)]
    t = set()
    for i in range(h):
        ai = a[i]
        for j in range(w):
            if ai[j] == '#':
                t.add((i,j))

    r = 0
    u = t | set()
    while 1:
        k = set()
        for i,j in t:
            for di,dj in dd:
                ni = i + di
                nj = j + dj
                if ni < 0 or ni >= h or nj < 0 or nj >= w:
                    continue
                nk = (ni,nj)
                if (ni,nj) in u:
                    continue
                k.add(nk)
        if not k:
            break
        r += 1
        t = k
        u |= k

    return r


print(main())

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,raw_input().split())
arr = [list(raw_input()) for x in range(N)]
chk = [[0 for x in range(M)] for x in range(N)]
q = []
for i in range(N):
	for j in range(M):
		if arr[i][j]=='#':
			chk[i][j] = 1
			q.append([i,j])

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

while q:
	cur = q.pop(0)
	for i in moves:
		y,x = cur[0]+i[0],cur[1]+i[1]
		if y<0 or y>=N or x<0 or x>=M:
			continue
		if chk[y][x]:
			continue
		chk[y][x] = chk[cur[0]][cur[1]]+1
		ans = max(ans,chk[y][x]-1)
		q.append([y,x])

print ans

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
A = [input().strip() for _ in range(H)]
B = [[0 for _ in range(W)] for _ in range(H)]
que = []
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            que.append((i,j,0))
que = deque(que)
while que:
    y,x,d = que.popleft()
    if x+1<W and A[y][x+1]=="." and B[y][x+1]==0:
        B[y][x+1]=d+1
        que.append((y,x+1,d+1))
    if y-1>=0 and A[y-1][x]=="." and B[y-1][x]==0:
        B[y-1][x]=d+1
        que.append((y-1,x,d+1))
    if x-1>=0 and A[y][x-1]=="." and B[y][x-1]==0:
        B[y][x-1]=d+1
        que.append((y,x-1,d+1))
    if y+1<H and A[y+1][x]=="." and B[y+1][x]==0:
        B[y+1][x]=d+1
        que.append((y+1,x,d+1))
bmax = 0
for i in range(H):
    for j in range(W):
        bmax = max(bmax,B[i][j])
print(bmax)

Submission status: Accepted

Solution code:
from collections import deque
from itertools import product


def bfs():
    while q:
        i, j = q.popleft()
        for di, dj in (1, 0), (-1, 0), (0, 1), (0, -1):
            ni, nj = i + di, j + dj
            if not (0 <= ni < H and 0 <= nj < W and dist[ni][nj] < 0):
                continue
            dist[ni][nj] = dist[i][j] + 1
            q.append((ni, nj))


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

q = deque()
dist = [[-1] * W for _ in range(H)]
for i, j in product(range(H), range(W)):
    if A[i][j] == ".":
        continue
    q.append((i, j))
    dist[i][j] = 0
bfs()
print(max(max(row) for row in dist))

Submission status: Accepted

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

from collections import deque
q = deque([])
visit = [[-1]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if A[i][j] == '#':
            q.append((i, j))
            visit[i][j] = 0

while q:
    y, x = q.popleft()
    for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
        ny, nx = y+dy, x+dx
        if 0 <= ny < h and 0 <= nx < w:
            if visit[ny][nx] == -1:
                visit[ny][nx] = visit[y][x]+1
                q.append((ny, nx))
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, visit[i][j])
print(ans)

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(1000000)
from collections import deque

H, W = map(int, input().split())
#配列の入力
data = [list(input()) for _ in range(H)]

memo = [[-1 for _ in range(W)]for _ in range(H)]
que = deque()

for h in range(H):
    for w in range(W):
        if data[h][w] == '#':
            memo[h][w] = 0
            que.append((h, w))

offset = ((-1, 0), (1, 0), (0, -1), (0, 1))
while que:
    now_h, now_w = que.popleft()
    for nh, nw in offset:
        if now_h+nh < 0 or H-1 < now_h+nh or now_w+nw < 0 or W-1 < now_w+nw:
            continue

        if memo[now_h+nh][now_w+nw] >= 0:
            continue

        memo[now_h+nh][now_w+nw] = memo[now_h][now_w]+1
        que.append((now_h+nh,now_w+nw))


ans = -1
for h in range(H):
    ans = max(ans, max(memo[h]))
print(ans)

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    from collections import deque

    h, w = input_int_list()
    grid = []
    visited = []
    grid.append(["@"] * (w + 2))
    visited.append([True] * (w + 2))
    for _ in range(h):
        grid.append(["@"] + list(input()) + ["@"])
        visited.append([True] + [False] * w + [True])
    grid.append(["@"] * (w + 2))
    visited.append([True] * (w + 2))

    # 幅優先探索で すべてを"#"に変える。
    # かかった手数分が答え
    direction = ((0, 1), (1, 0), (-1, 0), (0, -1))
    dq = deque()
    # すべての"#"をdequeに入れる
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if grid[i][j] == "#":
                dq.append((i, j, 0))
                visited[i][j] = True
    ans = 0
    # 幅優先探索
    while dq:
        i, j, d = dq.popleft()
        for di, dj in direction:
            if grid[i + di][j + dj] == "." and not visited[i + di][j + dj]:
                dq.append((i + di, j + dj, d + 1))
                visited[i + di][j + dj] = True
                ans = max(ans, d + 1)

    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

sys.setrecursionlimit(1000000)
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():
    H, W = NMI()
    grid = [SI() for _ in range(H)]
    step = [[-1]*W for _ in range(H)]
    que = deque()
    for h in range(H):
        for w in range(W):
            p = grid[h][w]
            if p == "#":
                que.append((h, w))
                step[h][w] = 0
    DIR = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    while que:
        x, y = que.popleft()

        for dx, dy in DIR:
            if not(0 <= x+dx < H and 0 <= y+dy < W):
                continue
            if step[x+dx][y+dy] >= 0:
                continue
            que.append((x+dx, y+dy))
            step[x+dx][y+dy] = step[x][y] + 1

    print(max([max(s) for s in step]))



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
def main():
    readline = stdin.readline
    H,W = map(int,readline()[:-1].split())
    A = ['' for i in range(H)]
    visited = [[False] * W for i in range(H)]
    q = deque()
    for i in range(H):
        A[i] = readline()[:-1]
        # print(A[i])
        for j,color in enumerate(A[i]):
            if '#' == color:
                q.append([i,j,0])
                visited[i][j] = True
            # for i in visited:
            #     print(i)
    mx = 0
    direction = [[1,0],[0,1],[-1,0],[0,-1]]
    op = -1
    while len(q) > 0:
        # print(q)
        tmp = [y,x,op] = q.popleft()
        # print(tmp)
        mx = mx if mx > op else op
        for [dx,dy] in direction:
            ny,nx = y + dy , x + dx
            if  0 <= ny and ny < H and 0 <= nx and nx < W:
                if A[ny][nx] == '#' or visited[ny][nx] == True:
                    continue
                q.append([ny,nx,op+1])
                visited[ny][nx] = True
    print(op)

main()