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)]
B = [[0 for w in range(W+2)] for h in range(H+2)]
for h in range(1,H+1):
    for w in range(1,W+1):
        if A[h-1][w-1] == '#':
            B[h][w] = -1
for h in range(1,H+1):
    for w in range(1,W+1):
        if A[h-1][w-1] != '#':
            if B[h-1][w] == -1 or B[h+1][w] == -1 or B[h][w-1] == -1 or B[h][w+1] == -1:
                B[h][w] = 1
            else:
                if B[h-1][w] == 0 and B[h+1][w] == 0 and B[h][w-1] == 0 and B[h][w+1] == 0:
                    pass
                else:
                    k = [B[h-1][w],B[h+1][w],B[h][w-1],B[h][w+1]]
                    k = [i for i in k if i > 0]
                    B[h][w] = min(k)+1
for w in reversed(range(1,W+1)):
    for h in reversed(range(1,H+1)):
        if A[h-1][w-1] != '#':
            if B[h-1][w] == -1 or B[h+1][w] == -1 or B[h][w-1] == -1 or B[h][w+1] == -1:
                B[h][w] = 1
            else:
                if B[h-1][w] == 0 and B[h+1][w] == 0 and B[h][w-1] == 0 and B[h][w+1] == 0:
                    pass
                else:
                    k = [B[h-1][w],B[h+1][w],B[h][w-1],B[h][w+1]]
                    k = [i for i in k if i > 0]
                    B[h][w] = min(k)+1

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

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)


# Graph
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


queue = deque(black_cells)
d = [10000]*(H*W)
for i in black_cells:
    d[i] = 0

# dijkstra
while len(queue) > 0:
    p = queue.popleft()
    for q in r(p):
        if d[q] > d[p] + 1:
            d[q] = d[p] + 1
            queue.append(q)

print(max(d))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import collections

h,w = [int(i) for i in input().split()]
board = [input() for j in range(h)] # 縦「n」行

d4 = [[1,0],[0,1],[-1,0],[0,-1]]
memo = [[-1]*w for j in range(h)]
dist = [[100000]*w for j in range(h)]


q = collections.deque()
for i in range(h):
    for j in range(w):
        if board[i][j] == "#":
            memo[i][j] = 1
            q.append((i,j,0))

while len(q) != 0:
#    print(memo)
    i,j,c = q.popleft()
    dist[i][j] = c
    for k in d4:
#        print(k)
        ii,jj = k
        if  i+ii < 0 or i+ii>=h or j+jj <0 or j+jj>=w:
#            print("out",i+ii,j+jj)
            continue
        if memo[i+ii][j+jj] < 0:
#            print("put")
            q.append((i+ii,j+jj,c+1))
            memo[i+ii][j+jj] = 1

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

print(ans)
#print(dist)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import numpy


def main():
  height, width = map(int, input().split())
  max_value = height + width
  values = []

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

  values = numpy.array(values)

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

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

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

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

  print(numpy.max(values), flush=True)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
r,c = map(int,input().split())
grid = []
temp = []
limit = r*c
total = 0
count = 0
for i in range(r):
    next = list(input())
    for j in range(c):
        if next[j]=='#':
            temp.append([i,j])
            total+=1
    grid.append(next)
while(total<limit):
    nextround = []
    while(len(temp)>0):
        x,y = temp.pop()
        # print('X:',x,'Y:',y)
        if x-1>-1:
            if grid[x-1][y] == '.':
                grid[x - 1][y] = '#'
                total +=1
                nextround.append([x-1,y])
        if x+1<r:

            if grid[x+1][y] == '.':
                grid[x + 1][y] = '#'
                total +=1
                nextround.append([x+1, y])
        if y-1>-1:
            if grid[x][y-1] == '.':
                grid[x][y-1] = '#'
                total +=1
                nextround.append([x,y-1])
        if y+1<c:
            if grid[x][y+1] == '.':
                grid[x][y+1] = '#'
                total +=1
                nextround.append([x,y+1])
    temp = nextround
    count+=1
print(count)

