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:
from collections import deque

h,w=map(int,input().split())
a=[input() for i in range(h)]
lis=[[-1 for i in range(w)] for j in range(h)]
q=deque()


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

while q:
  cur=q.popleft()

  if 0<=cur[0]+1<=h-1 and 0<=cur[1]<=w-1:
    if lis[cur[0]+1][cur[1]]==-1:
      lis[cur[0]+1][cur[1]]=lis[cur[0]][cur[1]]+1
      q.append((cur[0]+1,cur[1]))
  
  if 0<=cur[0]-1<=h-1 and 0<=cur[1]<=w-1:
    if lis[cur[0]-1][cur[1]]==-1:
      lis[cur[0]-1][cur[1]]=lis[cur[0]][cur[1]]+1
      q.append((cur[0]-1,cur[1]))

  
  if 0<=cur[0]<=h-1 and 0<=cur[1]+1<=w-1:
    if lis[cur[0]][cur[1]+1]==-1:
      lis[cur[0]][cur[1]+1]=lis[cur[0]][cur[1]]+1
      q.append((cur[0],cur[1]+1))
      
  if 0<=cur[0]<=h-1 and 0<=cur[1]-1<=w-1:
    if lis[cur[0]][cur[1]-1]==-1:
      lis[cur[0]][cur[1]-1]=lis[cur[0]][cur[1]]+1
      q.append((cur[0],cur[1]-1))      
  
print(max(max(l) for l in lis))

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int,input().split())
graph = []
finished = [[False for _ in range(w)] for _ in range(h)]
y = [0, 0, 1,-1]
x = [1,-1, 0, 0]
q = deque([])
for i in range(h):
    a = input()
    graph.append(a)
    for j in range(w):
        if a[j] == "#":
            q.append((i,j,0))
while q:
    c = q.popleft()
    for i in range(4):
        nh = c[0]+y[i]
        nw = c[1]+x[i]
        if nh < 0 or nh >= h or nw < 0 or nw >= w or finished[nh][nw]:continue
        finished[nh][nw] = True
        q.append((nh,nw,c[2]+1))
print(c[2])

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
a=[list(input()) for _ in range(h)]
field=[[float('inf') for i in range(w)] for j in range(h)]

q=deque()

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

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

while q:
    y,x=q.popleft()    
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if 0<=ny<h and 0<=nx<w and field[ny][nx]==float('inf'):
            field[ny][nx]=field[y][x]+1
            q.append((ny,nx))

ans=max(max(i for i in field))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
h, w = map(int, sys.stdin.readline().split())

a = [[False]*(w+2)]
for y in range(h):
    a.append([False] + [x!='#' for x in sys.stdin.readline()] + [False])
a.append([False]*(w+2))

s = deque()
for i in range(1, h+1):
    for j in range(1, w+1):
        if not a[i][j]:
            s.append((i,j))

ans = -1
while s:
    ns = deque()
    for i, j in s:
        if a[i-1][j]:
            a[i-1][j] = False
            ns.append((i-1, j))
        if a[i+1][j]:
            a[i+1][j] = False
            ns.append((i+1, j))
        if a[i][j-1]:
            a[i][j-1] = False
            ns.append((i, j-1))
        if a[i][j+1]:
            a[i][j+1] = False
            ns.append((i, j+1))
        
    s = ns
    ans += 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
_in = list(open(0))
h, w = list(map(int, _in[0].split()))

s = []
for i in range(h):
    for j in range(w):
        if _in[1+i][j]=='#':
            s.append((i,j))

a = [[True]*w + [False] for _ in range(h)]
a.append([False]*(w+1))

ans = 0

print(ans)

Submission status: Wrong Answer

Solution code:
_in = list(open(0))
h, w = list(map(int, _in[0].split()))

s = []
for i, y in enumerate(_in[1:]):
    for j, x in enumerate(y):
        if x == '#':
            s.append((i,j))

a = [[True]*w + [False] for _ in range(h)]
a.append([False]*(w+1))

ans = 0

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
_in = list(open(0))
h, w = list(map(int, _in[0].split()))

s = deque()
for i, y in enumerate(_in[1:]):
    for j, x in enumerate(y):
        if x == '#':
            s.append((i,j))

a = [[False]*w for _ in range(h)]

