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: Wrong Answer

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

def searchBlackIdx(area):
    blackIdx = []
    
    for i in range(H):
        for j in range(W):
            if area[i][j] == '#':
                blackIdx.append([i, j])
    
    return blackIdx

def calcDist(startIdxes, area):
    dist = [[-1 for i in range(W)] for i in range(H)]
    for startIdx in startIdxes:
        dist[startIdx[0]][startIdx[1]] = 0
    que = startIdxes
    
    while len(que) != 0:
        idx = que.pop(0)
        
        if idx[0]-1 >= 0 and dist[idx[0]-1][idx[1]] == -1 and area[idx[0]-1][idx[1]] != '#':
            dist[idx[0]-1][idx[1]] = dist[idx[0]][idx[1]] + 1
            area[idx[0]-1][idx[1]] = '#'
            que.append([idx[0]-1, idx[1]])
        
        if idx[0]+1 < H and dist[idx[0]+1][idx[1]] == -1 and area[idx[0]+1][idx[1]] != '#':
            dist[idx[0]+1][idx[1]] = dist[idx[0]][idx[1]] + 1
            area[idx[0]+1][idx[1]] = '#'
            que.append([idx[0]+1, idx[1]])
        
        if idx[1]-1 >= 0 and dist[idx[0]][idx[1]-1] == -1 and area[idx[0]][idx[1]-1] != '#':
            dist[idx[0]][idx[1]-1] = dist[idx[0]][idx[1]] + 1
            area[idx[0]][idx[1]-1] = '#'
            que.append([idx[0], idx[1]-1])
        
        if idx[1]+1 < W and dist[idx[0]][idx[1]+1] == -1 and area[idx[0]][idx[1]+1] != '#':
            dist[idx[0]][idx[1]+1] = dist[idx[0]][idx[1]] + 1
            area[idx[0]][idx[1]+1] = '#'
            que.append([idx[0], idx[1]+1])
    
    return dist

startIdx = searchBlackIdx(area)
ans = 0

dist = calcDist(startIdx, area)
a = max(dist)
b = max(a)
print(b)

Submission status: Wrong Answer

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

def searchBlackIdx(area):
    blackIdx = []
    
    for i in range(H):
        for j in range(W):
            if area[i][j] == '#':
                blackIdx.append([i, j])
    
    return blackIdx

def calcDist(startIdx, area):
    dist = [[2000 for i in range(W)] for i in range(H)]
    dist[startIdx[0]][startIdx[1]] = 0
    que = [startIdx]
    
    while len(que) != 0:
        idx = que.pop(0)
        
        if idx[0]-1 >= 0 and dist[idx[0]-1][idx[1]] == 2000 and area[idx[0]-1][idx[1]] != '#':
            dist[idx[0]-1][idx[1]] = dist[idx[0]][idx[1]] + 1
            que.append([idx[0]-1, idx[1]])
            
        if idx[0]+1 < H and dist[idx[0]+1][idx[1]] == 2000 and area[idx[0]+1][idx[1]] != '#':
            dist[idx[0]+1][idx[1]] = dist[idx[0]][idx[1]] + 1
            que.append([idx[0]+1, idx[1]])
        
        if idx[1]-1 >= 0 and dist[idx[0]][idx[1]-1] == 2000 and area[idx[0]][idx[1]-1] != '#':
            dist[idx[0]][idx[1]-1] = dist[idx[0]][idx[1]] + 1
            que.append([idx[0], idx[1]-1])
        
        if idx[1]+1 < W and dist[idx[0]][idx[1]+1] == 2000 and area[idx[0]][idx[1]+1] != '#':
            dist[idx[0]][idx[1]+1] = dist[idx[0]][idx[1]] + 1
            que.append([idx[0], idx[1]+1])
        
        if area[idx[0]-1][idx[1]] == '#':
            break
    
    return dist

startIdx = searchBlackIdx(area)
ans = [[2000 for i in range(H)] for i in range(W)]
while len(startIdx) != 0:
    idx = startIdx.pop()
    dist = calcDist(idx, area)
    ans = [[min(l) for l in zip(x,y)] for x,y in zip(ans, dist)]
    
print(ans)

print(max([x for i in ans for x in i if x != 2000]))

Submission status: Wrong Answer

Solution code:
import collections

h, w = map(int, input().split())

visited = [[-float("inf")]*(w) for _ in range(h)]
q = collections.deque([])

