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:
import copy
import collections
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
s = copy.deepcopy(a)
f = sum(a,[])
c = collections.Counter(f)
cnt = c["#"]
ans = 0
while True:
  ans += 1
  for i in range(h):
    for j in range(w):
      if a[i][j] == "#":
        dh = [-1,0,1,0]
        dw = [0,-1,0,1]
        for k in range(4):
          nh = i + dh[k]
          nw = j + dw[k]
          if 0 <= nh < h and 0 <= nw < w:
            if s[nh][nw] == ".":
              cnt += 1
            s[nh][nw] = "#"
  a = copy.deepcopy(s)
  if cnt == h*w:
    break
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
import collections
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
s = copy.deepcopy(a)
ans = 0
while True:
  ans += 1
  for i in range(h):
    for j in range(w):
      if a[i][j] == "#":
        dh = [-1,0,1,0]
        dw = [0,-1,0,1]
        for k in range(4):
          nh = i + dh[k]
          nw = j + dw[k]
          if 0 <= nh < h and 0 <= nw < w:
            s[nh][nw] = "#"
  a = copy.deepcopy(s)
  f = sum(a,[])
  c = collections.Counter(f)
  if c["#"] == h*w:
    break
print(ans)

Submission status: Wrong Answer

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)]
    colors = [[-1] * 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]):
            # print(j,color)
            colors[i][j] = 0 if color == '#' else -1
            if '#' == color:
                q.append([i,j,0])
                colors[i][j] = 0
            # for i in colors:
            #     print(i)
    mx = 0
    direction = [[1,0],[0,1],[-1,0],[0,-1]]

    while len(q) > 0:
        # print(q)
        tmp = [y,x,op] = q.popleft()
        mx = mx if mx > op else op
        if colors[y][x] > 0 : continue
        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 colors[ny][nx] >= 0:
                    continue
                q.append([ny,nx,op+1])
                colors[y][x] = op+1
    print(mx)

main()

Submission status: Wrong Answer

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)]
    colors = [[-1] * 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]):
            # print(j,color)
            colors[i][j] = 0 if color == '#' else -1
            if '#' == color:
                q.append([i,j,0])
                colors[i][j] = 0

            # for i in colors:
            #     print(i)
    mx = 0
    direction = [[1,0],[0,1],[-1,0],[0,-1]]

    while len(q) > 0:
        print(q)
        tmp = [y,x,op] = q.popleft()
        mx = mx if mx > op else op
        if colors[y][x] >= 0 and mx > 0: continue
        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 colors[ny][nx] >= 0:
                    continue
                colors[ny][nx] = op + 1
                q.append([ny,nx,op+1])

main()

Submission status: Wrong Answer

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)]
    colors = [[-1] * 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]):
            # print(j,color)
            colors[i][j] = 0 if color == '#' else -1
            if '#' == color:
                q.append([i,j,0])
            # for i in colors:
            #     print(i)
    mx = 0
    direction = [[1,0],[0,1],[-1,0],[0,-1]]

    while len(q) > 0:
        # print(q)
        tmp = [y,x,op] = q.popleft()
        mx = mx if mx > op else op
        if colors[y][x] >= 0 and mx > 0: continue
        colors[y][x] = 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 colors[ny][nx] >= 0:
                    continue
                q.append([ny,nx,op+1])
    print(mx)

main()

Submission status: Wrong Answer

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)]
    colors = [[-1] * 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]):
            # print(j,color)
            colors[i][j] = 0 if color == '#' else -1
            if '#' == color:
                q.append([i,j,0])
                colors[i][j] = 0
            # for i in colors:
            #     print(i)
    mx = 0
    direction = [[1,0],[0,1],[-1,0],[0,-1]]

    while len(q) > 0:
        # print(q)
        tmp = [y,x,op] = q.popleft()
        mx = mx if mx > op else op
        if colors[y][x] >= 0 and mx > 0: continue
        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 colors[ny][nx] >= 0:
                    continue
                q.append([ny,nx,op+1])
                colors[y][x] = op+1
    print(mx)