ans = -1
while s:
    ns = deque()
    for i, j in s:
        if a[i][j]:
            continue

        a[i][j] = True

        if i>0:
            ns.append((i-1, j))
        if i<h-1:
            ns.append((i+1, j))
        if j>0:
            ns.append((i, j-1))
        if j<w-1:
            ns.append((i, j+1))
        
    s = ns
    ans += 1
    
print(ans-1)

Submission status: Wrong Answer

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

# スタック最大数をセット
sys.setrecursionlimit(10**6)

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

queue = collections.deque()

ans = 0


def bfs(y, x, cnt):
    if (y < 0 or h <= y or x < 0 or w <= x or a[y][x] == '#'):
        return
    #print(y, x, cnt)
    a[y][x] = '#'
    queue.append([y + 1, x, cnt+1])
    queue.append([y - 1, x, cnt+1])
    queue.append([y, x+1, cnt+1])
    queue.append([y, x - 1, cnt+1])


for i in range(h):
    for j in range(w):
        if (a[i][j] == '#'):
            queue.append([i+1, j, 0])
            queue.append([i-1, j, 0])
            queue.append([i, j+1, 0])
            queue.append([i, j - 1, 0])
            break

while (len(queue) > 0):
    l = queue.popleft()
    # print(l)
    ans = max(ans, l[2])
    bfs(l[0], l[1], l[2])

print(ans)

Submission status: Wrong Answer

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

queue = collections.deque()

ans = 0


def bfs(y, x, cnt):
    if (y < 0 or h <= y or x < 0 or w <= x or a[y][x] == '#'):
        return
    #print(y, x, cnt)
    a[y][x] = '#'
    queue.append([y + 1, x, cnt+1])
    queue.append([y - 1, x, cnt+1])
    queue.append([y, x+1, cnt+1])
    queue.append([y, x - 1, cnt+1])


for i in range(h):
    for j in range(w):
        if (a[i][j] == '#'):
            queue.append([i+1, j, 0])
            queue.append([i-1, j, 0])
            queue.append([i, j+1, 0])
            queue.append([i, j - 1, 0])
            break

while (len(queue) > 0):
    l = queue.popleft()
    # print(l)
    ans = max(ans, l[2])
    bfs(l[0], l[1], l[2])

print(ans)

Submission status: Wrong Answer

Solution code:
import sys


#input
lines = [x.strip() for x in sys.stdin.readlines()]
h,w=[int(x) for x in lines[0].split()]
map=[[x for x in y] for y in lines[1:]]
memo=[[-1 for x in y] for y in lines[1:]]
#print(h,w)

def slv(lines):
    q=[]
    for x in range(w):
        for y in range(h):
            if map[y][x]=="#":
                q.append([x,y])
                continue
                for d in [1,-1]:
                    if w>x+d>=0 and map[y][x+d]=="#" and [x+d,y] not in q:
                        q.append([x+d,y])
                    elif h>y+d>=0 and map[y+d][x]=="#" and [x,y+d] not in q:
                        q.append([x,y+d])
    #print("pi")
    ans=0
    ct=0
    while q!=[]:
        ans+=1
        qn=len(q)
        for n in range(qn):
            x,y=q.pop(0)
            
            #ct+=1
            for d in [1,-1]:
                
                if w>x+d>=0 and map[y][x+d]==".":
                    q.append([x+d,y])
                    map[y][x+d]="#"
                if h>y+d>=0 and map[y+d][x]==".":
                    q.append([x,y+d])
                    map[y+d][x]="#"

    #print(ct)
    return ans

if __name__ == "__main__":
    print(slv(lines))

Submission status: Wrong Answer

Solution code:
import sys


#input
lines = [x.strip() for x in sys.stdin.readlines()]
h,w=[int(x) for x in lines[0].split()]
map=[[x for x in y] for y in lines[1:]]
memo=[[-1 for x in y] for y in lines[1:]]
#print(h,w)

def slv(lines):
    q=[]
    for x in range(w):
        for y in range(h):
            if map[y][x]=="#":
                iswht=False
                memo[y][x]=0
                for d in [1,-1]:
                    if w>x+d>=0 and map[y][x+d]=="." or h>y+d>=0 and map[y+d][x]==".":
                        iswht=True
                if iswht:
                    q.append([x,y])
    #print(blk,blk_d)
    ans=0
    while q!=[]:
        ans+=1
        for n in q:
            x,y=q.pop()
            for d in [1,-1]:
                if w>x+d>=0 and map[y][x+d]==".":
                    q.append([x+d,y])
                    map[y][x+d]="#"
                if h>y+d>=0 and map[y+d][x]==".":
                    q.append([x,y+d])
                    map[y+d][x]="#"

    return ans