a = []
for i in range(h):
    _a = list(input())
    a.append(_a)
    for j in range(w):
        if _a[j] == "#":
            q.appendleft([i, j])
            visited[i][j] = 0

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

ans = -1

while 0 < len(q):
    cy, cx = q.pop()
    for _dx, _dy in zip(dx, dy):
        x = cx + _dx
        y = cy + _dy

        if x < 0 or w <= x or y < 0 or h <= y:
            continue

        if a[y][x] == "." and visited[y][x] == -float("inf"):
            visited[y][x] = visited[cy][cx] + 1
            ans = max(ans, visited[y][x])
            q.appendleft([y, x])

print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
from itertools import product

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

ans = 0
while True:
    ans += 1
    target = deepcopy(grid)
    for y, x in product(range(H), range(W)):
        if grid[y][x] == "#":
            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:
                    target[ny][nx] = "#"
    for line in target:
        if set(line) != {"#"}:
            break
    else:
        break
    grid = target

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
  H, W = map(int, input().split())
  G = [list(input()) for _ in range(H)]
  direction = [[0,1],[0,-1],[1,0],[-1,0]]
  black = np.zeros((H,W))
  que = []
  ans = 0
  for i in range(H):
    for j in range(W):
      if G[i][j] == '#':
        que.append([i,j])
        black[i][j] = 0
  while que:
    qq = []
    ans += 1
    for nh, nw in que:
      dh, dw = 0,1
      if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
        qq.append([nh+dh,nw+dw])
        black[nh+dh][nw+dw] = black[nh][nw]+1
      dh, dw = 0,-1
      if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
        qq.append([nh+dh,nw+dw])
        black[nh+dh][nw+dw] = black[nh][nw]+1
      dh, dw = 1,0
      if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
        qq.append([nh+dh,nw+dw])
        black[nh+dh][nw+dw] = black[nh][nw]+1
      dh, dw = -1,0
      if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
        qq.append([nh+dh,nw+dw])
        black[nh+dh][nw+dw] = black[nh][nw]+1
    que = qq
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
  H, W = map(int, input().split())
  G = [list(input()) for _ in range(H)]
  direction = [[0,1],[0,-1],[1,0],[-1,0]]
  black = np.zeros((H,W))
  que = []
  ans = 0
  for i in range(H):
    for j in range(W):
      if G[i][j] == '#':
        que.append([i,j])
        black[i][j] = 0
  while que:
    qq = []
    ans += 1
    for nh, nw in que:
      dh, dw = 0,1
      if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
        qq.append([nh+dh,nw+dw])
        black[nh+dh][nw+dw] = black[nh][nw]+1
      dh, dw = 0,-1
      if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
        qq.append([nh+dh,nw+dw])
        black[nh+dh][nw+dw] = black[nh][nw]+1
      dh, dw = 1,0
      if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
        qq.append([nh+dh,nw+dw])
        black[nh+dh][nw+dw] = black[nh][nw]+1
      dh, dw = -1,0
      if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
        qq.append([nh+dh,nw+dw])
        black[nh+dh][nw+dw] = black[nh][nw]+1
    que = qq
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
from collections import deque
def main():
  h,w=map(int,input().split())
  hw=h*w
  maze=[list(input()) for i in range(h)]
  visited=[[hw]*w for i in range(h)]
  ans,b,q=0,[],deque()
  for i in range(h):
    for j in range(w):
      if maze[i][j]=='#':
        q.append((i,j))
        visited[i][j]=0
  while q:
    x,y=q.popleft()
    for i,j in ((0,1),(1,0),(-1,0),(0,-1)):
      newx,newy=x+i,y+j
      if 0<=newx<h and 0<=newy<w:
        if maze[newx][newy]!='#' and visited[newx][newy]==float('inf'):
          visited[newx][newy]=visited[x][y]+1
          q.append((newx,newy))
          ans=max(ans,visited[newx][newy])
  return print(ans)
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
import numpy as np
input = sys.stdin.readline
h,w=map(int, input().split(' '))
a = [list(input()) for i in range(h)]
b = np.zeros((h,w),dtype=np.int64)
q = deque()
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            q.append([i,j,0])
        else:
            b[i][j]=-1