main()

Submission status: Wrong Answer

Solution code:
def cal():
    from collections import deque
    import sys
    input=sys.stdin.readline
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    q = deque()
    counts = [[True for _ in range(w+2)]]+[[True]+[False for _ in range(w)]+[True] for _ in range(h)]+[[True for _ in range(w+2)]]
    loc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for i in range(w):
        for j in range(h):
            if a[j][i] == '#':
                q.append([i, j, 0])
                counts[j+1][i+1] = True

    while q:
        x, y, z = q.popleft()
        for i, j in loc:
            x0 = x+j
            y0 = y+i
            if not counts[y0+1][x0+1]:
                counts[y0+1][x0+1] = True
                q.append([x0, y0, z+1])
    print(z)

print(cal())

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    h,w = map(int,input().split())
    S = [[] for i in range(h)]
    q = deque()
    cnt = 0
    for i in range(h):
        s = input()
        for j in range(w):
            S[i].append(s[j])
            if s[j]=='#':
                q.append([i,j])
                cnt += 1
    ans = 0
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt<h*w:
        ans += 1
        n = len(q)
        for _ in range(n):
            b = q.pop()
            for nx in nxt:
                mv = [b[0]+nx[0],b[1]+nx[1]]
                if -1<mv[0]<h and -1<mv[1]<w:
                    if S[mv[0]][mv[1]]=='#':
                        continue
                    cnt += 1
                    S[mv[0]][mv[1]]='#'
                    q.append(mv)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import collections
import math
import copy

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

A=[list(str(input())) for i in range(H)]
#1<=sy<=R
d=[[-1 for j in range(W)]for i in range(H)]
inf=10**6
ans=0
queue=collections.deque()
for i in range(H):
    for j in range(W):
        if A[i][j]=='#':
            queue.append([i,j])
            d[i][j]=0

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

nax=0
while len(queue)>0:
    now=queue.popleft()
    for i in range(4):
        ny=now[0]+moves[i][0]
        nx=now[1]+moves[i][1]
        if 0<=ny and ny<H and 0<=nx and nx<W and d[ny][nx]==-1:
            d[ny][nx]=d[now[0]][now[1]]+1
            queue.append([ny,nx])


print(nax)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
L = ["#" + input() + "#" for i in range(h)]
L = ["#"*(w+2)] + L + ["#"*(w+2)]
d = [["#"]+[0]*w + ["#"] for i in range(h)]
d = [["#"]*(w+2)] + d + [["#"]*(w+2)]
print(L,d)
li =((1,0),(0,1),(-1,0),(0,-1))

cnt = 0
while True:#not all(d[j][i] == "#" for j in range(1,h+1) for i in range(1,w+1)):
    for p in range(1,h):
        for q in range(1,w):
            if L[p][q] == "#":
                #print(p,q)
                d[p][q] = "#"
                #print(d)
                for x,y in li:
                    if L[p+x][q+y] == ".":
                        d[p+x][q+y] = "#"
    cnt +=1
    flag = False
    for j in range(1,h):
        for i in range(1,w):
            if d[j][i] == "#":
                flag = True
            else:
                flag = False
                break
    if flag == True:
        break
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