Submission status: Accepted

Solution code:
MAX_INT = int(10e10)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def cnt(c,d):
    if (0 <= c < H) and (0 <= d < W):
        return grid[c][d]
    else:
        return MAX_INT
def tami(a,b):
    num = min(cnt(a+1,b),cnt(a,b+1),cnt(a-1,b),cnt(a,b-1))
    return num+1

H,W = IL()
A = [[i for i in S()] for i in range(H)]

grid = [[MAX_INT]*W for i in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            grid[i][j] = 0

for i in range(H):
    for j in range(W):
        if grid[i][j] != 0:
            grid[i][j] = tami(i,j)

for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if grid[i][j] != 0:
            grid[i][j] = tami(i,j)

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

print(ans)

Submission status: Accepted

Solution code:
# Enter your code here. Read input from STDIN. Print output to STDOUT
def parse(A):
    R=len(A)
    C=len(A[0])
    grid=[[1 for j in xrange(C)]  for i in xrange(R)]
    for i in xrange(R):
        for j in xrange(C):
            if A[i][j]=='.':
                grid[i][j]=0
                
    return grid

def find(grid):
    black={}
    R=len(grid)
    C=len(grid[0])
    new=[]
    for i in xrange(R):
        for j in xrange(C):
            if grid[i][j]==1:
                black[(i,j)]=0
                new+=[(i,j)]
    time=0        
    
    while len(black)<R*C:
        
        time+=1
        new_black=set([])
        
        for X in new:
            x,y=X
            check=[(x-1,y),(x+1,y),(x,y-1),(x,y+1)]
            for Y in check:
                y1,y2=Y[0],Y[1]
                if y1>R-1 or y1<0 or y2>C-1 or y2<0:
                    continue
                if grid[y1][y2]==0:
                    new_black.add((y1,y2))
                    
                    black[(y1,y2)]=1
                else:
                    continue
        for X in new_black:
            grid[X[0]][X[1]]=1
        new=[]
        new=new_black
        #print(new_black)
    return time    

H,W=list(map(int,raw_input().strip().split(' ')))
A=[]
for _ in xrange(H):
    A+=[raw_input()]
grid=parse(A)
print(find(grid))

Submission status: Accepted

Solution code:
import numpy as np

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

INF = H * W

dp = np.full((H, W), INF, dtype=np.int)

for i in range(H):
	for j in range(W):
		dp[i, j] = 0 if A[i][j] == '#' else dp[i, j]

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

print(np.max(dp))

Submission status: Accepted

Solution code:
import sys
H, W = map(int, sys.stdin.readline().split())
INF = float('inf')
S = [[INF] * W for i in range(H)]
for i in range(H):
    a = list(sys.stdin.readline())
    for j in range(W):
        if a[j] == '#':
            S[i][j] = 0

ma = 0
for i in range(1, H):
    for j in range(W):
        S[i][j] = min(S[i][j], S[i - 1][j] + 1)

for i in range(H - 2, -1, -1):
    for j in range(W):
        S[i][j] = min(S[i][j], S[i + 1][j] + 1)

for i in range(H):
    for j in range(1, W):
        S[i][j] = min(S[i][j], S[i][j - 1] + 1)

for i in range(H):
    for j in range(W - 2, -1, -1):
        S[i][j] = min(S[i][j], S[i][j + 1] + 1)

for i in range(H):
    for j in range(W):
        ma = max(ma, S[i][j])

print(ma)

Submission status: Accepted

Solution code:
###############################################################################

from bisect import bisect_left as binl
from copy import copy

def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


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


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * sy) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


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


def safe_ref(listlist, x, y):
    if x < 0 or y < 0 or x >= len(listlist) or y >= len(listlist[0]):
        return None
    try:
        return listlist[x][y]
    except:
        return None