"""
while q:
    [s,t,cnt] = q.popleft()
    if s>0 and a[s-1][t] == -1:
        q.append([s-1,t,cnt+1])
        a[s-1][t] = cnt+1
    if s<h-1 and a[s+1][t] == -1:
        q.append([s+1,t,cnt+1])
        a[s+1][t] = cnt+1
    if t>0 and a[s][t-1] == -1:
        q.append([s,t-1,cnt+1])
        a[s][t-1] = cnt+1
    if t<w-1 and a[s][t+1] == -1:
        q.append([s,t+1,cnt+1])
        a[s][t+1] = cnt+1
ans = 0
for i in range(h):
    ans = max(ans,max(a[i]))
print(ans)
"""

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
h,w=map(int, input().split())
l=[]
d=[]
c=0
s=[[False for j in range(w)] for i in range(h)]
for i in range(h):
	l.append(list(input()))
for i in range(h):
	for j in range(w):
		if(l[i][j]=='#'):
			c+=1
			d.append((i,j))
			s[i][j]=True
count=0
while(len(d)!=0):
	print(d)
	count+=1
	k=len(d)
	for i in range(k):
		a,b=d.pop(0)
		if(a-1>=0 and s[a-1][b]==False):
			d.append((a-1,b))
			s[a-1][b]=True
			c+=1
		if(a+1<h and s[a+1][b]==False):
			d.append((a+1,b))
			s[a+1][b]=True
			c+=1
		if(b-1>=0 and s[a][b-1]==False):
			d.append((a,b-1))
			s[a][b-1]=True
			c+=1
		if(b+1<w and s[a][b+1]==False):
			d.append((a,b+1))
			s[a][b+1]=True
			c+=1
print(count)

Submission status: Wrong Answer

Solution code:
h,w=map(int, input().split())
l=[]
d=[]
c=0
s=[[False for j in range(w)] for i in range(h)]
for i in range(h):
	l.append(list(input()))
for i in range(h):
	for j in range(w):
		if(l[i][j]=='#'):
			c+=1
			d.append((i,j))
			s[i][j]=True
count=0
while(True):
	if(c>=h*w):
		break
	count+=1
	k=len(d)
	for i in range(k):
		a,b=d.pop()
		if(a-1>=0 and s[a-1][b]==False):
			d.append((a-1,b))
			s[a-1][b]=True
			c+=1
		if(a+1<h and s[a+1][b]==False):
			d.append((a+1,b))
			s[a+1][b]=True
			c+=1
		if(b-1>=0 and s[a][b-1]==False):
			d.append((a,b-1))
			s[a][b-1]=True
			c+=1
		if(b+1<w and s[a][b+1]==False):
			d.append((a,b+1))
			s[a][b+1]=True
			c+=1
print(count)

Submission status: Wrong Answer

Solution code:
h,w=map(int, input().split())
l=[]
d=[]
c=0
s=set()
for i in range(h):
	l.append(list(input()))
for i in range(h):
	for j in range(w):
		if(l[i][j]=='#'):
			c+=1
			d.append((i,j))
			s.add((i,j))
count=0
while(True):
	if(c>=h*w):
		break
	count+=1
	k=len(d)
	for i in range(k):
		a,b=d.pop()
		if(a-1>=0 and b not in s):
			d.append((a-1,b))
			s.add((a-1,b))
			c+=1
		if(a+1<h and b not in s):
			d.append((a+1,b))
			s.add((a+1,b))
			c+=1
		if(b-1>=0 and b-1 not in s):
			d.append((a,b-1))
			s.add((a,b-1))
			c+=1
		if(b+1<w and b+1 not in s):
			d.append((a,b+1))
			s.add((a,b+1))
			c+=1
print(count)

Submission status: Wrong Answer

Solution code:
h,w=map(int, input().split())
l=[]
d=[]
c=0
s=[set() for i in range(h)]
for i in range(h):
	l.append(list(input()))
for i in range(h):
	for j in range(w):
		if(l[i][j]=='#'):
			c+=1
			d.append((i,j))
			s[i].add(j)
count=0
while(True):
	if(c>=h*w):
		break
	count+=1
	k=len(d)
	for i in range(k):
		a,b=d.pop()
		if(a-1>=0 and b not in s[a-1]):
			d.append((a-1,b))
			s[a-1].add(b)
			c+=1
		if(a+1<h and b not in s[a+1]):
			d.append((a+1,b))
			s[a+1].add(b)
			c+=1
		if(b-1>=0 and b-1 not in s[a]):
			d.append((a,b-1))
			s[a].add(b-1)
			c+=1
		if(b+1<w and b+1 not in s[a]):
			d.append((a,b+1))
			s[a].add(b+1)
			c+=1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

