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 = [int(x) for x in input().split()]
meiro = [list(input()) for _ in range(h)]
ans = [[float("INF")]*w for _ in range(h)]
mina=-1
for i in range(h):
    for j in range(1,w):
        if meiro[i][j]=="#":
            ans[i][j]=0
        else:
            ans[i][j]=min(ans[i][j-1]+1,ans[i][j])
for i in range(h):
    for j in range(w-2,-1,-1):
        if meiro[i][j]=="#":
            ans[i][j]=0
        else:
            ans[i][j]=min(ans[i][j+1]+1,ans[i][j])
for j in range(w):
    for i in range(1,h):
        if meiro[i][j]=="#":
            ans[i][j]=0
        else:
            ans[i][j]=min(ans[i-1][j]+1,ans[i][j])
for j in range(w):
    for i in range(h-2,-1,-1):
        if meiro[i][j]=="#":
            ans[i][j]=0
        else:
            ans[i][j]=min(ans[i+1][j]+1,ans[i][j])
for i in range(h):
    for j in range(w):
        mina = max(mina,ans[i][j])
print(mina)

Submission status: Wrong Answer

Solution code:
import numpy as np
h,w=map(int,input().split())
a=[]
for i in range(h):
  a.append([0 if i=='#' else h+w for i in list(input())])
a=np.array(a)
print(a)
for i in range(h-1):
  a[i+1,:]=np.minimum(a[i,:]+1,a[i+1,:])
for i in range(h-1,0,-1):
  a[i-1,:]=np.minimum(a[i,:]+1,a[i-1,:])
for i in range(w-1):
  a[:,i+1]=np.minimum(a[:,i]+1,a[:,i+1])
for i in range(w-1,0,-1):
  a[:,i-1]=np.minimum(a[:,i]+1,a[:,i-1])
print(np.max(a))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

#上下左右のマスを黒くしていく
#BFS
from collections import deque
def bfs():
    dx=[0,1,0,-1]
    dy=[1,0,-1,0]
    log=[[0]*w for i in range(h)]

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

    while que:
        #queの先頭を取り出す
        p=que.popleft()
        for i in range(4):
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]

            if not(0<=nx<h and 0<=ny<w):continue
            if log[nx][ny]!=0:continue
            que.append((nx,ny))
            a[nx][ny]='#'
            log[nx][ny]=log[p[0]][p[1]]+1

    return log

G=bfs()
ans=0
for i in range(h):
    for j in range(w):
        if ans<G[i][j]:
            ans=G[i][j]
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        a = input()
        A.append(a)
    bl = set()
    wl = set()
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                bl.add((i, j))
            else:
                wl.add((i, j))
    r = 1
    while wl:
        bln = set()
        for i in bl:
            if (i[0] + 1, i[1]) in wl:
                wl.remove((i[0] + 1, i[1]))
                bln.add((i[0] + 1, i[1]))
            if (i[0] - 1, i[1]) in wl:
                wl.remove((i[0] - 1, i[1]))
                bln.add((i[0] - 1, i[1]))
            if (i[0], i[1] + 1) in wl:
                wl.remove((i[0], i[1] + 1))
                bln.add((i[0], i[1] + 1))
            if (i[0], i[1] - 1) in wl:
                wl.remove((i[0], i[1] - 1))
                bln.add((i[0], i[1] - 1))
        bl = bln
        r += 1
    return r
print(main())

Submission status: Wrong Answer

Solution code:
#from collections import deque

num_r,num_c = map(int,input().split())
field = [input() for i in range(num_r)]
q = []
seen = [0]*(num_c*num_r)
count = 0

for i in range(num_r):
  for j in range(num_c):
    if field[i][j] == "#":
      seen[i*num_c+j] = 1
      q.append([i,j])