def main():
    h, w = intin()
    alistlist = []
    for i in range(h):
        alistlist.append([s for s in input()])

    count = 0
    check_list = []

    for i, alist in enumerate(alistlist):
        for j, a in enumerate(alist):
            if a == '#':
                count += 1
                check_list.append((i, j))

    for repeated in range(h * w * 3):
        if count == h * w:
            print(repeated)
            return

        new_alistlist = copy(alistlist)
        next_list = []

        for i, j in check_list:
            if safe_ref(alistlist, i+1, j) == '.':
                new_alistlist[i+1][j] = '#'
                next_list.append((i+1, j))
                count += 1
            if safe_ref(alistlist, i-1, j) == '.':
                new_alistlist[i-1][j] = '#'
                next_list.append((i-1, j))
                count += 1
            if safe_ref(alistlist, i, j+1) == '.':
                new_alistlist[i][j+1] = '#'
                next_list.append((i, j+1))
                count += 1
            if safe_ref(alistlist, i, j-1) == '.':
                new_alistlist[i][j-1] = '#'
                next_list.append((i, j-1))
                count += 1

        check_list = next_list
        alistlist = new_alistlist


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    h, w = map(int, raw_input().split())
    aa = []
    for _ in xrange(h):
        aa.append(raw_input())
    q = []
    dist = [[False] * w for _ in xrange(h)]
    for y in xrange(h):
        row = aa[y]
        for x in xrange(w):
            if row[x] == '#':
                dist[y][x] = True
                q.append([x, y])
    m = 0
    nexts = []
    while True:
        for x, y in q:
            for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                xx = x + dx
                yy = y + dy
                if 0 <= xx < w and 0 <= yy < h:
                    if aa[yy][xx] == '.' and not dist[yy][xx]:
                        dist[yy][xx] = True
                        nexts.append([xx, yy])
        if nexts:
            m += 1
            q = nexts
            nexts = []
        else:
            break
    print m


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
masu = []
for i in range(H):
    masu.append(list(input()))
black = []
for i in range(H):
    for j in range(W):
        if masu[i][j] == "#":
            black.append([i,j])
ans = -1
while len(black) != 0:
    ans += 1
    blacktemp = black[:]
    black = []
    for k in blacktemp:
        for i, j in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
            if 0 <= k[0] + i <= H-1 and 0 <= k[1] + j <= W-1:
                if masu[k[0]+i][k[1]+j] == ".":
                    masu[k[0]+i][k[1]+j] = "#"
                    black.append([k[0]+i, k[1]+j])
print(ans)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.head = None
        self.last = None
        self._size = 0

    def enqueue(self, data):
        if self.last is None:
            self.head = Node(data)
            self.last = self.head
        else:
            self.last.next = Node(data)
            self.last = self.last.next
            
        self._size += 1

    def dequeue(self):
        if self.head is None:
            return None
        else:
            to_return = self.head.data
            self.head = self.head.next
            self._size -= 1
            
            if self._size == 0:
                self.head = None
                self.last = None
            return to_return
        
    def size(self):
        return self._size
    
def inside(y,x,H,W):
    if 0<=y<H and 0<=x<W:
        return True
    else:
        return False
    
def addQueueIfPossible(new_y, new_x, new_val, data, queue):
    if inside(new_y, new_x, H, W) and data[new_y][new_x]==-1:
        data[new_y][new_x] = new_val
        queue.enqueue((new_y, new_x, new_val))
        return True
    else:
        return False

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

data = []
for _ in range(H):
    data.append([0 if it=='#' else -1 for it in input()])



queue = Queue()
for y in range(H):
    for x in range(W):
        if data[y][x] == 0:
            queue.enqueue((y,x,0))

while queue.size() > 0:
    y, x, val = queue.dequeue()
    # up
    addQueueIfPossible(y-1, x, val+1, data, queue)
    # down
    addQueueIfPossible(y+1, x, val+1, data, queue)
    # right
    addQueueIfPossible(y, x+1, val+1, data, queue)
    # down
    addQueueIfPossible(y, x-1, val+1, data, queue)

print(val)

Submission status: Accepted

Solution code:
BLACK = '#'
WHITE = '.'
sizeI, sizeJ = map(int, input().split())
a = [list(input()) for _ in range(sizeI)]

