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 numpy as np
from collections import deque
H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]

d = np.full((H, W), 2001)


def bfs(i, j):
    q = deque()
    q.append((i, j))
    d[i][j] = 0

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

            if (0 <= nx < H) and (0 <= ny < W) and d[nx][ny] > d[x][y] + 1:
                q.append((nx, ny))
                if grid[nx][ny] == '#':
                    d[nx][ny] = 0
                else:
                    d[nx][ny] = d[x][y] + 1


for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            bfs(i, j)
            break
    else:
        continue
    break

print(np.amax(d))

Submission status: Wrong Answer

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

d = np.full((H, W), 1001)


def bfs(i, j):
    q = deque()
    q.append((i, j))
    d[i][j] = 0

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

            if (0 <= nx < H) and (0 <= ny < W) and d[nx][ny] > d[x][y] + 1:
                q.append((nx, ny))
                if grid[nx][ny] == '#':
                    d[nx][ny] = 0
                else:
                    d[nx][ny] = d[x][y] + 1


for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            bfs(i, j)
            break
    else:
        continue
    break

print(np.amax(d))

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    h, w = list(map(int, readline().split()))
    a = [[True] * w for _ in range(h)]
    ql = []
    ql = collections.deque(ql)
    for i in range(h):
        s = str(readline().rstrip().decode('utf-8'))
        for j in range(w):
            if s[j] == "#":
                ql.append([0, i, j])

    mt = 0
    while True:
        if len(ql) != 0:
            cost, x, y = ql.popleft()
            mt = max(mt, cost)
            for xv, yv in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if a[xv][yv] == ".":
                        ql.append([cost + 1, xv, yv])
                        a[xv][yv] = "#"
        else:
            break
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    h, w = list(map(int, readline().split()))
    a = [[True] * w for _ in range(h)]
    ql = []
    ql = collections.deque(ql)
    for i in range(h):
        s = str(readline().rstrip().decode('utf-8'))
        for j in range(w):
            if s[j] == "#":
                ql.append([0, i, j])

    mt = 0
    while True:
        if len(ql) != 0:
            cost, x, y = ql.popleft()
            mt = max(mt, cost)
            for xv, yv in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if a[xv][yv] and a[xv][yv] == ".":
                        ql.append([cost + 1, xv, yv])
                        a[xv][yv] = "#"
        else:
            break
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    h, w = list(map(int, input().rstrip('\n').split()))
    a = [["."] * w for _ in range(h)]
    ql = []
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    for i in range(h):
        s = str(readline().rstrip().decode('utf-8'))
        for j in range(w):
            if a[i][j] == "#":
                a[i][j] = "#"
                ql.append([0, i, j])
                fq[i, j]

    mt = 0
    while True:
        if len(ql) != 0:
            cost, x, y = ql.popleft()
            mt = max(mt, cost)
            for xv, yv in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if (xv, yv) not in fq and a[xv][yv] == ".":
                        ql.append([cost + 1, xv, yv])
                        fq[xv, yv]
        else:
            break
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy
H,W = map(int, input().split())
field = [[j == "#" for j in input()] for _ in range(H)]
dy = [1,-1,0,0]
dx = [0,0,1,-1]

queue = deque()
# sy,sx = 0,0
# gy,gx = H-1,W-1
que = deque([(i, j) for i in range(H) for j in range(W) if field[i][j]])
# for i in range(H):
#     for j in range(W):
#         if field[i][j] == True:
#             queue.append([i,j])
# queue = [[sy,sx]]
flag = False
count = 0
while True:
    count += 1
    nqueue = deque()
    while queue:
        h,w = queue.popleft()
        for i in range(4):
            nh = h + dy[i]
            nw = w + dx[i]
            if (0<=nh<H) and (0<=nw<W):
                if field[nh][nw] == False:
                    field[nh][nw] = True
                    nqueue.append([nh,nw])
    if nqueue:
        queue = copy.copy(nqueue)
    else:
        break
print(count-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int, input().split())
A = []
for _ in range(H):
    temp = list(input())
    A.append(temp)
ans = 0
Q = deque([])
def bfs(x,y):
    next_ = [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]
    for i in next_:
        if 0 <= i[0] <= H-1 and 0 <= i[1] <= W-1 and A[i[0]][i[1]] == ".":
            A[i[0]][i[1]] = "#"
            Q.append([i[0],i[1]])