while q:
  tank = []
  for i in q:
    if (0<=i[0]-1) and (seen[(i[0]-1)*num_c+i[1]] == 0):
      tank.append([i[0]-1,i[1]])
      seen[(i[0]-1)*num_c+i[1]] = 1
    if (i[0]+1<num_r) and (seen[(i[0]+1)*num_c+i[1]] == 0):
      tank.append([i[0]+1,i[1]])
      seen[(i[0]-1)*num_c+i[1]] = 1
    if (0<=i[1]-1) and (seen[i[0]*num_c+(i[1]-1)] == 0):
      tank.append([i[0],i[1]-1])
      seen[i[0]*num_c+(i[1]-1)] = 1
    if (i[1]+1<num_c) and (seen[i[0]*num_c+(i[1]+1)] == 0):
      tank.append([i[0],i[1]+1])
      seen[i[0]*num_c+(i[1]+1)] = 1
      
  count = count + 1
  q = tank

print(count-1)

Submission status: Wrong Answer

Solution code:
num_r,num_c = map(int,input().split())
field = [input() for i in range(num_r)]
q = []
seen = [0]*(num_c*num_r)
count = 0

for i in range(num_r):
  for j in range(num_c):
    if field[i][j] == "#":
      q.append([i,j])

while q:
  tank = []
  for i in q:
    if (0<=i[0]-1) and (seen[(i[0]-1)*num_c+i[1]] == 0):
      tank.append([i[0]-1,i[1]])
      seen[(i[0]-1)*num_c+i[1]] = 1
    if (i[0]+1<num_r) and (seen[(i[0]-1)*num_c+i[1]] == 0):
      tank.append([i[0]+1,i[1]])
      seen[(i[0]-1)*num_c+i[1]] = 1
    if (0<=i[1]-1) and (seen[i[0]*num_c+(i[1]-1)] == 0):
      tank.append([i[0],i[1]-1])
      seen[i[0]*num_c+(i[1]-1)] = 1
    if (i[1]+1<num_c) and (seen[i[0]*num_c+(i[1]+1)] == 0):
      tank.append([i[0],i[1]+1])
      seen[i[0]*num_c+(i[1]+1)] = 1
      
  count = count + 1
  q = tank
  
print(count-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
G = [list(input()) for _ in range(H)]
que = deque([])
# 始点を追加
for i in range(H):
    for j in range(W):
        if G[i][j] == '#':
            que.append([i, j])
cnt = 0
while que:
    h, w = que.popleft()
    dh = [1, 0, -1, 0]
    dw = [0, 1, 0, -1]
    next_que = deque([])
    for j in range(4):
        nh = h + dh[j]
        nw = w + dw[j]
        if 0 <= nh < H and 0 <= nw < W and G[nh][nw] == '.':
            G[nh][nw] = '#'
            next_que.append([nh, nw])
    if not que:
        que = next_que
        cnt += 1
# for l in G:
#     print(*l, sep='')
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque
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] == '#':
            q.append((i, j))
ans = -1

while len(q) != 0:
    ans += 1
    qq = []
    while len(q) != 0:
        t = q.popleft()
        i,j = t[0],t[1]
        if i > 1 and A[i-1][j] == '.':
            qq.append((i-1,j))
            A[i-1][j] = '#'
        if j > 1 and A[i][j-1] == '.':
            qq.append((i,j-1))
            A[i][j-1] = '#'
        if i < H-2 and A[i+1][j] == '.':
            qq.append((i+1,j))
            A[i+1][j] = '#'
        if j < W-2 and A[i][j+1] == '.':
            qq.append((i,j+1))
            A[i][j+1] = '#'
    q = deque(qq)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
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] == '#':
            q.append((i, j))
ans = -1

while len(q) != 0:
    ans += 1
    qq = []
    while len(q) != 0:
        t = q.popleft()
        i,j = t[0],t[1]
        if i > 1 and A[i-1][j] == '.':
            qq.append((i-1,j))
            A[i-1][j] = '#'
        if j > 1 and A[i][j-1] == '.':
            qq.append((i,j-1))
            A[i][j-1] = '#'
        if i < H-1 and A[i+1][j] == '.':
            qq.append((i+1,j))
            A[i+1][j] = '#'
        if j < W-1 and A[i][j+1] == '.':
            qq.append((i,j+1))
            A[i][j+1] = '#'
    q = deque(qq)

print(ans)

Submission status: Wrong Answer

Solution code:
import queue