nBlack = 0
curStep = []
for i in range(sizeI):
    for j in range(sizeJ):
        if a[i][j] == BLACK:
            nBlack += 1
            curStep.append((i, j))
need = sizeI * sizeJ
ret = 0
while nBlack != need:
    nextStep = []
    for i, j in curStep:
        for di, dj in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            ni, nj = i + di, j + dj
            if 0 <= ni < sizeI and 0 <= nj < sizeJ and a[ni][nj] == WHITE:
                a[ni][nj] = BLACK
                nBlack += 1
                nextStep.append((ni, nj))
    ret += 1
    curStep = nextStep
print(ret)

Submission status: Accepted

Solution code:

from collections import defaultdict, deque
def inpl(): return list(map(int, input().split()))

H, W = inpl()
searched = [[10**9]*(W+2) for _ in range(H+2)]

for h in range(H+2):
    searched[h][0] = 0
    searched[h][-1] = 0
for w in range(W+2):
    searched[0][w] = 0
    searched[-1][w] = 0

Q = deque()
for h in range(H):
    for w, c in enumerate(input()):
        if c == "#":
            searched[h+1][w+1] = 0
            Q.append((h+1, w+1, 0))

while Q:
    h, w, c = Q.popleft()
    if searched[h][w] < c:
        continue
    for dh, dw in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
        nh, nw = h+dh, w+dw
        if searched[nh][nw] > c+1:
            searched[nh][nw] = c+1
            Q.append((nh, nw, c+1))

print(max(map(max, searched)))

Submission status: Accepted

Solution code:
from collections import deque

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

L = [[float("inf") for x in range(W)] for y in range(H)]



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

Q = deque()

for y in range(H) :
    for x in range(W) :
        if A[y][x] != "#" :
            continue
        
        L[y][x] = 0
        
        Q.append((y,x))

while Q :
    y,x = Q.popleft()

    for dy,dx in dxy :
        ny = y+dy
        nx = x+dx

        if (ny < 0) or (ny >= H) or (nx < 0) or (nx >= W) :
            continue

        if L[ny][nx] <= (L[y][x] + 1) :
            continue
        
        L[ny][nx] = L[y][x] + 1
        
        Q.append((ny,nx))

ans = 0

for y in range(H) :
    ans = max(ans, max(L[y]))
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int, input().split())
a=[[i for i in input()] for j in range(h)]
q=[]
ans=-1
for i in range(h):
    for j in range(w):
        if(a[i][j]=="#"):
            q.append([i,j])
while len(q)>0:
    tl=q
    q=[]
    for i in tl:
        y=i[0]
        x=i[1]
        if(y>0):
            if(a[y-1][x]=="."):
                a[y-1][x]="#"
                q.append([y-1,x])
        if(x>0):
            if(a[y][x-1]=="."):
                a[y][x-1]="#"
                q.append([y,x-1])
        if(y<h-1):
            if(a[y+1][x]=="."):
                a[y+1][x]="#"
                q.append([y+1,x])
        if(x<w-1):
            if(a[y][x+1]=="."):
                a[y][x+1]="#"
                q.append([y,x+1])
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from collections import deque
h,w=map(int,input().split())
MAP=[list(input().strip()) for _ in range(h)]
q=deque()
for i,M in enumerate(MAP):
    for j,m in enumerate(M):
        if m=='#':
            q.append((i,j,0))
delta=[(1,0),(-1,0),(0,1),(0,-1)]
ans=0
while q:
    x,y,d=q.popleft()
    ans=max(ans,d)
    for dx,dy in delta:
        if 0<=x+dx<h and 0<=y+dy<w:
            if MAP[x+dx][y+dy]=='.':
                MAP[x+dx][y+dy]='#'
                q.append((x+dx,y+dy,d+1))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
G = [input() for _ in range(H)]
dist = [0]*(H*W)
bn = 0
B = deque()
geta = W
for i, g in enumerate(G):
    for j, f in enumerate(g):
        if f == '#':
            bn += 1
            B.append(i*geta + j)