visited = [[-1] * w for _ in range(h)]
que = deque()
for i in range(h):
    for j in range(w):
        if map[i][j] == "#":
            visited[i][j] = 0
            que.append((i, j))

ans = 0
while que:
    y, x = que.popleft()
    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        next_y, next_x = y + i, x + j
        ans = visited[y][x]
        if -1 < next_y < h or -1 < next_x < w:
            continue
        elif visited[next_y][next_x] == f_inf:
            visited[next_y][next_x] = visited[y][x] + 1
            que.append((next_y, next_x))

print(int(ans))

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
maiz = []
black = []
white = 0
for i in range(h):
    line = list(input())
    for j in range(w):
        if line[j] == '#':
            black.append([j, i])
        else:
            white += 1
    maiz.append(line)
print(black)
print(white)

def paint(black, white, maiz):
    new_black = []
    for bx, by in black:
        hjkl = [[bx-1, by], [bx, by-1], [bx+1, by], [bx, by+1]]
        for dx, dy in hjkl:
            if (dx<0) or (dx>w-1) or (dy<0) or (dy>h-1):
                continue
            if maiz[dy][dx] == '.':
                maiz[dy][dx] = '#'
                new_black.append([dx, dy])
                white -=1
    return new_black, white, maiz

ans = 0
while white > 0:
    black, white, maiz = paint(black, white, maiz)
    ans += 1
    #print("i:{} ans:{}".format(i, ans))
    #print('black', black)
    #print('white', white)
    #for i in maiz:
    #    print(i)

print(ans)

Submission status: Wrong Answer

Solution code:
from subprocess import call
call (('pypy3', '-c', """

def bfs():
    #global ans
    d = [[float("inf")] * w for _ in range(h)]
    que = []
    for i in range(h):
        for j in range(w):
           if A[i][j] == "#":
               que.append([i, j])
               d[i][j] = 0
            
    while que:
        p = que.popleft()
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4): 
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < h and 0 <= ny < w and A[nx][ny] != "#" and d[nx][ny] == float("inf"):
                d[nx][ny] = d[p[0]][p[1]] + 1
                A[nx][ny] = "#"
                que.append([nx, ny])
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, d[i][j])


h, w = map(int, input().split())
A = [list(input()) for _ in range(h)]
ans = 0
bfs()

print(ans)

"""))

Submission status: Wrong Answer

Solution code:
from subprocess import call
call(('pypy3','-c',"""



from collections import deque
def main():
  h,w=map(int,input().split())  
  mp=["#"*(w+2)]+["#"+input()+"#" for _ in range(h)]+["#"*(w+2)]
  dist=[-1]*((h+2)*(w+2))
  q=deque()
  
  for i in range(h+2):
    for j in range(w+2):
      if mp[i][j]=="#":
        q.append(i*w+j)
        dist[i*w+j]=0
      else:
        dist[i*w+j]=-1
  #print(q)
 
  while q:
    c=q.popleft()
    x=c//w
    y=c%w
    for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
      xx,yy=x+i,y+j
      tmp=xx*w+yy
      if dist[tmp]==-1:
        dist[tmp]=dist[c]+1
        q.append(tmp)
      
  print(max(dist))
  return

main()


"""))

Submission status: Wrong Answer

Solution code:
#場所を一次元で持つといいらしい
def main():
  h,w=map(int,input().split()) 
  #1<=h,w<=1000
  mp=[(input()) for _ in range(h)]
  
  used=[True]*(h*w)
  
  q=[]
  for i in range(h):
    for j in range(w):
      if mp[i][j]=="#": #壁ですよ
        q.append(i*w+j)
        used[i*w+j]=False
      
  ans=0     
  while q:
    qq=[] #new_list qq
    for p in q:
      for i in [1,-1,w,-w]:
        pp=p+i
        if 0<=pp<h*w and used[pp]==True:
          qq.append(pp)
          used[pp]=False
    q=qq #qと置き換え
    ans+=1        
  print(ans-1) #ラスト無駄に一回足してる分｡
  return

main()

Submission status: Wrong Answer

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

import queue


nums=list(map(int,input().split()))
H = nums[0]
W = nums[1]

INF = 10**9
field = [[None for i in range(W)] for j in range(H)]
check = [[INF for i in range(W)] for j in range(H)]