def bfs(s1,s2):
    queueX = queue.Queue()
    queueY = queue.Queue()
    queueX.put(s1)
    queueY.put(s2)
    s[s1][s2] = 0
    while queueX.empty() == False:
        x = queueX.get()
        y = queueY.get()

        for i in range(4):
            nextX = x + moveR[i]
            nextY = y + moveC[i]
            if 0 <= nextX and nextX < H\
                and 0 <= nextY and nextY < W\
                and s[nextX][nextY] != '#'\
                and (s[nextX][nextY] == '.' or s[nextX][nextY] > s[x][y] + 1):
                    s[nextX][nextY] = s[x][y] + 1
                    queueX.put(nextX)
                    queueY.put(nextY)

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
moveR = [0, 1, -1, 0]
moveC = [1, 0, 0, -1]

cnt = 0
cntlst = []
for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            cntlst.append([i, j])
            cnt += 1
if cnt == (W * H):
    print(0)
    exit()

for i in cntlst:
    bfs(i[0], i[1])
ans = 0
#for i in range(H):
#    for j in range(W):
#        ans = max(ans, s[i][j])

print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = []
nb = 0
q = []
for j in range(H):
    A.append(list(input()))
    nb += A[-1].count("#")
    for i in range(W):
        if A[-1][i] == "#":
            q.append([j, i])

addblack = 0
temp = 0
while True:
    nq = []
    temp += 1
    for ty, tx in q:
        for dy, dx in ((0, 1), (1, 0), (-1, 0), (0, -1)):
            ny, nx = ty + dy, tx + dx
            if ny < 0 or ny >= H or nx < 0 or nx >= W:
                continue
            elif A[ny][nx] == "#":
                continue
            else:
                A[ny][nx] = "#"
                addblack += 1
                nq.append([ny, nx])
        q = nq
    
    if addblack + nb == H * W:
        print(temp)
        break

Submission status: Wrong Answer

Solution code:
import queue
import copy

H,W = map(int,input().split())
c =[]
c.append(['×' for _ in range(W+2)])
ans = []
ans.append([0 for _ in range(W+2)])
p = queue.Queue()
for i in range(H):
    tmp = list('×'+input()+'×')
    ans_tmp = []
    for j in range(W+2):
        if tmp[j] == '#':
            ans_tmp.append(0)
            p.put([j,i+1])
        elif tmp[j] == '×':
            ans_tmp.append(0)
        else:
            ans_tmp.append(10**4)
    c.append(tmp)
    ans.append(ans_tmp)

c.append(['×' for _ in range(W+2)])
ans.append([0 for _ in range(W+2)])
q = queue.Queue()
c_copy = copy.deepcopy(c)

def bfs(p):
    while not p.empty():
        tmp = p.get()
        print(tmp)
        q.put(tmp)
        c = copy.deepcopy(c_copy)
        while not q.empty():
            x,y = q.get()
            """
            if [x,y] == [gx,gy]:
                return ans[gy][gx]
            """
            if c[y][x-1] == '.':
                q.put([x-1,y])
                ans[y][x-1] = min(ans[y][x] + 1,ans[y][x-1])
                c[y][x-1] = '#'
            if c[y][x+1] == '.':
                q.put([x+1,y])
                ans[y][x+1] = min(ans[y][x] + 1,ans[y][x+1])
                c[y][x+1] = '#'
            if c[y-1][x] == '.':
                q.put([x,y-1])
                ans[y-1][x] = min(ans[y][x] + 1,ans[y-1][x])
                c[y-1][x] = '#'
            if c[y+1][x] == '.':
                q.put([x,y+1])
                ans[y+1][x] = min(ans[y][x] + 1,ans[y+1][x])
                c[y+1][x] = '#'

bfs(p)
max_ans = 0
for i in range(H+2):
    #print(ans[i])
    max_ans = max(max_ans,max(ans[i]))

print(max_ans)

Submission status: Wrong Answer

Solution code:
import queue
import copy

H,W = map(int,input().split())
c =[]
c.append(['-' for _ in range(W+2)])
ans = []
ans.append([0 for _ in range(W+2)])
sharp = []
for i in range(H):
    tmp = list('|'+input()+'|')
    ans_tmp = []
    for j in range(W+2):
        if tmp[j] == '#':
            ans_tmp.append(0)
            sharp.append([i+1,j])
        elif tmp[j] == '.':
            ans_tmp.append(10**4)
        else:
            ans_tmp.append(0)
    c.append(tmp)
    ans.append(ans_tmp)