cnt = [[10 ** 10] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            cnt[i][j] = 0
def bfs(q, v, c):
    while q:
        y, x = q.pop()
        for i, j in ([0, 1], [1, 0], [-1, 0], [0, -1]):
            ny = y + i
            nx = x + j
            if 0 <= nx < w and 0 <= ny < h and v[ny][nx] == 0:
                v[ny][nx] = 1
                if c[ny][nx] >= c[y][x] + 1:
                    c[ny][nx] = c[y][x] + 1
                    q.append([ny, nx])





for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            queue = deque()
            queue.append([i, j])
            visited = [[0] * w for _ in range(h)]
            bfs(queue, visited, cnt)
            """
            for k in range(h):
                print(cnt[k])
            print()
            """
ans = 0
for i in range(h):
    ans = max(ans, max(cnt[i]))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

ds = [[-1,0],[1,0],[0,-1],[0,1]]
q = deque([])

cnt = 0

for i in range(H):
  for j in range(W):
    if mp[i][j] == '#':
      q.append((i,j,0))
      cnt += 1
      
while q:
  t = q.popleft()
  for d in ds:
    ny = t[0]+d[0]
    nx = t[1]+d[1]
    if 0 <= ny < H and 0<= nx < W:
      if mp[ny][nx] == '.':
        mp[ny][nx] = '#'
        q.append((ny,nx,t[2]+1))
        cnt += 1
        if cnt == H*W:
          print(t[2]+1)
          exit()

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [-1] * (w * h)
    que, frag = deque(), set()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i * w + j] = 0
                que.append((i, j)), frag.add((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if (i, j) in frag:  # 処理済みか否か
                continue
            if 0 <= i < h and 0 <= j < w:
                dist[i * w + j] = dist[x * w + j] + 1
                que.append((i, j)), frag.add((i, j))
    return max(dist)


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

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
d=[0]*H
black=0
ans=0
for s in range(H):
  d[s]=list(str(input()))
  black+=d[s].count('#')
dx=[1,0,-1,0]
dy=[0,1,0,-1]
def bfs(n):
  global black
  for i in range(H):
    for j in range(W):
      if d[i][j]==n:
        for k in range(4):
          y= i + dy[k]
          x= j + dx[k]
          if 0<=y<H and 0<=x<W and d[y][x] == '.':
            d[y][x] = n+1
            black+=1

for i in range(H):
    for j in range(W):
      if d[i][j]=='#':
        for k in range(4):
          y = i + dy[k]
          x = j + dx[k]
          if 0<=y<H and 0<=x<W and d[y][x] == '.':
            d[y][x] = 0
            black+=1        
m=H*W
i=0
while m!=black:
  bfs(i)
  ans+=1
  i+=1
print(ans+1)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
d=[0]*H
black=0
ans=0
for s in range(H):
  d[s]=list(str(input()))
  black+=d[s].count('#')
dx=[1,0,-1,0]
dy=[0,1,0,-1]
def bfs(n):
  global black
  for i in range(H):
    for j in range(W):
      if d[i][j]==n:
        for k in range(4):
          y= i + dy[k]
          x= j + dx[k]
          if 0<=y<H and 0<=x<W and d[y][x] == '.':
            d[y][x] = n+1
            black+=1

for i in range(H):
    for j in range(W):
      if d[i][j]=='#':
        for k in range(4):
          y = i + dy[k]
          x = j + dx[k]
          if 0<=y<H and 0<=x<W and d[y][x] == '.':
            d[y][x] = 0
            black+=1        
m=H*W
i=0
while m!=black:
  bfs(i)
  ans+=1
  i+=1
print(ans+1)

Submission status: Wrong Answer

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

from collections import deque

seen = [[float("inf")] * w for _ in range(h)]
que = deque([])
direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]

for i in range(w):
    for j in range(h):
        if town[j][i] == "#":
            seen[j][i] = 0
            x = i
            y = j
            que.append((x, y))
while que:
    if not "inf" in seen:
        break
    p, q = que.popleft()
    for dx, dy in direction:
            nx = p + dx
            ny = q + dy
            if 0 <= nx < w and 0 <= ny < h and town[ny][nx] != "#" and seen[ny][nx] == float("inf"):
                que.append((nx, ny))
                seen[ny][nx] = seen[q][p] + 1

ans = max(list(map(lambda x: max(x), seen)))
print(ans)

Submission status: Wrong Answer

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

def get_start_idx(area):
    start_idx = []
    for h in range(H):
        for w in range(W):
            if area[h][w] == "#":
                start_idx.append([h, w])
    return start_idx

que = get_start_idx(area)
memo = [[-1 for _ in range(W)] for _ in range(H)]
patterns = [[0, -1], [0, 1], [1, 0], [-1, 0]]

for idx in que:
    memo[idx[0]][idx[1]] = 0
    
while len(que) != 0:
    idx = que.pop(0)
    for p in patterns:
        if 0 <= idx[0]+p[0] < H and 0 <= idx[1]+p[1] < W:
            if memo[idx[0]+p[0]][idx[1]+p[1]] == -1:
                memo[idx[0]+p[0]][idx[1]+p[1]] = memo[idx[0]][idx[1]]+1
                que.append([idx[0]+p[0], idx[1]+p[1]])
    
print(max(max(memo)))

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
a = [input() for i in range(h)]

cnt = [[-1]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            cnt[i][j] = 0

ans = 0
f = True
while f and ans<5:
    f = False
    for i in range(h):
        for j in range(w):
            if cnt[i][j] != ans:
                if cnt[i][j]==-1 or cnt[i][j]>ans:
                    f = True
                continue
            for k,l in [[-1,0],[1,0],[0,-1],[0,1]]:
                if 0<=i+k<h and 0<=j+l<w and cnt[i+k][j+l]==-1:
                    cnt[i+k][j+l] = ans+1
    if f:ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
a = [input() for i in range(h)]

cnt = [[-1]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            cnt[i][j] = 0

ans = 0
f = True
while f and ans<5:
    f = False
    for i in range(h):
        for j in range(w):
            if cnt[i][j]==-1 or cnt[i][j]==ans+1:
                f = True
                continue
            elif cnt[i][j]!=ans:
                continue
            for k,l in [[-1,0],[1,0],[0,-1],[0,1]]:
                if 0<=i+k<h and 0<=j+l<w and cnt[i+k][j+l]==-1:
                    cnt[i+k][j+l] = ans+1
    if f:ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = 1 << 60

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

dist = [[INF if a[i][j] == "." else 0 for j in range(w)] for i in range(h)]
queue = deque([])
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            queue.append((i, j, 0))

while queue:
    y, x, cnt = queue.popleft()
    if not (0 <= y < h and 0 <= x < w):
        continue
    if cnt > 0 and dist[y][x] <= cnt:
        continue
    dist[y][x] = cnt
    for i in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        queue.append((x + i[0], y + i[1], cnt + 1))

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

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
masu = [list(input()) for _ in range(H)]
from collections import deque
def bfs():
    que = deque()
    seen = [[0]*(W+2)] + [[0] + [-1]*(W)+[0]  for _ in range(H)] +[[0]*(W+2)] 
    for w in range(W):
        for h in range(H):
            if masu[h][w] == '#':
                que.append((w,h))
                seen[h+1][w+1] =0
    while que:
        a,b = que.popleft()
        for x,y in [[0,1],[1,0],[0,-1],[-1,0]]:
            nx = a+x
            ny = b+y
            if seen[ny+1][nx+1] == -1:
                seen[ny+1][nx+1] = seen[b+1][a+1]+1
                que.append((nx,ny))
    ans = 0
    for l in seen:print(*l)
    for i in range(H+2):
        for j in range(W+2):
            if seen[i][j] > ans:
                ans = seen[i][j]
    return ans
print(bfs())

Submission status: Wrong Answer

Solution code:
from collections import deque

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

q=deque()

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

ans=0
while len(q)>0:
    i,j,cnt=deque.pop(q)

    ans=max(ans,cnt)

    a[i][j]='#'

    for di,dj in [(-1,0),(1,0),(0,-1),(0,1)]:
        ni=i+di
        nj=j+dj
        if 0<=ni<h and 0<=nj<w and a[ni][nj]=='.':
            deque.appendleft(q,(ni,nj,cnt+1))

print(ans)

Submission status: Wrong Answer

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

import numpy as np

H, W = map(int, input().strip().split())
words = [input() for i in range(H)]
a = [[] for _ in range(H)]
for i in range(H):
    for j in range(W):
        a[i].append(words[i][j])

que_x = list()
que_y = list()

for i in range(H):
    for j in range(W):
        if a[i][j] == '.':
            que_x.append(i)
            que_y.append(j)

def check():
    que_x = list()
    que_y = list()
    for i in range(H):
        for j in range(W):
            if a[i][j] == '.':
                que_x.append(i)
                que_y.append(j)
    if que_x == []:
        return True
    else:
        return False


res = 0
while not check():
    print(a)
    print()
    prev_a = [a[i].copy() for i in range(H)]
    res += 1
    que_pop = list()
    for x, y in zip(que_x, que_y):
        if prev_a[x][y] == '#':
            continue
        if x > 0 and prev_a[x-1][y] == '#':
            a[x][y] = '#'
            continue
        if x < H-1 and prev_a[x+1][y] == '#':
            a[x][y] = '#'
            continue
        if y > 0 and prev_a[x][y-1] == '#':
            a[x][y] = '#'
            continue
        if y < W-1 and prev_a[x][y+1] == '#':
            a[x][y] = '#'
            continue

    print(a)
    print()
print(int(res))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

l = []
dist = [[-1] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            l.append(deque([[i, j]]))
            dist[i][j] = 0

dy = [-1, 0, 1, 0]
dx = [0, -1, 0, 1]
while True:
    flag = False
    for d in l:
        if not d:
            continue

        flag = True
        x1, y1 = d.popleft()

        for i in range(4):
            x2 = x1 + dx[i]
            y2 = y1 + dy[i]

            if 0 <= x2 < h and 0 <= y2 < w and dist[x2][y2] == -1:
                d.append([x2, y2])
                dist[x2][y2] = dist[x1][y1] + 1
    
    if not flag:
        break

print(max(list(map(lambda x: max(x), dist))))

Submission status: Wrong Answer

Solution code:
import copy

h,w = map(int,input().split())
a = [input() for _ in range(h)]
#b = [[False]*w for _ in range(h)]
c = []
d = [(-1,0), (1,0), (0,-1), (0,1)]
ans = 0

"""
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            b[i][j] = True
            c.append((i,j))
"""

while True:
    tmp = []
    cnt = 0
    for i,j in c:
        for d1,d2 in d:
            if 0 <= i + d1 < h and 0 <= j + d2 < w:
                #if not b[i+d1][j+d2]:
                if a[i+d1][j+d2] == '.':
                    tmp.append((i+d1, j+d2))
                    #b[i+d1][j+d2] = True
                    a[i+d1][j+d2] = '#'
                    cnt += 1
    if cnt > 0:
        c = copy.deepcopy(tmp)
        ans += 1
    else:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
def conv(S,index,c):
	lstS = list(S)
	lstS[index] = c
	S = ''.join(lstS)

	return S


def DFS(stack,MAP,size,count):
	if len(stack) == 0:
		return count
	else:
		newstack = []
		for p in stack:
			y = p[0]
			x = p[1]
			Y = size[0]
			X = size[1]
			if y != 0:
				if MAP[y-1][x] == '.':
					MAP[y-1] = conv(MAP[y-1],x,'#')
					newstack.append([y-1,x])
			if y != Y-1:
				if MAP[y+1][x] == '.':
					MAP[y+1] = conv(MAP[y+1],x,'#')
					newstack.append([y+1,x])
			if x != 0:
				if MAP[y][x-1] == '.':
					MAP[y] = conv(MAP[y],x-1,'#')
					newstack.append([y,x-1])
			if x != X-1:
				if MAP[y][x+1] == '.':
					MAP[y] = conv(MAP[y],x+1,'#')
					newstack.append([y,x+1])

		return DFS(newstack,MAP,size,count+1)


if __name__ == '__main__':
	H, W = map(int, input().split())

	MAP = []
	stack = []

	for y in range(H):
		IN = input() 
		MAP.append(IN)

	for y in range(H):
		for x in range(W):
			c = 0
			if MAP[y][x] == '#':
				if y != 0:
					if MAP[y-1][x] == '.':
						c = 1
				if y != H-1:
					if MAP[y+1][x] == '.':
						c = 1
				if x != 0:
					if MAP[y][x-1] == '.':
						c = 1
				if x != W-1:
					if MAP[y][x+1] == '.':
						c = 1

				if c == 1:
					stack.append([y,x])

	step = DFS(stack,MAP,[H,W],0)

	print(step-1)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
from collections import deque
st=deque()
a=[]
b=[[0 for _ in range(w)] for _ in range(h)]
c=0

for i in range(h):
  a.append(input())
  for j in range(w):
    if a[i][j]=="#":
      st.append([i,j,1])
      b[i][j]=1

def dfs(x,y,i):
  d=[[0,1],[0,-1],[1,0],[-1,0]]
  for m in d:
    nx=x+m[0]
    ny=y+m[1]
    if (0<=nx<=w-1) and (0<=ny<=h-1) and b[ny][nx]==0:
      b[ny][nx]=1
      st.append([ny,nx,i+1])

while st:
  y,x,c=st.popleft()
  dfs(y,x,c)
print(c-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(4100000)
def main():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    Q = deque([])
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                Q.append((h,w))
    visited = [[0] * W for _ in range(H)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    ans = 0
    while Q:
        y, x = Q.popleft()
        now = visited[y][x]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if not(0 <= nx < W and 0 <= ny < H):
                continue
            if not visited[ny][nx]:
                visited[ny][nx] = now + 1
                Q.append((ny,nx))
                ans = max(ans, now+1)

    print(ans)




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(): #幅優先探索
  #入力のグラフを初期化
  #d = [[float("inf")] * w for i in range(h)] 
  #d == mazeリストの"."を"inf"に変えたリスト
  dx = [-1,0,0,1]
  dy = [0,-1,1,0]
  
  #que = deque([])
  #que.append((sx,sy))
  #d[sx][sy] = 0
  
  while que:
    lead_h,lead_w = que.popleft()
    lead = d[lead_h][lead_w]
    #lead == queの先頭にある要素を取り出す
    for i in range(4):
      nx = lead_w + dx[i]
      ny = lead_h + dy[i]
      
      if 0<=nx<h and 0<=ny<w and maze[nx][ny]!="#" and d[nx][ny]==float("inf"):
        que.append((nx,ny))
        d[nx][ny] = lead + 1
  return lead

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([])
for i in range(h):
  for j in range(w):
    if maze[i][j] == "#":
      que.append((i,j)) #各"#"をスタートに組み込む
      d[i][j] = 0

print(bfs())

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(): #幅優先探索
  #入力のグラフを初期化
  #d = [[float("inf")] * w for i in range(h)] 
  #d == mazeリストの"."を"inf"に変えたリスト
  dx = [-1,0,0,1]
  dy = [0,-1,1,0]
  
  #que = deque([])
  #que.append((sx,sy))
  #d[sx][sy] = 0
  
  while que:
    lead_h,lead_w = que.popleft()
    lead = d[lead_h][lead_w]
    #lead == queの先頭にある要素を取り出す
    for i in range(4):
      nx = lead_w + dx[i]
      ny = lead_h + dy[i]
      
      if 0<=nx<h and 0<=ny<w and maze[nx][ny]!="#" and d[nx][ny]==float("inf"):
        que.append((nx,ny))
        d[nx][ny] = lead + 1
  return lead

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([])
for i in range(h):
  for j in range(w):
    if maze[i][j] == "#":
      sx = i
      sy = j
      que.append((sx,sy))
      d[i][j] = 0

print(bfs())

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(): #幅優先探索
  #入力のグラフを初期化
  #d = [[float("inf")] * w for i in range(h)] 
  #d == mazeリストの"."を"inf"に変えたリスト
  dx = [-1,0,0,1]
  dy = [0,-1,1,0]
  
  #que = deque([])
  #que.append((sx,sy))
  #d[sx][sy] = 0
  
  while que:
    lead = que.popleft()
    #lead == queの先頭にある要素を取り出す
    for i in range(4):
      nx = lead[0] + dx[i]
      ny = lead[1] + dy[i]
      
      if 0<=nx<h and 0<=ny<w and maze[nx][ny]!="#" and d[nx][ny]==float("inf"):
        que.append((nx,ny))
        d[nx][ny] = d[lead[0]][lead[1]] + 1
  return lead[0]

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([])
for i in range(h):
  for j in range(w):
    if maze[i][j] == "#":
      sx = i
      sy = j
      que.append((sx,sy))
      d[i][j] = 0

print(bfs())

Submission status: Wrong Answer

Solution code:
import numpy as np
import pprint
h,w=map(int, input().split())
a=[list(input()) for i in range(h)]


#スタートをキューに格納

route=[[1,0],[0,1],[-1,0],[0,-1]]
cnt=0

q=[]
for i in range(h):
  for j in range(w):
    if a[i][j]=="#":
      q.append([i,j])
qDummy=q
for _ in range(h*w):
  q=qDummy
  while q:
    #print(len(q))
    qDummy=[]
    for _ in range(len(q)):
      x,y = q.pop(0)

      for i in range(4):
        nx, ny = x+route[i][0], y+route[i][1]
        #条件に合致すれば追加
        if 0<=nx<h and 0<=ny<w:
          a[nx][ny]="#"
          qDummy.append([nx,ny])
          #print("nx,ny", nx,ny)
  cnt+=1
  #pprint.pprint(a)
  if np.sum(np.array(a)=="#")==h*w:
    print(cnt)
    exit()

Submission status: Wrong Answer

Solution code:
import numpy as np
h,w=map(int, input().split())
a=[list(input()) for i in range(h)]


#スタートをキューに格納

route=[[1,0],[0,1],[-1,0],[0,-1]]
cnt=0

for _ in range(h*w):
  q=[]
  for i in range(h):
    for j in range(w):
      if a[i][j]=="#":
        q.append([i,j])
                
  while q:
    #print(len(q))
    for _ in range(len(q)):
      x,y = q.pop(0)

      for i in range(4):
        nx, ny = x+route[i][0], y+route[i][1]
        #条件に合致すれば追加
        if 0<=nx<h and 0<=ny<w and a[nx][ny] != '#':
          a[nx][ny]="#"
          #print("nx,ny", nx,ny)
  cnt+=1
  #print(a)
  if np.sum(np.array(a)=="#")==h*w:
    print(cnt)
    exit()

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(): #幅優先探索
  #入力のグラフを初期化
  #d = [[float("inf")] * w for i in range(h)] 
  
  dx = [-1,0,0,1]
  dy = [0,-1,1,0]
  
  #que = deque([])
  #que.append((sx,sy))
  #d[sx][sy] = 0
  
  while que:
    lead = que.popleft()
    #lead == queの先頭にある要素を取り出す
    for i in range(4):
      nx = lead[0] + dx[i]
      ny = lead[1] + dy[i]
      
      if 0<=nx<h and 0<=ny<w and maze[nx][ny]!="#" and d[nx][ny]==float("inf"):
        que.append((nx,ny))
        d[nx][ny] = d[lead[0]][lead[1]] + 1
  return lead[0]

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

#多点スタートなので毎回毎回初期化(スタート地点を0に)せずに最初から
#すべての"#"を0にしておく
d = [[float("inf")] * w for i in range(h)] 
#d == mazeリストの要素を全て"inf"に変えたリスト

que = deque([])
for i in range(h):
  for j in range(w):
    if maze[i][j] == "#":
      sx = i
      sy = j
      que.append((sx,sy))
      d[i][j] = 0
      #dリスト内の"#"にあたる位置にある"inf"がすべて"0"になる

print(bfs())

Submission status: Wrong Answer

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] == "#":
            black.append((i, j))

while black:
    x, y = black.popleft()
    visited[x][y] = True
    for dx, dy in dif:
        if 0 <= dx+x < H and 0 <= dy+y < W and visited[dx+x][dy+y] == False:
            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: Wrong Answer

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] == '#'])

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

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

print(depth)