visited = set(B)
while bn < H*W:
    if not B:
        break
    dh, dw = divmod(B.pop(), geta)
    dhw = dh * geta + dw
    for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        ni, nj = dh + di, dw + dj
        if not (0 <= ni <= H - 1) or not (0 <= nj <= W - 1):
            continue
        nij = ni * geta + nj
        if nij in visited or G[ni][nj] == '#':
            continue
        visited.add(nij)
        dist[nij] = 1 + dist[dhw]
        B.appendleft(nij)
print(max(dist))

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
B = [input() for _ in range(H)]
BB = [[1<<30]*W for _ in range(H)]
for y in range(H):
    p=1<<30
    for x in range(W):
        p+=1
        if B[y][x]=="#":
            p=0
        BB[y][x] = p

    p = 1 << 30
    for x in range(W-1,-1,-1):
        p += 1
        if B[y][x] == "#":
            p = 0
        p = min(p, BB[y][x])
        BB[y][x] = p
#print(BB)
ans = 0
for x in range(W):
    p = 1 << 30
    for y in range(H):
        p = min(p+1, BB[y][x])
        BB[y][x] = p

    p = 1 << 30
    for y in range(H - 1, -1, -1):
        p = min(p+1, BB[y][x])
        ans = max(ans, p)
        BB[y][x] = p
#print(BB)
print(ans)

Submission status: Accepted

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

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

ANS=[[-1]*W 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[i][j]=0

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

        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])
            ANS[nx][ny]=z+1

    QUE=NQUE

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    h,w = map(int,input().split())
    a = []
    for i in range(h):
        inp = list(input())
        a.append(inp)
    
    dp = [[10**9]*w for i in range(h)]
    
    for i in range(h):
        for j in range(w):
            if a[i][j] == '.' and [i,j] != [0,0]:
                if i >= 1:
                    dp[i][j] = dp[i-1][j]+1
                    if j >= 1:
                        dp[i][j] = min(dp[i][j],dp[i][j-1]+1)
                else:
                    dp[i][j] = dp[i][j-1]+1
            elif a[i][j] == '#':
                dp[i][j] = 0
    for i in range(h):
        for j in range(w-1,-1,-1):
            if a[i][j] == '.' and [i,j] != [0,w-1]:
                if i >= 1:
                    dp[i][j] = min(dp[i-1][j]+1,dp[i][j])
                    if j+1 <= w-1:
                        dp[i][j] = min(dp[i][j],dp[i][j+1]+1)
                else:
                    dp[i][j] = min(dp[i][j+1]+1,dp[i][j])
    for i in range(h-1,-1,-1):
        for j in range(w):
            if a[i][j] == '.' and [i,j] != [h-1,0]:
                if i+1 <= h-1:
                    dp[i][j] = min(dp[i+1][j]+1,dp[i][j])
                    if j >= 1:
                        dp[i][j] = min(dp[i][j],dp[i][j-1]+1)
                else:
                    dp[i][j] = min(dp[i][j-1]+1,dp[i][j])
    for i in range(h-1,-1,-1):
        for j in range(w-1,-1,-1):
            if a[i][j] == '.' and [i,j] != [h-1,w-1]:
                if i+1 <= h-1:
                    dp[i][j] = min(dp[i+1][j]+1,dp[i][j])
                    if j+1 <= w-1:
                        dp[i][j] = min(dp[i][j],dp[i][j+1]+1)
                else:
                    dp[i][j] = min(dp[i][j+1]+1 ,dp[i][j])
        
    res = -1
    for i in range(h):
        for j in range(w):
            res = max(res,dp[i][j])

    print(res)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())

from collections import deque

q = deque([])