c.append(['-' for _ in range(W+2)])
ans.append([0 for _ in range(W+2)])
q = queue.Queue()

def bfs(x,y):
    q.put([x,y])

    while not q.empty():
        x,y = q.get()
        """
        if [x,y] == [gx,gy]:
            return ans[gy][gx]
        """
        if c[y][x-1] == '.':
            q.put([x-1,y])
            ans[y][x-1] = min(ans[y][x] + 1,ans[y][x-1])
            c[y][x-1] = '#'
        if c[y][x+1] == '.':
            q.put([x+1,y])
            ans[y][x+1] = min(ans[y][x] + 1,ans[y][x+1])
            c[y][x+1] = '#'
        if c[y-1][x] == '.':
            q.put([x,y-1])
            ans[y-1][x] = min(ans[y][x] + 1,ans[y-1][x])
            c[y-1][x] = '#'
        if c[y+1][x] == '.':
            q.put([x,y+1])
            ans[y+1][x] = min(ans[y][x] + 1,ans[y+1][x])
            c[y+1][x] = '#'

c_copy = copy.deepcopy(c)

for l in sharp:
    c = copy.deepcopy(c_copy)
    bfs(l[0],l[1])

max_ans = 0
for i in range(H+2):
    #print(ans[i])
    max_ans = max(max_ans,max(ans[i]))

print(max_ans)

Submission status: Wrong Answer

Solution code:

from collections import deque
import numpy as np
H,W = map(int,input().split())
A = [list(input()) for _ in range(H)]
table = [[float('inf')]*(W) for _ in range(H)]
visited = [[False]*(W) for _ in range(H)]
start = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            table[i][j] = 0
            start.append((i,j))
for (sy, sx) in start:
    visited[sy][sx] = True
    que = deque([(sx,sy)])
    while que:
        y,x = que.popleft()
        for dy, dx in ((1,0),(-1,0),(0,1),(0,-1)):
            ny,nx = y+dy, x+dx
            if 0<=ny<H and 0<=nx<W:
                if table[ny][nx] == float('inf'):
                    table[ny][nx] = table[y][x]+1
                    que.append((ny, nx))
print(np.array(table).max())

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W=map(int, input().split())
S=[]
S.append(list(['X']*(W+2)))
for h in range(H):
    S.append(['X']+list(input())+['X'])
S.append(list(['X']*(W+2)))

q=deque([])
d=[(1,0),(-1,0),(0,1),(0,-1)]
cnt_n=0
def add_q(S):
    for h in range(1,H+1):
        for w in range(1,W+1):
            for dy,dx in d:
                if (S[h][w]=='#') & (S[h+dy][w+dx]=='.'):
                    q.append([h+dy,w+dx])
    return S,q

def chnge_are(S,q):
    while q:
        y,x = q.popleft()
        S[y][x]='#'
    return S
        
def res_chk(S,cnt_n):
    res=0
    for h in range(H+2):
        if S[h].count('.')!=0:
            res=1
    if res==1:
        cnt_n+=1
        S,q=add_q(S)
        S=chnge_are(S,q)
        return res_chk(S,cnt_n)
    else:
        return cnt_n

res_chk(S,cnt_n)

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W=map(int, input().split())
S=[]
S.append(list(['X']*(W+2)))
for h in range(H):
    S.append(['X']+list(input())+['X'])
S.append(list(['X']*(W+2)))

q=deque([])
d=[(1,0),(-1,0),(0,1),(0,-1)]
cnt_n=0
def add_q(S):
    for h in range(1,H+1):
        for w in range(1,W+1):
            if S[h][w]=='#':
                for dy,dx in d:
                    q.append([h+dy,w+dx])
    return S,q

def chnge_are(S,q):
    while q:
        y,x = q.popleft()
        S[y][x]='#'
    return S
        
def res_chk(S,cnt_n):
    res=0
    for h in range(H+2):
        if S[h].count('.')!=0:
            res=1
    if res==1:
        cnt_n+=1
        S,q=add_q(S)
        S=chnge_are(S,q)
        return res_chk(S,cnt_n)
    else:
        return cnt_n

res_chk(S,cnt_n)

Submission status: Wrong Answer

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