for j in range(H):
    for k in range(W):
        if A[j][k] == "#":
            Q.append([j,k])

while len(Q) > 0:
    for _ in range(len(Q)):
        Q_next = Q.popleft()
        bfs(Q_next[0],Q_next[1])
    ans += 1
    break_loop = 1
    for r in range(H):
        if "." in A[r]:
            break_loop = 0
    if break_loop:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
a1 = [[1000] * (w+2) for i in range(h+2)]
a2 = [['.'] * (w+2) for i in range(h+2)]
for i in range(h):
  a2[i+1][1:-1] = list(input())
for i in range(h):
  for j in range(w):
    if a2[i+1][j+1] == '#':
      a1[i+1][j+1] = 0
for i in range(w):
  for j in range(h):
    a1[j+1][i+1] = min(a1[j][i+1]+1,a1[j+1][i+1])
for i in range(w):
  for j in range(h):
    a1[h-j][i+1] = min(a1[h-j+1][i+1]+1,a1[h-j][i+1])
for i in range(h):
  for j in range(w):
    a1[i+1][j+1] = min(a1[i+1][j]+1,a1[i+1][j+1])
for i in range(h):
  for j in range(w):
    a1[i+1][w-j] = min(a1[i+1][w-j+1]+1,a1[i+1][w-j])
m = 0
for i in range(h):
  for j in range(w):
    m = max(m,a1[i+1][j+1])
print(m)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
a=['*'*(w+2)]+['*'+input()+'*' for _ in range(h)]+['*'*(w+2)]
from collections import deque
d=deque()
c=[[0]*w for _ in range(h)]
for i in range(1,h+1):
  for j in range(1,w+1):
    if a[i][j]=='#':
      d.append([i,j])
di=[[0,1],[1,0],[-1,0],[0,-1]]
while d:
  g=d.popleft()
  for i in di:
    x=g[0]+i[0]
    y=g[1]+i[1]
    if a[x][y]=='.':
      if c[x-1][y-1]==0:
        d.append([x,y])
        c[x-1][y-1]=c[g[0]-1][g[1]-1]+1
m=0
for i in range(h-1):
  for j in range(w-1):
    m=max(m,c[i][j])
print(m)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
a=['*'*(w+2)]+['*'+input()+'*' for _ in range(h)]+['*'*(w+2)]
from collections import deque
d=deque()
c=[[0]*w for _ in range(h)]
for i in range(1,h+1):
  for j in range(1,w+1):
    if a[i][j]=='#':
      d.append([i,j])
      c[i-1][j-1]=1
di=[[0,1],[1,0],[-1,0],[0,-1]]
while d:
  g=d.popleft()
  for i in di:
    x=g[0]+i[0]
    y=g[1]+i[1]
    if a[x][y]=='.':
      if c[x-1][y-1]==0:
        d.append([x,y])
        c[x-1][y-1]=c[g[0]-1][g[1]-1]+1
m=0
for i in range(h-1):
  for j in range(w-1):
    m=max(m,c[i][j])
print(m)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import heapq
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

h,w=map(int,input().split())
A=[list(input()) for i in range(h)]
# print(A)
dis=[[-1]*w for i in range(h)]
hq=[]
for i in range(h):
    for j in range(w):
        if A[i][j]=="#":
            hq.append((0,i,j))
            dis[i][j]=0
dii=[(1,0),(-1,0),(0,1),(0,-1)]
heapq.heapify(hq)
ans=0
while hq:
    count,i,j=heapq.heappop(hq)
    for di,dj in dii:
        if not (0<=i+di<h and 0<=j+dj<w):
            continue
        if dis[i+di][j+dj]==-1:
            heapq.heappush(hq, (count+1, i+di, j+dj))
            dis[i+di][j+dj]=count+1
            ans=max(ans,count+1)
#             # print(count+1)
# ans=0
# for Ai in dis:
#     ans=max(ans,max(Ai))
# print(ans)
# for d in dis:
#     print(d)

Submission status: Wrong Answer