field = [input() for _ in range(h)]
black = [[0 for j in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
        if field[i][j] == "#":
            black[i][j] = 1
            q.append((i, j, 0))

dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]
ans = 0
while q:
    i, j, dist = q.popleft()
    for di, dj in dir:
        ni = i + di
        nj = j + dj
        if (0 <= ni and ni <= h-1) and (0 <= nj and nj <= w-1) and black[ni][nj] == 0:
            black[ni][nj] = 1
            ans = dist + 1
            q.append((ni, nj, dist + 1))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

q = deque()
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            q.append((h, w))

dh = [1, -1, 0, 0]
dw = [0, 0, 1, -1]
ans = 0

while len(q):
    ans += 1
    n = len(q)
    for i in range(n):
        h, w = q.popleft()
        for j in range(4):
            nh = h + dh[j]
            nw = w + dw[j]
            if nh >= H or nh < 0 or nw >= W or nw < 0:
                continue
            if A[nh][nw] == '.':
                A[nh][nw] = '#'
                q.append((nh, nw))

print(ans - 1)

Submission status: Accepted

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]
for d, i, j in q:
    visited[i][j] = True

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

while q:
    d, i, j = q.popleft()
    ans = d
    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
        visited[ni][nj] = True
        q.append((d + 1, ni, nj))

print(ans)

Submission status: Accepted

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()
    po = q.popleft
    pu = q.append
    a = [100000] * (h * w)
    for i, r in enumerate(s):
        for j, c in enumerate(r):
            if c == '#':
                pu((i, j))
                a[i*w+j] = 0
    dd = ((0, -1), (0, 1), (1, 0), (-1, 0))
    while q:
        x, y = po()
        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
                pu((nx, ny))
    print z - 1
main()

Submission status: Accepted

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

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: Accepted

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*w+j)


    r = 0
    u = t | set()
    while 1:
        k = set()
        for ij in t:
            i = ij // w
            j = ij % w
            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*w + nj
                if nk in u:
                    continue
                k.add(nk)
        if not k:
            break
        r += 1
        t = k
        u |= k

    return r


print(main())

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
from collections import deque

INF = float('inf')
MOD = 10 ** 9 + 7
dy, dx = (0, -1, 0, 1), (1, 0, -1, 0)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    h, w = LI()
    B = [list(SI()) for _ in range(h)]

    D = deque()
    for i, row in enumerate(B):
        for j, c in enumerate(row):
            if c == '#':
                D.append((i, j, 0))

    while D:
        y, x, cnt = D.popleft()
        for i in range(4):
            yy = y + dy[i]
            xx = x + dx[i]

            if 0 <= yy < h and 0 <= xx < w:
                if B[yy][xx] == '#':
                    continue
                B[yy][xx] = '#'
                D.append((yy, xx, cnt + 1))

    print(cnt)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
range = xrange
input = lambda: sys.stdin.readline().rstrip()

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

found = [False]*(w*h)

cur = []
for y in range(h):
    for x in range(w):
        if A[y][x]=='#':
            cur.append(y*w+x)
            found[y*w+x]=True


counter = 0
while cur:
    counter += 1
    tmp = []
    
    while cur:
        ind = cur.pop()
        y,x = divmod(ind,w)

        if 0<=x-1 and not found[ind-1]:
            tmp.append(ind-1)
            found[ind-1] = True
        if x+1<w and not found[ind+1]:
            tmp.append(ind+1)
            found[ind+1] = True

        if 0<=y-1 and not found[ind - w]:
            tmp.append(ind - w)
            found[ind-w] = True
    
        if y+1<h and not found[ind + w]:
            tmp.append(ind + w)
            found[ind+w] = True
    cur = tmp

print counter-1

Submission status: Accepted

Solution code:
import collections

h,w = map(int, input().split())
cells = []
for i in range(h):
    row = input()
    cells.append([c == '#' for c in row])

blacks = collections.deque()

for i in range(h):
    for j in range(w):
        if cells[i][j]:
            blacks.append((i,j,0))
res = 0
while blacks:
    y,x,c = blacks.popleft()
    for dy,dx in ((-1, 0), (1, 0), (0, -1), (0,1)):
        if 0<=y+dy<h and 0<=x+dx<w and not cells[y+dy][x+dx]:
            cells[y+dy][x+dx] = True
            blacks.append((y+dy, x+dx, c+1))
            res = c+1
print(c)