que = deque()
seen = [[-1]*W for _ in range(H)]
max = 0



for i in range(H):
    for j in range(W):
        if map[i][j] == "#":
            que.append([i,j])
            seen[i][j] = 0

while que:
    print(que)
    y, x = que.popleft()
    for dy, dx in ([0,1],[0,-1],[1,0],[-1,0]):
        ny = y + dy
        nx = x + dx
        if 0<=ny<H and 0<=nx<W and seen[ny][nx]==-1:
            seen[ny][nx] = seen[y][x] + 1
            que.append([ny,nx])
            if max < seen[ny][nx]:
                max = seen[ny][nx]

print(max)

Submission status: Wrong Answer

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

que = deque()
seen = [[-1]*W for _ in range(H)]
max = 0

t1 = time.time()

for i in range(H):
    for j in range(W):
        if map[i][j] == "#":
            que.append([i,j])
            seen[i][j] = 0

#while que:
#    y, x = que.popleft()
#    for dy, dx in ([0,1],[0,-1],[1,0],[-1,0]):
#        ny = y + dy
#        nx = x + dx
#        if 0<=ny<H and 0<=nx<W and seen[ny][nx]==-1:
#            seen[ny][nx] = seen[y][x] + 1
#            que.append([ny,nx])
#            if max < seen[ny][nx]:
#                max = seen[ny][nx]

print(max)

Submission status: Wrong Answer

Solution code:
print(5)

Submission status: Wrong Answer

Solution code:
# 迷路読み込み
h,w = map(int, input().split())
maze=[list(input()) for i in range(h)]

for i in range(h):
    maze[i]=['#']+maze[i]+['#']
maze=[['#' for i in range(w+2)]]+maze+[['#' for i in range(w+2)]]

import collections
from collections import deque

INF = -10 ** 9
distance = [[INF for i in range(w+1)] for j in range(h+1)]
d = deque()
def bfs():
    cnt=0
    while len(d):
        x, y = d.pop()
        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

            if (0 <= nx and  0 <= ny  and maze[nx][ny] != '#' and distance[nx][ny] == INF):
                d.appendleft((nx, ny))
                distance[nx][ny] = distance[x][y] + 1
                if cnt<distance[nx][ny]:
                    cnt=distance[nx][ny]

    return cnt


for i in range(1,h+1):
    for j in range(1,w):
        if maze[i][j]=='#':
            d.append((i,j))
            distance[i][j]=0
print(bfs())

Submission status: Wrong Answer

Solution code:
from collections import deque


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

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

que = deque()
flag = False
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            que.append((i, j))
            flag = True

if flag is False:
    print(0)
    exit()

n_que = deque()
step = 0
while len(que):

    h, w = que[0][0], que[0][1]
    que.popleft()
    for d in range(4):
        nh, nw = h + dy[d], w + dx[d]
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        if maze[nh][nw] is '#':
            continue
        n_que.append((nh, nw))
        maze[nh][nw] = "#"

    if len(que) == 0:
        if len(n_que) == 0:
            print(step)
            exit()
        que = n_que
        n_que = deque()
        step += 1

Submission status: Wrong Answer

Solution code:
def main():
  from collections import deque

  h,w=map(int,input().split())
  a=[["#"]+list(map(str,input().strip("\n")))+["#"] for e in range(h)]
  b=["#" for _ in range(w+2)]
  c=[b]+a+[b]
  
  que=deque()
  for i in range(1,h+1):
    for j in range(1,w+1):
      if c[i][j]=="#":
        que.append([i,j])
  xy=[(1,0),(0,1),(-1,0),(0,-1)]
  count=0
  while(que):
    i,j=que.popleft()
    check=0
    for x,y in xy:
      if c[i+x][j+y]==".":
        check+=1
        c[i+x][j+y]="#"
    if len(que)==0: 
      count+=1
      for i in range(1,h+1):
        for j in range(1,w+1):
          if c[i][j]=="#":
            que.append([i,j])
      if len(que)==w*h:
        break
  print(count)
  
if __name__=="__main__":
  main()

Submission status: Wrong Answer

Solution code:
from collections import deque


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

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

longest = 0
reached = [[-1 for _ in range(W)] for _ in range(H)]