black = 0

for i in range(H):
    str1 = input()
    for j in range(W):
        field[i][j] = str1[j]

            

for i in range(H):
    for j in range(W):
        if field[i][j] == "#":
            check[i][j] = 0
        elif j-1 >= 0 and check[i][j - 1] != INF:
            check[i][j] = check[i][j-1] + 1

for i in range(H):
    for j in range(W-1, -1, -1):
        if field[i][j] == "#":
            check[i][j] = 0
        elif j < W-1 and check[i][j + 1] != INF:
            check[i][j] = check[i][j + 1] + 1
            

for i in range(W):
    for j in range(H-1, -1, -1):
        if field[j][i] == "#":
            check[j][i] = 0
        elif j < H-1 and check[j + 1][i] != INF:
            check[j][i] = check[j + 1][i] + 1
for i in range(W):
    for j in range(H):
        if field[j][i] == "#":
            check[j][i] = 0
        elif j-1>0 and check[j - 1][i] != INF:
            check[j][i] = check[j - 1][i] + 1
print(max(max(check)))

Submission status: Wrong Answer

Solution code:
#A - Darker and Darker
import copy
import sys
from collections import deque
H,W = (int(i) for i in input().split())
s_tmp = []
for _ in range(H):
    s_tmp.append(list(input()))
d = [[1, 0], [-1, 0], [0, 1], [0, -1]]
q = deque()
s = copy.deepcopy(s_tmp)
flg = False

cnt = 0
dot_cnt = 0

for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            q.append([i,j])
        elif s[i][j] == '.':
            dot_cnt += 1
                
while dot_cnt > 0:
    
    cnt += 1
    dot_cnt = 0
    for i in range(H):
        for j in range(W):
            if s[i][j] == 'y':
                q.append([i,j])
            elif s[i][j] == '.':
                dot_cnt += 1

    while len(q) > 0:
        #print(q)
        node = q.popleft()#qから左端を取り出す(幅優先)
        if node is not None:
            y = node[0]
            x = node[1]
            #上下を探索して移動できるところをスタックする
            for dx, dy in d:
                nx, ny = x + dx, y + dy
                if not (0 <= nx < W and 0 <= ny < H) or s[ny][nx] == '#' or s[ny][nx] == 'y':
                    continue
                else:
                    tmp = [ny,nx]
                    #if s[ny][nx] != 'y':
                        #q.append(tmp)
                    s[ny][nx] = 'y'