if __name__ == "__main__":
    print(slv(lines))

Submission status: Wrong Answer

Solution code:
import sys


#input
lines = [x.strip() for x in sys.stdin.readlines()]
h,w=[int(x) for x in lines[0].split()]
map=[[x for x in y] for y in lines[1:]]
memo=[[-1 for x in y] for y in lines[1:]]
#print(h,w)

def slv(lines):
    q=[]
    blk=0
    blk_d=0
    for x in range(w):
        for y in range(h):
            if map[y][x]=="#":
                iswht=False
                blk+=1
                memo[y][x]=0
                for d in [1,-1]:
                    if w>x+d>=0 and map[y][x+d]=="." or h>y+d>=0 and map[y+d][x]==".":
                        iswht=True
                if iswht:
                    blk_d+=1
                    q.append([x,y])
    #print(blk,blk_d)
    ans=0
    while q!=[]:
        x,y=q.pop()
        for d in [1,-1]:
            if w>x+d>=0 and map[y][x+d]=="." and memo[y][x+d]<0:
                q.append([x+d,y])
                memo[y][x+d]=memo[y][x]+1
            if h>y+d>=0 and map[y+d][x]=="." and memo[y+d][x]<0:
                q.append([x,y+d])
                memo[y+d][x]=memo[y][x]+1
            else:
                continue
            ans=max([ans,memo[y][x]+1])

    return ans

if __name__ == "__main__":
    print(slv(lines))

Submission status: Wrong Answer

Solution code:
import sys


#input
lines = [x.strip() for x in sys.stdin.readlines()]
h,w=[int(x) for x in lines[0].split()]
map=[[x for x in y] for y in lines[1:]]
memo=[[-1 for x in y] for y in lines[1:]]
print(h,w)

def slv(lines):
    q=[]
    blk=0
    for x in range(w):
        for y in range(h):
            if map[y][x]=="#":
                for d in [1,-1]:
                    if w>x+d>=0 and map[y][x+d]=="." or h>y+d>=0 and map[y+d][x]==".":
                        pass
                    else:
                        continue
                blk+=1
                memo[y][x]=0
                q.append([x,y])
    #print(blk)
    ans=0
    while q!=[]:
        x,y=q.pop(0)
        for d in [1,-1]:
            if w>x+d>=0 and map[y][x+d]=="." and memo[y][x+d]<0:
                q.append([x+d,y])
                memo[y][x+d]=memo[y][x]+1
            if h>y+d>=0 and map[y+d][x]=="." and memo[y+d][x]<0:
                q.append([x,y+d])
                memo[y+d][x]=memo[y][x]+1
            else:
                continue
            ans=max([ans,memo[y][x]+1])

    return ans

if __name__ == "__main__":
    print(slv(lines))

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]
INF = 10**5
checked = [[INF] * (W) for _ in range(H)]
dy = [1,0,-1,0]
dx = [0,1,0,-1]
ans = 0
for i in range(H):
  for j in range(W):
    if grid[i][j] == '.' and checked[i][j] == INF:
      que = deque([])
      checked[i][j] = 0
      update = True
      for k in range(4):
        ny,nx = i+dy[k], j+dx[k]
        if 0 <= ny < H and 0 <= nx < W:
          if grid[ny][nx] == '#':
            ans = max(ans, 1)
            update = False
            break
          elif checked[ny][nx] != INF:
            continue
          else:
            checked[ny][nx] = 1
            que.append((ny, nx))
      while len(que) > 0 and update:
        cy, cx = que.popleft()
        for k in range(4):
          ny,nx = cy+dy[k], cx+dx[k]
          if 0 <= ny < H and 0 <= nx < W:
            if grid[ny][nx] == '#':
              ans = max(ans, checked[cy][cx]+1)
              update = False
              break
            elif checked[ny][nx] != INF:
              continue
            else:
              checked[ny][nx] = checked[cy][cx] + 1
              que.append((ny, nx))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *
import numpy as np

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    H,W = map(int, input().split())
    grid = [list(input().rstrip()) for _ in range(H)]
    q = deque()
    visited = [[False]*W for _ in range(H)]
    black_cnt = 0
    for y in range(H):
        for x in range(W):
            if grid[y][x] == '#':
                q.append((y,x,0))
                visited[y][x] = True
                black_cnt += 1
    while q:
        y,x,step = q.popleft()
        for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
            ny = y+dy
            nx = x+dx
            if 0<=ny<H and 0<=nx<W and not visited[ny][nx] and grid[ny][nx] == '.':
                q.append((ny,nx,step+1))
                visited[ny][nx] = True
                black_cnt += 1
                if black_cnt == W*H:
                    print(step+1)
                    return 0

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *
import numpy as np

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    H,W = map(int, input().split())
    grid = [list(input().rstrip()) for _ in range(H)]
    q = deque()
    visited = [[False]*W for _ in range(H)]
    black_cnt = 0
    for y in range(H):
        for x in range(W):
            if grid[y][x] == '#':
                q.append((y,x,0))
                visited[y][x] = True
                black_cnt += 1
    while q:
        y,x,step = q.popleft()
        for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
            ny = y+dy
            nx = x+dx
            if 0<=ny<H and 0<=nx<W and not visited[ny][nx]:
                q.append((ny,nx,step+1))
                visited[ny][nx] = True
                black_cnt += 1
                if black_cnt == W*H:
                    print(step+1)
                    return 0

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
h,w = map(int,input().split())
b = [[i == "#" for i in list(input())]+[True] for _ in range(h)]+[[True]*(w+1)]
check = []
for i in range(h):
  for j in range(w):
    if b[i][j]:
      check.append((i,j))
ans = 0
while check:
  new = []
  k = 0
  for i,j in check:
    if not b[i-1][j]:
      new.append((i-1,j))
      b[i-1][j] = True
      k = 1
    if not b[i+1][j]:
      new.append((i+1,j))
      b[i+1][j] = True
      k = 1
    if not b[i][j-1]:
      new.append((i,j-1))
      b[i][j-1] = True
      k = 1
    if not b[i][j+1]:
      new.append((i,j+1))
      b[i][j+1] = True
      k = 1
  check = new
  if k:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
h,w = map(int,input().split())
b = [[i == "#" for i in list(input())]+[True] for _ in range(h)]+[[True]*(w+1)]
#print(b)
check = []
for i in range(h):
  for j in range(w):
    if b[i][j]:
      check.append((i,j))
ans = 0
while check:
  new = []
  k = 0
  for i,j in check:
    if not b[i-1][j]:
      new.append((i-1,j))
      b[i-1][j] = True
      k = 1
    if not b[i+1][j]:
      new.append((i+1,j))
      b[i+1][j] = True
      k = 1
    if not b[i][j-1]:
      new.append((i,j-1))
      b[i][j-1] = True
      k = 1
    if not b[i][j+1]:
      new.append((i,j+1))
      b[i][j+1] = True
      k = 1
  check = new
  if k:
    ans += 1
  #print(b)
print(ans)

Submission status: Wrong Answer

Solution code:
x=input().split()
a=int(x[0])
b=int(x[1])
x=[]
n=0
for i in range(a):
    y=[p for p in input()]
    x.append(y)
flag=True
while flag:
    s=[]
    ss=[]
    for i in range(a):
        for j in range(b):
            if x[i][j]=='#':
                ss.append(i)
                ss.append(j)
                s.append(ss)
                ss=[]
    for i in s:
        y=i[0]
        z=i[1]
        if y-1>=0:
            x[y-1][z]='#'
        if y+1<a:
            x[y+1][z]='#'
        if z-1>=0:
            x[y][z-1]='#'
        if z+1<b:
            x[y][z+1]='#'
    n+=1
    flag=False
    for i in range(a):
        for j in range(b):
            if x[i][j]=='.':
                flag=True
print(n)

Submission status: Wrong Answer

Solution code:
from collections import deque
import itertools
#入力
h,w = map(int, input().split())
w = w + 2
maze = [list('#' * (w))]
for i in range(h):
    maze.append(list('#' + input() + '#')) #迷路の読み込み
maze.append(list('#' * (w)))
h = h + 2
                
distance = [[100] * w for i in range(h)] #まずは無限大の距離と仮定

start = []

for i in range(1,h-1):
    for j in range(1,w-1):
        if maze[i][j] == '#':
            start.append((i,j,0))

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