for sh in range(H):
    for sw in range(W):
        if (reached[sh][sw] is -1) and (maze[sh][sw] == '.'):
            # start bfs
            togo = deque()
            togo.append((sh, sw))
            reached[sh][sw] = 0
            path = 0

            while len(togo):
                h, w = togo[0][0], togo[0][1]
                togo.popleft()
                for d in range(4):
                    nh, nw = h + dy[d], w + dx[d]
                    if nh < 0 or nw < 0 or nh >= H or nw >= W:
                        continue
                    if maze[nh][nw] == '#':
                        path = reached[h][w] + 1
                        break
                    if reached[nh][nw] != -1:
                        continue
                    togo.append((nh, nw))
                    reached[nh][nw] = reached[h][w] + 1

                if path != 0:
                    if longest < path:
                        longest = path
                    break

print(longest)

Submission status: Wrong Answer

Solution code:
from collections import deque


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

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

longest = 0
reached = [[-1 for _ in range(W)] for _ in range(H)]

for sh in range(H):
    for sw in range(W):
        if (reached[sh][sw] is -1) and (maze[sh][sw] == '.'):
            # start bfs
            togo = deque()
            togo.append((sh, sw))
            reached[sh][sw] = 0
            path = 0

            while len(togo):
                h, w = togo[0][0], togo[0][1]
                togo.popleft()
                for d in range(4):
                    nh, nw = h + dy[d], w + dx[d]
                    if nh < 0 or nw < 0 or nh >= H or nw >= W:
                        continue
                    if maze[nh][nw] == '#':
                        path = reached[h][w] + 1
                        break
                    if reached[nh][nw] != -1:
                        continue
                    togo.append((nh, nw))
                    reached[nh][nw] = reached[h][w] + 1

                if path != 0:
                    if longest < path:
                        longest = path
                    break

print(longest)

Submission status: Wrong Answer

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



H, W = map(int, input().split())
C = [list(input()) for _ in range(H)]
gone = [[0] * W for _ in range(H)]
cot = 0
que = deque()

que_count = 0
for h in range(H):
    for w in range(W):
        if C[h][w] == "#":
            gone[h][w] = 1
            que.append((h,w))
            que_count += 1
            cot += 1
INF = 10 ** 9
go = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans  = 0
nq = 0
while cot != H*W:
    while que_count != 0 and cot != H*W:
        h,w = que.popleft()
        que_count -= 1
        for temp in go:
            # この時，実際に行くのかは不明
            gx,gy = temp
            nx = w + gx
            ny = h + gy

            if 0<= nx < W and 0<= ny < H and gone[ny][nx] != 1: #行って無かったら，行く
                # この時に実際に移動する
                gone[ny][nx] = 1
                que.append( (ny,nx))
                nq += 1
                cot += 1
    que_count = nq

    ans += 1
print(ans)

Submission status: Wrong Answer

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

A = ['#' * (W + 2)] + ['#' + input() + '#' for i in range(H)] + ['#' * (W + 2)]


B = [[A[i][j] == '#' for j in range(W + 2)] for i in range(H + 2)]


import collections
q = collections.deque()
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if B[i][j] == True:
            q.appendleft((i, j, 0))

while True:
    i, j, c = q.pop()
    if B[i - 1][j] == False:
        q.appendleft((i - 1, j, c + 1))
        B[i - 1][j] = True
    if B[i + 1][j] == False:
        q.appendleft((i + 1, j, c + 1))
        B[i + 1][j] = True
    if A[i][j - 1] == False:
        q.appendleft((i, j - 1, c + 1))
        B[i][j - 1] = True
    if B[i][j + 1] == False:
        q.appendleft((i, j + 1, c + 1))
        B[i][j + 1] = True


    if len(q) == 0:
        print(c)
        break


# A = [['#' for i in range(W + 2)]]\
#     + [list('#' + input() + '#') for i in range(H)]\
#     + [['#' for i in range(W + 2)]]
# import collections
# q = collections.deque()
# for i in range(1, H + 1):
#     for j in range(1, W + 1):
#         if A[i][j] == '#':
#             q.appendleft((i, j, 0))