Solution code:
def main():
    h,w = map(int,input().split()) 
    x=[[-1 for _ in range(w)] for _ in range(h)]
    a=[]
    for _ in range(h):
        a.append(list(input()))
    for i in range(h):
        for j in range(w):
            if a[i][j]=="#":
                x[i][j]=0
    cnt=0
    check=0
    while True:
        key=0
        for i in range(h):
            for j in range(w):
                if x[i][j]==-1:
                    if j<w-1 and x[i][j+1]==check:
                        x[i][j]=x[i][j+1]+1
                    elif 0<j and x[i][j-1]==check:
                        x[i][j]=x[i][j-1]+1
                    elif i<h-1 and x[i+1][j]==check:
                        x[i][j]=x[i+1][j]+1
                    elif 0<i and x[i-1][j]==check:
                        x[i][j]=x[i-1][j]+1
                    else:
                        key=1
        if key==0:
            cnt+=1
            print(cnt)
            return
        else:
            check+=1
            cnt+=1
    print(cnt)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    h,w = map(int,input().split()) 
    x=[]
    for _ in range(h):
        x.append(list(input()))
    for i in range(h):
        for j in range(w):
            if x[i][j]=="#":
                x[i][j]=0
    cnt=0
    check=0
    while True:
        key=0
        for i in range(h):
            for j in range(w):
                if x[i][j]=='.':
                    if j<w-1 and x[i][j+1]==check:
                        x[i][j]=x[i][j+1]+1
                    elif 0<j and x[i][j-1]==check:
                        x[i][j]=x[i][j-1]+1
                    elif i<h-1 and x[i+1][j]==check:
                        x[i][j]=x[i+1][j]+1
                    elif 0<i and x[i-1][j]==check:
                        x[i][j]=x[i-1][j]+1
                    else:
                        key=1
        if key==0:
            cnt+=1
            print(cnt)
            return
        else:
            check+=1
            cnt+=1
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
line = sys.stdin.readline

H, W = map(int, line().split())
grid = np.full((H + 2, W + 2), 1000)
grid[1:-1, 1:-1] = (np.array([list(line().rstrip()) for _ in range(H)]).reshape(H, W) == '#') * 1
grid2 = grid.copy()
grid2[1:-1, 1:-1] = np.where(grid2[1:-1, 1:-1] < 1, 1, 0)

down = grid.copy()
for i in range(1, H + 1):
    down[i, 1:-1] = (down[i - 1, 1:-1] * grid2[i - 1, 1:-1] + grid2[i, 1:-1]) * grid2[i, 1:-1]

up = grid.copy()
for i in range(H, 0, -1):
    up[i, 1:-1] = (up[i + 1, 1:-1] * grid2[i + 1, 1:-1] + grid2[i, 1:-1]) * grid2[i, 1:-1]

right = grid.copy()
for i in range(1, W + 1):
    right[1:-1, i] = (right[1:-1, i - 1] * grid2[1:-1, i - 1] + grid2[1:-1, i]) * grid2[1:-1, i]

left = grid.copy()
for i in range(W, 0, -1):
    left[1:-1, i] = (left[1:-1, i + 1] * grid2[1:-1, i + 1] + grid2[1:-1, i]) * grid2[1:-1, i]

v = np.minimum(down, up)
h = np.minimum(left, right)

answer = np.minimum(v, h)
for i in range(1, H):
    answer[i + 1] = np.minimum(answer[i] + 1, answer[i + 1])
for i in range(H, 0, -1):
    answer[i - 1] = np.minimum(answer[i] + 1, answer[i - 1])
print(np.max(answer[1:-1, 1:-1]))

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
line = sys.stdin.readline

H, W = map(int, line().split())
grid = np.full((H + 2, W + 2), 1000)
grid[1:-1, 1:-1] = (np.array([list(line().rstrip()) for _ in range(H)]).reshape(H, W) == '#') * 1
grid2 = grid.copy()
grid2[1:-1, 1:-1] = np.where(grid2[1:-1, 1:-1] < 1, 1, 0)

down = grid.copy()
for i in range(1, H + 1):
    down[i, 1:-1] = (down[i - 1, 1:-1] * grid2[i - 1, 1:-1] + grid2[i, 1:-1]) * grid2[i, 1:-1]

up = grid.copy()
for i in range(H, 0, -1):
    up[i, 1:-1] = (up[i + 1, 1:-1] * grid2[i + 1, 1:-1] + grid2[i, 1:-1]) * grid2[i, 1:-1]

right = grid.copy()
for i in range(1, W + 1):
    right[1:-1, i] = (right[1:-1, i - 1] * grid2[1:-1, i - 1] + grid2[1:-1, i]) * grid2[1:-1, i]

left = grid.copy()
for i in range(W, 0, -1):
    left[1:-1, i] = (left[1:-1, i + 1] * grid2[1:-1, i + 1] + grid2[1:-1, i]) * grid2[1:-1, i]