print(cnt-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

def main():
    input = sys.stdin.readline  
    H,W = map(int,input().split())
    isVisited = [[False]*W for _ in range(H)]
    queue = deque()

    for i in range(H):
        st = input()
        for j in range(W):
            if st[j] == "#":
                queue.append((i,j))

    answer = 0
    a =  [(0,1),(1,0),(-1,0),(0,-1)]
    while True:
        nqueue = deque()
        while queue:
            i,j = queue.popleft()

            if not isVisited[i][j]:
                isVisited[i][j] = True
                for ix,iy in a:
                    if 0<=i+ix<H and 0<=j+iy<W:
                        nqueue.append((i+ix,j+iy))
        
        if nqueue:
            answer += 1
            queue = nqueue
        else:
            break
 
    print(answer-1)
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

def main():
    input = sys.stdin.readline  
    H,W = map(int,input().split())
    isVisited = [[False]*W for _ in range(H)]
    queue = deque()

    for i in range(H):
        st = input()
        for j in range(W):
            if st[j] == "#":
                queue.append((i,j))

    answer = 0
    a =  [(0,1),(1,0),(-1,0),(0,-1)]
    while True:
        nqueue = deque()
        while queue:
            i,j = queue.popleft()

            isVisited[i][j] = True
            for ix,iy in a:
                if 0<=i+ix<H and 0<=j+iy<W and not isVisited[i+ix][j+iy]:
                    nqueue.append((i+ix,j+iy))
        
        if nqueue:
            answer += 1
            queue = nqueue
        else:
            break
 
    print(answer)
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque


def solve():
    H, W = map(int, input().split())
    grid = [['' for _ in range(W)] for _ in range(H)]
    for i in range(H):
        grid[i] = list(input())
    
    que = deque()
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '#':
                que.append([i, j])
    
    xy = [[0, -1], [1, 0], [0, 1], [-1, 0]]
    ans = 0
    while que:
        n = len(que)
        for _ in range(n):
            y, x = que.popleft()
            for i in range(4):
                xi = x - xy[i][0]
                yi = y - xy[i][1]
                if 0 <= xi <= W-1 and 0 <= yi <= H-1:
                    if grid[yi][xi] == '.':
                        grid[yi][xi] = '#'
                        que.append([xi, yi])
        ans += 1
    print(ans-1)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
h,w=map(int, input().split(' '))
a = [input() for i in range(h)]
nl = [[] for i in range(h)]
q = deque()
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            nl[i].append(0)
            q.append([i,j,0])
        else:
            nl[i].append(-1)
"""
while q:
    [s,t,cnt] = q.popleft()
    if s>0 and nl[s-1][t] == -1:
        q.append([s-1,t,cnt+1])
        nl[s-1][t] = cnt+1
    if s<h-1 and nl[s+1][t] == -1:
        q.append([s+1,t,cnt+1])
        nl[s+1][t] = cnt+1
    if t>0 and nl[s][t-1] == -1:
        q.append([s,t-1,cnt+1])
        nl[s][t-1] = cnt+1
    if t<w-1 and nl[s][t+1] == -1:
        q.append([s,t+1,cnt+1])
        nl[s][t+1] = cnt+1
ans = 0
for i in range(h):
    ans = max(ans,max(nl[i]))
print(ans)
"""

Submission status: Wrong Answer

Solution code:
import numpy as np

h, w = map(int, input().split())
grid = (np.array([list(input())
                  for _ in range(h)]) == "#")
cost = np.full((h, w), 1000, dtype=np.int64)
cost[grid[:, :]] = 0

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

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

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

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

print(np.max(cost))

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
grid=[None]*h
seen=[[-1 for i in range(w)] for j in range(h)]
from collections import deque
que=deque()
for i in range(h):
  grid[i]=list(input())
  for j in range(len(grid[i])):
    if grid[i][j]=="#":
      grid[i][j]="."
      que.append([i,j,0])
      
ans=0
while que:
  node=que.popleft()
  y=node[0]
  x=node[1]
  p=node[2]
  if grid[y][x]=="#":
    continue
  if grid[y][x]==".":
    grid[y][x]="#"
  if y-1>=0:
    que.append([y-1,x,p+1])
  if y+1<h:
    que.append([y+1,x,p+1])
  if x-1>=0:
    que.append([y,x-1,p+1])
  if x+1<w:
    que.append([y,x+1,p+1])
print(max(p,0))

Submission status: Wrong Answer

Solution code:
import copy
h,w=map(int,input().split())
a=[list("."*(w+2))]+[list("."+input()+".") for i in range(h)]+[list("."*(w+2))]
b=copy.deepcopy(a) 
#print(a,b)
ans=0
while ans<h+w-2:
    for i in range(1,h+1):
        for j in range(1,w+1):
            if a[i][j]=='#':
                b[i-1][j]='#'
                b[i+1][j]='#'
                b[i][j-1]='#'
                b[i][j+1]='#'
    #print(a,b)
    if a==b:
        break
    else:
        a=copy.deepcopy(b) 
        ans+=1
print(ans-1)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

h, w = map(int, readline().split())
grid = [[0]*(w) for _ in range(h)]

black = []
for i in range(h):
    for j, k in enumerate(readline()):
        if k == "#":
            black.append((i, j))
            grid[i][j] = 1

ans = 0
d = ((0, 1),
     (1, 0),
     (0, -1),
     (-1, 0),)
while True:
    paint = []
    while black:
        x, y = black.pop()
        for nx, ny in d:
            if x+nx == -1 or x+nx == h or y+ny == -1 or y+ny == w:
                continue
            if not grid[nx + x][ny + y]:
                grid[nx + x][ny + y] = 1
                paint.append((nx + x, ny + y))

    if len(paint) == 0:
        break
    black = paint[:]
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    h,w=map(int,input().split())
    maze=[list(input()) for i in range(h)]
    d=[[float("inf")]*w for i in range(h)]
    que=deque([])
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    for i in range(h):
        for j in range(w):
            if maze[i][j]=="#":
                que.append((i,j))           
                d[i][j]=0
    while que:
        p=que.popleft()
        for i in range(4):
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]
            if 0<=nx and nx<h and 0<=ny and ny<w and maze[nx][ny]!="#" and d[nx][ny]==float("inf"):
                d[nx][ny]=d[p[0]][p[1]]+1
                que.append((nx,ny))  
    return max(max(d))