for t in range(len(start)):
    que = deque()
    que.append(start[t])
    
    while que:
        i,j,k = que.popleft() #先頭を取得
        for di,dj in move:
            if maze[i+di][j+dj] == '.' and distance[i+di][j+dj] > k+1:
                #迷路の道で，今までの距離が今出した距離より長いなら
                distance[i+di][j+dj] = k+1 #より短い今の距離に更新し
                que.append((i+di,j+dj,k+1)) #queの末尾に追加            

ans = itertools.chain(*distance)
ans = list(ans) #二次元リストを一次元化
for i in range(len(ans)):
    if ans[i] == 100:
        ans[i] = 0 #infを0にする
        
print(max(ans))

Submission status: Wrong Answer

Solution code:

import sys
from collections import deque
from itertools import product
sys.setrecursionlimit(10**9)

H,W=map(int,input().split())
G=[[""]*W for _ in range(H)]
spos=()
black=0

for y in range(H):
    A=input()
    for x in range(W):
        G[y][x]=A[x]
        if A[x]=="#":
            black+=1
            if len(spos)==0:
                spos=(x,y)

# print(black)
def isFilled(todo,index):
    # print(len(todo),H*W-black+1)
    return len(todo)==H*W-black+1 and not index<len(todo)

def bfs(pos):
    todo=[pos]
    index=1
    dx,dy=[-1,1,0,0],[0,0,-1,1]
    depth=[[0]*W for _ in range(H)]
    while True:
        x,y=pos

        # print(G,black)
        if isFilled(todo,index):
            return depth[y][x]

        for i in range(4):
            npos=(x+dx[i],y+dy[i])
            if 0<=npos[0]<W and 0<=npos[1]<H:
                if G[npos[1]][npos[0]]=="." and not npos in todo:
                    depth[npos[1]][npos[0]]=depth[y][x]+1
                    todo.append(npos)

        if index<len(todo):
            pos=todo[index]
            G[pos[1]][pos[0]]="#"
            index+=1


print(bfs(spos)+1-black)

Submission status: Wrong Answer

Solution code:
from collections import deque


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    h, w = read_int(2)
    a = []
    for y in range(h):
        a.append(list(read_line(w)))
    return a