v = np.minimum(down, up)
h = np.minimum(left, right)

answer = np.minimum(v, h)
for i in range(1, H):
    answer[i + 1] = np.minimum(answer[i] + 1, answer[i + 1])
for i in range(H, 0, -1):
    answer[i - 1] = np.minimum(answer[i] + 1, answer[i - 1])
print(answer[1:-1, 1:-1].max())

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
line = sys.stdin.readline

R, C = map(int, line().split())
grid = np.zeros((R + 2, C + 2), np.int32)
grid[1:-1, 1:-1] = (np.array([list(line().rstrip()) for _ in range(R)]).reshape(R, C) == '#') * 1
grid[0] = 1
grid[-1] = 1
grid[:, 0] = 1
grid[:, -1] = 1
grid = np.where(grid < 1, 1, 0)

down = grid.copy()
for i in range(R, 0, -1):
    down[i] = (down[i + 1] + down[i]) * grid[i]

up = grid.copy()
for i in range(1, R + 1):
    up[i] = (up[i - 1] + up[i]) * grid[i]

right = grid.copy()
for i in range(C, 0, -1):
    right[:, i] = (right[:, i + 1] + right[:, i]) * grid[:, i]

left = grid.copy()
for i in range(1, C + 1):
    left[:, i] = (left[:, i - 1] + left[:, i]) * grid[:, i]

grid_h = (np.minimum(left, right)) * grid
grid_v = (np.minimum(up, down)) * grid
grid = np.minimum(grid_v, grid_h)

answer = grid.max()

print(answer)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
line = sys.stdin.readline

R, C = map(int, line().split())
grid = np.zeros((R + 2, C + 2), np.int32)
grid[1:-1, 1:-1] = (np.array([list(line().rstrip()) for _ in range(R)]).reshape(R, C) == '#') * 1
grid = np.where(grid < 1, 1, 0)

down = grid.copy()
for i in range(R, 0, -1):
    down[i] = (down[i + 1] + down[i]) * grid[i]

up = grid.copy()
for i in range(1, R + 1):
    up[i] = (up[i - 1] + up[i]) * grid[i]

right = grid.copy()
for i in range(C, 0, -1):
    right[:, i] = (right[:, i + 1] + right[:, i]) * grid[:, i]

left = grid.copy()
for i in range(1, C + 1):
    left[:, i] = (left[:, i - 1] + left[:, i]) * grid[:, i]

grid_h = (np.minimum(left, right)) * grid
grid_v = (np.minimum(up, down)) * grid
grid = np.minimum(grid_v, grid_h)

answer = grid.max()

print(answer)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
line = sys.stdin.readline

R, C = map(int, line().split())
grid = np.zeros((R + 2, C + 2), np.int32)
grid[1:-1, 1:-1] = (np.array([list(line().rstrip()) for _ in range(R)]).reshape(R, C) == '.') * 1
left = np.zeros((R + 2, C + 2), np.int32)
right = np.zeros((R + 2, C + 2), np.int32)
up = np.zeros((R + 2, C + 2), np.int32)
down = np.zeros((R + 2, C + 2), np.int32)

down[R] = grid[R]
for i in range(R, 0, -1):
    down[i - 1] = (down[i] + 1) * grid[i - 1]

up[1] = grid[1]
for i in range(1, R):
    up[i + 1] = (up[i] + 1) * grid[i + 1]

right[:, C] = grid[:, C]
for i in range(C, 0, -1):
    right[:, i - 1] = (right[:, i] + 1) * grid[:, i - 1]

left[:, 1] = grid[:, 1]
for i in range(1, C):
    left[:, i + 1] = (left[:, i] + 1) * grid[:, i + 1]

grid_h = (np.minimum(left, right)) * grid
grid_v = (np.minimum(up, down)) * grid
grid = np.minimum(grid_v, grid_h)
for i in range(1, R):
    grid[i + 1] = np.minimum(grid[i] + 1, grid[i + 1])
for i in range(R, 0, -1):
    grid[i - 1] = np.minimum(grid[i] + 1, grid[i - 1])

answer = grid.max() + 1

print(answer)

Submission status: Wrong Answer

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

state = []
# 初期状態
for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            state.append([w, h])