if __name__=='__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs():
    d=[[float("inf")]*w for i in range(h)]
    que=deque([])
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    for i in range(h):
        for j in range(w):
            if maze[i][j]=="#":
                que.append((i,j))           
                d[i][j]=0
    while que:
        p=que.popleft()
        for i in range(4):
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]
            if 0<=nx and nx<h and 0<=ny and ny<w and maze[nx][ny]!="#" and d[nx][ny]==float("inf"):
                d[nx][ny]=d[p[0]][p[1]]+1
                que.append((nx,ny))  
    return max(max(d))
h,w=map(int,input().split())
maze=[list(input()) for i in range(h)]

print(bfs())

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]

# d = [[2001] * W for _ in range(H)]


def bfs(q):
    res_q = deque()
    while len(q):
        x, y = q.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy

            if (0 <= nx < H) and (0 <= ny < W) and grid[nx][ny] != '#':
                res_q.append((nx, ny))
                grid[nx][ny] = '#'
    return res_q


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

res = 0
while len(q):
    res += 1
    q = bfs(q)

print(res)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy

h,w = map(int, input().split())
s = [["#"]*(w+2)]+[["#"]+list(input())+["#"] for i in range(h)]+[["#"]*(w+2)]
black = -(h+w) * 2 - 4
for i in s:
  black += i.count("#")
s[1][1] = 1
q = deque([(i, j) for i in range(1,h+1) for j in range(1,w+1) if s[i][j] == "#"])
white = 0
while True:
  q2 = deque()
  while q:
    a,b = q.popleft()
    if s[a-1][b] == ".":
      s[a-1][b] = "#"
      q2.append((a-1,b))
    if s[a+1][b] == ".":
      s[a+1][b] = "#"
      q2.append((a+1,b))
    if s[a][b-1] == ".":
      s[a][b-1] = "#"
      q2.append((a,b-1))
    if s[a][b+1] == ".":
      s[a][b+1] = "#"
      q2.append((a,b+1))   
  if q2:
    q = copy.copy(q2)
    white += 1
  else:
    print(white)
    break

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy

h,w = map(int, input().split())
s = [["#"]*(w+2)]+[["#"]+list(input())+["#"] for i in range(h)]+[["#"]*(w+2)]
black = -(h+w) * 2 - 4
for i in s:
  black += i.count("#")
s[1][1] = 1
q = deque([(i, j) for i in range(1,h+1) for j in range(1,w+1) if s[i][j] == "#"])
white = -1
while True:
  q2 = deque()
  white += 1
  while q:
    a,b = q.popleft()
    if s[a-1][b] == ".":
      s[a-1][b] = "#"
      q2.append((a-1,b))
    if s[a+1][b] == ".":
      s[a+1][b] = "#"
      q2.append((a+1,b))
    if s[a][b-1] == ".":
      s[a][b-1] = "#"
      q2.append((a,b-1))
    if s[a][b+1] == ".":
      s[a][b+1] = "#"
      q2.append((a,b+1))   
  if q2:
    q = copy.copy(q2)
  else:
    print(white)
    break

Submission status: Wrong Answer

Solution code:
H, W=map(int, input().split())

m=[[-1 for i in range(W+2)]]
mm=[[-1]+[0 for i in range(W)]+[-1] for j in range(H)]
m=m+mm+m

nexts=[]
for i in range(1, H+1):
  c=input()
  for j in range(1, W+1):
    if c[j-1]=='#':
      nexts.append([i, j])
      m[i][j]=1
      
def f(math, in_nexts):
  n=len(in_nexts)
  out_nexts=[]
  for i in range(n):
    x=in_nexts[i][0]
    y=in_nexts[i][1]
    if math[x-1][y]==0:
      math[x-1][y]=math[x][y]+1
      out_nexts.append([x-1, y])
    if math[x+1][y]==0:
      math[x+1][y]=math[x][y]+1
      out_nexts.append([x+1, y])
    if math[x][y-1]==0:
      math[x][y-1]=math[x][y]+1
      out_nexts.append([x, y-1])
    if math[x][y+1]==0:
      math[x][y+1]=math[x][y]+1
      out_nexts.append([x, y+1])
      
  return math, out_nexts

counter=0
while len(nexts)>0:
  print(nexts)
  m, nexts=f(m, nexts)
  counter+=1
  
print(counter-1)