def read_int(n):
    return list(map(int, read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    white_tile = '.'
    black_tile = '#'

    w, h = get_area(a)
    invalid = w * h
    memo = [[invalid for x in range(w)] for y in range(h)]

    queue = deque()
    next_steps = [[1, 0], [-1, 0], [0, 1], [0, -1]]

    maximum_count = 0

    for y in range(h):
        for x in range(w):
            if a[y][x] == black_tile:
                queue.append((x, y, 0))

    while queue:
        x, y, d = queue.popleft()

        memo[y][x] = d
        maximum_count = max(maximum_count, d)

        for dx, dy in next_steps:
            nx, ny = x + dx, y + dy
            if not (0 <= nx < w and 0 <= ny < h):
                continue
            if memo[ny][nx] <= d + 1:
                continue
            if a[ny][nx] == black_tile:
                continue
            queue.append((nx, ny, d + 1))

    return maximum_count


def get_area(a):
    w = len(a[0])
    h = len(a)
    return w, h


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

Map = [[] for _ in range(H)]
reached = [[False] * W for _ in range(H)]
q = deque()
cnt = 0
count = 0
tempList = []
for y in range(H):
    for i, x in enumerate(input()):
        Map[y].append(x)
        if x == "#":
            cnt += 1
            reached[y][i] = True
            if i + 1 < W and not reached[y][i + 1]:
                reached[y][i + 1] = True
                tempList.append((i + 1, y))

            if i > 0 and not reached[y][i - 1]:
                reached[y][i - 1] = True
                tempList.append((i - 1, y))

            if y + 1 < H and not reached[y + 1][i]:
                reached[y + 1][i] = True
                tempList.append((i, y + 1))

            if y > 0 and not reached[y - 1][i]:
                reached[y - 1][i] = True
                tempList.append((i, y - 1))

q.append(tempList)


def BFS(blist):
    global count
    tList = []

    count += 1

    for (x, y) in blist:
        if x+1<W and not reached[y][x + 1]:
            reached[y][x + 1] = True
            tList.append((x + 1, y))

        if x-1>=0 and not reached[y][x - 1]:
            reached[y][x - 1] = True
            tList.append((x - 1, y))

        if y+1<H and not reached[y + 1][x]:
            reached[y + 1][x] = True
            tList.append((x, y + 1))

        if y-1>=0 and not reached[y - 1][x]:
            reached[y - 1][x] = True
            tList.append((x, y - 1))

    if tList:
        q.append(tList)


while q:
    BFS(q.popleft())

print(count)

Submission status: Wrong Answer

Solution code:

from collections import deque

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

Map = [[] for _ in range(H)]
reached = [[False] * W for _ in range(H)]
q = deque()
cnt = 0
count = 0
tempList = []
for y in range(H):
    for i, x in enumerate(input()):
        Map[y].append(x)
        if x == "#":
            cnt += 1
            reached[y][i] = True
            if i + 1 < W and not reached[y][i + 1]:
                reached[y][i + 1] = True
                tempList.append((i + 1, y))

            if i - 1 >= 0 and not reached[y][i - 1]:
                reached[y][i - 1] = True
                tempList.append((i - 1, y))

            if y + 1 < H and not reached[y + 1][i]:
                reached[y + 1][i] = True
                tempList.append((i, y + 1))

            if y - 1 >= 0 and not reached[y - 1][i]:
                reached[y - 1][i] = True
                tempList.append((i, y - 1))

q.append(tempList)


def BFS(blist):
    global count
    tList = []

    count += 1

    for (x, y) in blist:
        if x+1<W and not reached[y][x + 1]:
            reached[y][x + 1] = True
            tList.append((x + 1, y))

        if x-1>=0 and not reached[y][x - 1]:
            reached[y][x - 1] = True
            tList.append((x - 1, y))

        if y+1<H and not reached[y + 1][x]:
            reached[y + 1][x] = True
            tList.append((x, y + 1))

        if y-1>=0 and not reached[y - 1][x]:
            reached[y - 1][x] = True
            tList.append((x, y - 1))

    # if np.array(reached).all():
    #     print(count)
    #     sys.exit()
    if tList:
        q.append(tList)


while q:
    BFS(q.popleft())

print(count)

Submission status: Wrong Answer

Solution code:

from collections import deque
import numpy as np
import sys

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

Map = [[] for _ in range(H)]
reached = [[False] * W for _ in range(H)]
q = deque()
cnt = 0
count = 0
tempList = []
for y in range(H):
    for i, x in enumerate(input()):
        Map[y].append(x)
        if x == "#":
            cnt += 1
            reached[y][i] = True
            if i + 1 < W and not reached[y][i + 1]:
                reached[y][i + 1] = True
                tempList.append((i + 1, y))

            if i - 1 >= 0 and not reached[y][i - 1]:
                reached[y][i - 1] = True
                tempList.append((i - 1, y))

            if y + 1 < H and not reached[y + 1][i]:
                reached[y + 1][i] = True
                tempList.append((i, y + 1))

            if y - 1 >= 0 and not reached[y - 1][i]:
                reached[y - 1][i] = True
                tempList.append((i, y - 1))

q.append(tempList)


def BFS(blist):
    global count
    global cnt
    tList = []

    count += 1

    for (x, y) in blist:
        reached[y][x] = True
        Map[y][x] = "#"

        if x+1<W and not reached[y][x + 1]:
            tList.append((x + 1, y))

        if x-1>=0 and not reached[y][x - 1]:
            tList.append((x - 1, y))

        if y+1<H and not reached[y + 1][x]:
            tList.append((x, y + 1))

        if y-1>=0 and not reached[y - 1][x]:
            tList.append((x, y - 1))

    # if np.array(reached).all():
    #     print(count)
    #     sys.exit()
    if tList:
        q.append(tList)


while q:
    BFS(q.popleft())

print(count)

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
import sys

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

Map = [[] for _ in range(H)]
reached = [[False]*W for _ in range(H)]
q = deque()
cnt = 0
count = 0
tempList = []
for y in range(H):
    for i, x in enumerate(input()):
        Map[y].append(x)
        if x=="#":
            reached[y][i] = True
            if i + 1 < W and not reached[y][i + 1]:
                tempList.append((i + 1, y))

            if i - 1 >= 0 and not reached[y][i - 1]:
                tempList.append((i - 1, y))

            if y + 1 < H and not reached[y + 1][i]:
                tempList.append((i, y + 1))

            if y - 1 >= 0 and not reached[y - 1][i]:
                tempList.append((i, y - 1))

q.append(tempList)

def BFS(blist):
    global count
    tList = []

    count += 1

    for (x, y) in blist:
        reached[y][x] = True
        Map[y][x] = "#"
        if x+1<W and not reached[y][x + 1]:
            tList.append((x + 1, y))

        if x-1>=0 and not reached[y][x - 1]:
            tList.append((x - 1, y))

        if y+1<H and not reached[y + 1][x]:
            tList.append((x, y + 1))

        if y-1>=0 and not reached[y - 1][x]:
            tList.append((x, y - 1))

    if np.array(reached).all():
        print(count)
        sys.exit()

    q.append(tList)

while q:
    BFS(q.popleft())

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
import sys

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

Map = [[] for _ in range(H)]
reached = [[False]*W for _ in range(H)]
q = deque()
cnt = 0
count = 0
tempList = []
for y in range(H):
    for i, x in enumerate(input()):
        Map[y].append(x)
        if x=="#":
            cnt += 1
            reached[y][i] = True
            tempList.append((i + 1,y))
            tempList.append((i - 1, y))
            tempList.append((i, y + 1))
            tempList.append((i, y - 1))

q.append(tempList)

def BFS(blist):
    global count
    global cnt
    tList = []

    count += 1

    for (x, y) in blist:
        if x>=W or y>=H or x<0 or y<0 or reached[y][x]:
            continue

        reached[y][x] = True
        Map[y][x] = "#"
        cnt += 1

        tList.append((x + 1, y))
        tList.append((x - 1, y))
        tList.append((x, y + 1))
        tList.append((x, y - 1))

    if cnt==H*W:
        print(count)
        sys.exit()

    q.append(tList)

while q:
    BFS(q.popleft())

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
import sys

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

Map = [[] for _ in range(H)]
reached = [[False]*W for _ in range(H)]
q = deque()
cnt = 0
count = 0
tempList = []
for y in range(H):
    for i, x in enumerate(input()):
        Map[y].append(x)
        if x=="#":
            reached[y][i] = True
            tempList.append((i + 1,y))
            tempList.append((i - 1, y))
            tempList.append((i, y + 1))
            tempList.append((i, y - 1))

q.append(tempList)

def BFS(blist):
    global count
    tList = []

    count += 1

    for (x, y) in blist:
        if x>=W or y>=H or x<0 or y<0 or reached[y][x]:
            continue

        reached[y][x] = True
        Map[y][x] = "#"

        tList.append((x + 1, y))
        tList.append((x - 1, y))
        tList.append((x, y + 1))
        tList.append((x, y - 1))

    if np.where(np.array(Map)=="#", True, False).all():
        print(count)
        sys.exit()

    q.append(tList)

while q:
    BFS(q.popleft())

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
import sys

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

Map = [[] for _ in range(H)]
reached = [[False]*W for _ in range(H)]
q = deque()
cnt = 0
count = 0
tempList = []
for y in range(H):
    for i, x in enumerate(input()):
        Map[y].append(x)
        if x=="#":
            tempList.append((i,y))
            cnt += 1

q.append(tempList)

def BFS(blist):
    global count
    global cnt
    tList = []

    count += 1

    for (x, y) in blist:
        if x+1<W:
            Map[y][x+1] = "#"
            tList.append((x + 1, y))

        if y+1<H:
            Map[y+1][x] = "#"
            tList.append((x, y + 1))

        if x-1>=0:
            Map[y][x-1] = "#"
            tList.append((x - 1, y))

        if y-1>=0:
            Map[y-1][x] = "#"
            tList.append((x, y - 1))

    if np.where(np.array(Map)=="#", True, False).all():
        print(count)
        sys.exit()

    q.append(tList)

while q:
    BFS(q.popleft())

Submission status: Wrong Answer

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

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

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


# スタート地点をqueueに追加
que = deque([(i,j) for i in range(h) for j in range(w) if a[i][j]])

loop = len(que)
count = 0

add = 0
while len(que):
    count += 1
    loop += add
    add = 0
    for i in range(loop):
        p = que.popleft()
        add -= 1
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and not a[ny][nx]:
                a[ny][nx] = True
                que.append([ny, nx])
                add += 1


print(count)