tmp = []
ret = 0
while len(state) > 0:
    ret += 1
    x, y = state.pop()
    for nx, ny in ((1,0), (-1,0), (0,1), (0,-1)):
        nx += x
        ny += y
        if nx < 0 or ny < 0 or nx >= W or ny >= H:
            continue

        if field[ny][nx] == ".":
            field[ny][nx] = "#"
            tmp.append([nx, ny])
    state = tmp
    tmp = list()


print(ret-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
INF = 10**9
sheet = []
log = [[True]*W for i in range(H)]
step = [(-1,0),(1,0),(0,-1),(0,1)]
stuck = deque()
ans = -1

for i in range(H):
  line = input()
  for j in range(W):
    if line[j]=='#':
      stuck += [(i,j,0)]
      log[i][j] = False
      
while stuck:
  y, x, m = stuck.popleft()
  for s in step:
    dx, dy = s
    if x+dx<0 or x+dx>W-1 or y+dy<0 or y+dy>H-1:
      continue
    if log[y+dy][x+dx]:
      log[y+dy][x+dx]=False
      stuck += [(y+dy, x+dx, m+1)]
      if ans<m+1:
        ans = m+1
      
print(ans)

Submission status: Wrong Answer

Solution code:
# 最初に黒マスを全部queueに突っ込めばOK
from collections import deque
import itertools

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

c = []
for _ in range(H):
    c.append(input())

d = deque()
score = [[-1 for _ in range(W)] for _ in range(H)]

for y in range(H):
    for x in range(W):
        if c[y][x] == '#':
            score[y][x] = 0
            d.append([y, x])

diff = [[-1, 0], [1, 0], [0, -1], [0, 1]]

ans = -1

while len(d) > 0:
    y, x = d.popleft()

    for dy, dx in diff:
        ny, nx = y + dy, x + dx
        if nx >= 0 and ny >= 0 and nx < W and ny < H and score[ny][nx] == -1:
            score[ny][nx] = score[y][x] + 1
            ans = max(ans, score[ny][nx])
            d.append([ny, nx])

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

input = sys.stdin.readline


class AtCoder:
    def main(self):
        H, W = map(int, input().split())
        A = [list(input().rstrip()) for _ in range(H)]

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

        moving_range = ((1, 0), (-1, 0), (0, -1), (0, 1))

        ans = 0
        # while blacks:
        #     next_blacks = []
        #     for b_h, b_w in blacks:
        #         for m_h, m_w in moving_range:
        #             target = (b_h + m_h, b_w + m_w)
        #             if field[target] == '.':
        #                 field[target] = '#'
        #                 next_blacks.append(target)
        #     if len(next_blacks) > 0:
        #         ans += 1
        #     blacks = next_blacks

        print(ans)


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

input = sys.stdin.readline


class AtCoder:
    def main(self):
        H, W = map(int, input().split())
        A = [list(input().rstrip()) for _ in range(H)]

        blacks = []
        field = defaultdict(lambda: '#')
        for h in range(H):
            for w in range(W):
                field[(h + 1, w + 1)] = A[h][w]
                if A[h][w] == '#':
                    blacks.append((h + 1, w + 1))

        moving_range = ((1, 0), (-1, 0), (0, -1), (0, 1))

        ans = 0
        # while blacks:
        #     next_blacks = []
        #     for b_h, b_w in blacks:
        #         for m_h, m_w in moving_range:
        #             target = (b_h + m_h, b_w + m_w)
        #             if field[target] == '.':
        #                 field[target] = '#'
        #                 next_blacks.append(target)
        #     if len(next_blacks) > 0:
        #         ans += 1
        #     blacks = next_blacks

        print(ans)


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

input = sys.stdin.readline


class AtCoder:
    def main(self):
        H, W = map(int, input().split())

        blacks = []
        field = defaultdict(lambda: '#')
        for h in range(H):
            for w, c in enumerate(input().rstrip()):
                field[(h + 1, w + 1)] = c
                if c == '#':
                    blacks.append((h + 1, w + 1))

        moving_range = ((1, 0), (-1, 0), (0, -1), (0, 1))

        ans = 0
        # while blacks:
        #     next_blacks = []
        #     for b_h, b_w in blacks:
        #         for m_h, m_w in moving_range:
        #             target = (b_h + m_h, b_w + m_w)
        #             if field[target] == '.':
        #                 field[target] = '#'
        #                 next_blacks.append(target)
        #     if len(next_blacks) > 0:
        #         ans += 1
        #     blacks = next_blacks

        print(ans)


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
S = [input() for _ in range(H)]
C = [[100000]*W for _ in range(H)]

nexts = [[0, 0, -1, 1], [1, -1, 0, 0]]
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            continue
        q = deque()
        q.append((i, j))
        C[i][j] = 0
while len(q) >= 1:
    x, y = q.popleft()
    for k in range(4):
        mx = x + nexts[0][k]
        my = y + nexts[1][k]
        if mx < 0 or my < 0 or mx >= H or my >= W:
            continue
        if C[x][y] + 1 >= C[mx][my] or S[mx][my] == '#':
            continue
        C[mx][my] = C[x][y] + 1
        q.append((mx, my))
print(max([max(i) for i in C]))

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
M = [[True] * (W+2)]
for i in range(H):
  M.append([True] + [x == '#' for x in input()] + [True])
M.append([True] * (W+2))


nq = []
for y in range(1, H+1):
  for x in range(1, W+1):
    if M[y][x]:
      nq += [(x, y)]

res = 0
while len(nq) > 0:
  q = nq
  nq = []
  while len(q) > 0:
    x, y = q.pop()
    if not M[y-1][x]:
      nq += [(x, y-1)]
      M[y-1][x] = True
    if not M[y+1][x]:
      nq += [(x, y+1)]
      M[y+1][x] = True
    if not M[y][x-1]:
      nq += [(x-1, y)]
      M[y][x-1] = True
    if not M[y][x+1]:
      nq += [(x+1, y-1)]
      M[y][x+1] = True
  res += 1

print(res-1)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
# https://atcoder.jp/contests/agc033/submissions/6021787
buf = sys.stdin.buffer
H,W = map(int,buf.readline().split())
# +1周分だけ
black = np.zeros((H+2,W+2),dtype=np.bool)
# \nがあることに注意
black[1:-1,1:] = (np.frombuffer(buf.read(H*(W+1)),dtype='S1') == b'#').reshape(H,W+1)

INF = 10 ** 4
dist = np.zeros((H,W),dtype=np.int8)
# .のところは０それ以外はINFで初期化
dist[~black[1:-1,1:-1]] = INF
# 右、左、下、上と展開させていく感じ
for n in range(1,H):
    np.minimum(dist[n-1]+1,dist[n],out=dist[n])
for n in range(H-2,-1,-1):
    np.minimum(dist[n+1]+1,dist[n],out=dist[n])
for n in range(1,W):
    np.minimum(dist[:,n-1]+1,dist[:,n],out=dist[:,n])
for n in range(W-2,-1,-1):
    np.minimum(dist[:,n+1]+1,dist[:,n],out=dist[:,n])

print(dist.max())

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
a = [['*' for _ in range(w+2)]]
for _ in range(h):
    a.append(['*'] + list(input()) + ['*'])
a.append(['*' for _ in range(w+2)])

q = set()

def encode(i, j):
    return i*w + j

def decode(x):
    i = x // w
    j = x % w
    return [i, j]

for i in range(1, h+1):
    for j in range(1, w+1):
        if a[i][j] == '#':
            q.add(encode(i, j))

for ans in range(h+w):
    nq = set()
    for x in q:
        i, j = decode(x)
        if a[i][j] == '#':
            for k in [-1,1]:
                if a[i+k][j] == '.':
                    nq.add(encode(i+k, j))
                    a[i+k][j] = '#'
            for k in [-1,1]:
                if a[i][j+k] == '.':
                    nq.add(encode(i, j+k))
                    a[i][j+k] = '#'
    if len(nq) == 0:
        print(ans)
        exit()
    else:
        q = set()
        q = q | nq

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
a = [['*' for _ in range(w+2)]]
for _ in range(h):
    a.append(['*'] + list(input()) + ['*'])
a.append(['*' for _ in range(w+2)])

q = set()

def encode(i, j):
    return (i+1)*w + j

def decode(x):
    i = x // w - 1
    j = x % w
    return [i, j]

for i in range(1, h+1):
    for j in range(1, w+1):
        if a[i][j] == '#':
            q.add(encode(i, j))

for ans in range(h+w):
    nq = set()
    for x in q:
        i, j = decode(x)
        if a[i][j] == '#':
            for k in [-1,1]:
                if a[i+k][j] == '.':
                    nq.add(encode(i+k, j))
                    a[i+k][j] = '#'
            for k in [-1,1]:
                if a[i][j+k] == '.':
                    nq.add(encode(i, j+k))
                    a[i][j+k] = '#'
    if len(nq) == 0:
        print(ans)
        exit()
    else:
        q = set()
        q = q | nq

Submission status: Wrong Answer

Solution code:
H, V = map(int, input().strip().split())
#print(H, V)
grid = [['.'] * V + ['.'] + ['.']]
for i in range(H):
    row = list(input().strip())
    grid.append(['.'] + row + ['.'])
grid.append(['.'] * V + ['.'] + ['.'])
#print(grid)
flag = 1
counter = 0
while flag == 1:
    counter += 1
    for i in range(1, H + 1):
        for j in range(1, V + 1):
            #print(i, j, grid[i][j])
            if grid[i][j] == '#':
                #print()
                #print(i, j, grid[i][j])
                #print()
                if grid[i][j + 1] != '#':
                    grid[i][j + 1] = '*'
                if grid[i][j - 1] != '#':
                    grid[i][j - 1] = '*'
                if grid[i + 1][j] != '#':
                    grid[i + 1][j] = '*'
                if grid[i - 1][j] != '#':
                    grid[i - 1][j] = '*'
    #print()
    #print(grid)
    #print()
    for i in range(1, H + 1):
        for j in range(1, V + 1):
            if grid[i][j] == '*':
                grid[i][j] = '#'
    #print(grid)
    #print()
    test = []
    flag = 0
    for i in range(1, H + 1):
        test.append(grid[i][1:-1])
        if '.' in grid[i][1:-1]:
            flag = 1
    #print(test)
#print()
print(counter)

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs(h, w, board, visited):
    queue = deque([])
    for i in range(h):
        for j in range(w):
            if board[i][j] == "#":
                queue.append([i, j])
                visited[i][j] = 0
    ans = -1
    while queue:
        y, x = queue.popleft()
        for i, j in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            yn, xn = y+i, x+j
            if yn >= h or xn >= w or yn < 0 or xn < 0:
                continue
            if visited[yn][xn] == -1 and board[yn][xn] == ".":
                visited[yn][xn] = visited[y][x] + 1
                queue.append([yn, xn])
                ans = max(ans, visited[yn][xn])

    return ans


def main():
    h, w = map(int, input().split())
    board = [input() for _ in range(h)]
    visited = [[-1 for _ in range(w)] for _ in range(h)]
    print(bfs(h, w, board, visited))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

h, w = map(int, input().split())
b = np.zeros((h, w))

for i in range(h):
    for j, m in enumerate(input()):
        if m == "#": b[i][j] = 1

cnt = 0
while True:
    b1 = np.roll(b, 1, axis=0)
    b2 = np.roll(b, -1, axis=0)
    b3 = np.roll(b, 1, axis=1)
    b4 = np.roll(b, -1, axis=1)
    b1[0, :], b2[h-1, :], b3[:, 0], b4[:, w-1] = 0, 0, 0, 0
    
    b = b + b1 + b2 + b3 + b4
    cnt += 1
    
    if b.all():
        print(cnt)
        break

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=0
while q:
    nq=deque()
    while True:        
        y,x=q.popleft()
        for dy,dx in ((1,0),(-1,0),(0,1),(0,-1)):
            ny=dy+y
            nx=dx+x
            if 0<=ny<h and 0<=nx<w and a[ny][nx]!='#':
                a[ny][nx]='#'
                nq.append((ny,nx))
        if not q:
            ans+=1
            q=nq
            break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
L = [list(input().strip())  for _ in range(N)]
# S = input().strip

al = [[False for _ in range(M)] for _ in range(N)]
d = set()
for i in range(N):
    for j in range(M):
        if L[i][j] == "#":
            al[i][j] = True
            d.add((i, j))
            pass

for i in range(1000):
    if len(d) == 0:
        print(i - 1)
        exit()
    else:
        d2 = set()
        for x, y in d:
            if x - 1 >= 0 and al[x - 1][y] == False:
                al[x - 1][y] = True
                d2.add((x - 1, y))

            if x + 1 < N and al[x + 1][y] == False:
                al[x + 1][y] = True
                d2.add((x + 1, y))

            if y - 1 >= 0 and al[x][y - 1] == False:
                al[x][y - 1] = True
                d2.add((x, y - 1))

            if y + 1 < M and al[x][y + 1] == False:
                al[x][y + 1] = True
                d2.add((x, y + 1))

        d = d2