# while True:
#     i, j, c = q.pop()
#     if A[i - 1][j] == '.':
#         q.appendleft((i - 1, j, c + 1))
#         A[i - 1][j] = '#'
#     if A[i + 1][j] == '.':
#         q.appendleft((i + 1, j, c + 1))
#         A[i + 1][j] = '#'
#     if A[i][j - 1] == '.':
#         q.appendleft((i, j - 1, c + 1))
#         A[i][j - 1] = '#'
#     if A[i][j + 1] == '.':
#         q.appendleft((i, j + 1, c + 1))
#         A[i][j + 1] = '#'


#     if len(q) == 0:
#         print(c)
#         break

Submission status: Wrong Answer

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

from collections import deque
def solve():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    Q = deque()

    cnt=h*w
    for x in range(w):
        for y in range(h):
            if l[y][x]=="#":
                cnt-=1
                Q.append([x,y])
    if cnt==h*w:
        return 0

    ans=0
    while True:
        nxtQ = deque()

        ans+=1
        while Q:
            p = Q.popleft()
            for i in range(4):
                nx = p[0] + dx[i]
                ny = p[1] + dy[i]

                if 0 <= nx < w and 0 <= ny < h:
                    if l[ny][nx]==".":
                        l[ny][nx] = "#"
                        nxtQ.append([nx,ny])
                        cnt-=1
        Q=nxtQ
        if cnt<=0:
            return ans

print(solve())

Submission status: Wrong Answer

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

def readlines(n):
    for _ in range(n):
        yield list(input().rstrip())

def main():
    H, W = map(int, input().split())
    A = list(readlines(H))

    dires = [(-1,0),(0, 1),(1, 0),(0, -1)]
    q = deque()
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                q.append((i, j))
    ans = 0
    while q:
        h, w = q.popleft()
        next_q = set()
        for y, x in dires:
            suc_y = h+y
            suc_x = w+x
            if suc_x < 0 or suc_y < 0 or suc_x >= W or suc_y >= H or A[suc_y][suc_x] == "#":
                continue
            A[suc_y][suc_x] = "#"
            next_q.add((suc_y, suc_x))

        if not q:
            ans += 1
            q = deque(next_q)
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
painted = [list(input()) for _ in range(h)]
starts = []
for y in range(h):
    for x in range(w):
        if painted[y][x] == '#':
            starts.append((y, x))


def paint_black(starts):
    que = deque()
    next_position = []
    for start in starts:
        que.append(start)
    while que:
        y, x = que.popleft()
        for iy, ix in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            ny = y + iy
            nx = x + ix
            if (0 <= ny < h) and (0 <= nx < w):
                if painted[ny][nx] != '#':
                    painted[ny][nx] = '#'
                    next_position.append((ny, nx))
    return next_position

cnt = 1
next_position = paint_black(starts)
while not all([i == '#' for row in painted for i in row]):
    cnt += 1
    next_position = paint_black(next_position)

print(cnt)

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
    maxDist = 0
    count = 0
    while len(que) != 0:
        idx = que.pop(0)
        count += 1
        
        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
            maxDist = max(maxDist, 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
            maxDist = max(maxDist, 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
            maxDist = max(maxDist, 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
            maxDist = max(maxDist, dist[idx[0]][idx[1]] + 1)
            area[idx[0]][idx[1]+1] = '#'
            que.append([idx[0], idx[1]+1])
    
    return dist, maxDist, count

startIdx = searchBlackIdx(area)

dist, maxDist, count = calcDist(startIdx, area)
print(maxDist, count)

Submission status: Wrong Answer

Solution code:
H, W = list(map(int, input().split()))
 
start = []
c = []
for y in range(H):
    c.append(input())
    for x in range(W):
        if c[-1][x]=='#':
            start.append([y,x])
            
visited = [0 for _ in range(W*H)]
for one in start:
    visited[one[0]*W+one[1]] = 1
    
cnt = 0
while sum(visited)!=W*H:
    tmp_s = []
    for one in start:
        cy,cx = one
        for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            ny, nx = cy+dy, cx+dx
            if 0 <= nx < W and 0 <= ny < H and visited[ny*W+nx]==0:
                visited[ny*W+nx] = 1
                tmp_s.append([ny,nx])
    cnt+=1
    start = tmp_s
    print(start)
print(cnt)