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:
# -*- coding: utf-8 -*-
# 18:01 -> 18:36 (give up. TLE)
from collections import deque

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

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

A = []
black_deque = deque()

for i in range(H):
    A.append(list(input()))
    black_deque.extend([(i,j) for j in range(W) if A[i][j] == '#'])

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

print(len(black_deque))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# 18:01 -> 18:36 (give up. TLE)
from collections import deque

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

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

A = []
first_black = []

for i in range(H):
    A.append(list(input()))
    first_black.extend([(i,j) for j in range(W) if A[i][j] == '#'])

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

black_deque = deque()
black_deque.extend(first_black)

print(len(black_deque))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# 18:01 -> 
from collections import deque

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

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

A = []
first_black = []

for i in range(H):
    A.append(list(input()))
    first_black.extend([(i,j) for j in range(W) if A[i][j] == '#'])

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

black_deque = deque()
black_deque.extend(first_black)

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

print(depth+1)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
A = [["#"]*(w+2)] + [["#"] + [s for s in input()] + ["#"]
                     for _ in range(h)] + [["#"]*(w+2)]


def main():
    step = 0
    Q = set([])
    for hh in range(1, h + 1):
        for ww in range(1, w + 1):
            if A[hh][ww] == "#":
                if A[hh - 1][ww] == ".":
                    Q.add((hh - 1, ww))
                if A[hh][ww - 1] == ".":
                    Q.add((hh, ww - 1))
                if A[hh + 1][ww] == ".":
                    Q.add((hh + 1, ww))
                if A[hh][ww + 1] == ".":
                    Q.add((hh, ww + 1))
    while len(Q) > 0:
        step += 1
        new = set([])
        while len(Q) > 0:
            hh, ww = Q.pop()
            A[hh][ww] = "#"
            if A[hh - 1][ww] == ".":
                new.add((hh - 1, ww))
            if A[hh][ww - 1] == ".":
                new.add((hh, ww - 1))
            if A[hh + 1][ww] == ".":
                new.add((hh + 1, ww))
            if A[hh][ww + 1] == ".":
                new.add((hh, ww + 1))
        Q = new.copy()
    print(step)
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
import heapq as hp

h, w = map(int, input().split())
a = np.array([list(input()) for _ in range(h)])
a = np.pad(a, 1, 'constant')

q = []
for i in range(h+2):
    for j in range(w+2):
        if a[i][j] == '#':
            hp.heappush(q, (0, i, j))

while q:
    cnt, y, x = hp.heappop(q)
    for dy, dx in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
        ny, nx = dy + y, dx + x
        if a[ny][nx] == '.':
            hp.heappush(q, (cnt + 1, ny, nx))
            a[ny][nx] = '#'
    if np.count_nonzero(a == '#') == w * h:
        print(cnt+1)
        exit()

Submission status: Wrong Answer

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

INF = 1 << 21


def main():
  H, W = list(map(int, input().split()))
  M = [input()[:-1] for _ in range(H)]

  blacks = deque()
  whites = []
  d = [[INF]*W for _ in range(H)]
  for i in range(H):
    for j in range(W):
      if M[i][j] == '#':
        blacks.append((i, j))
        d[i][j] = 0
      elif M[i][j] == '.':
        whites.append((i, j))

  def bfs(q, d):
    is_visited = [[0]*W for _ in range(H)]
    while len(q):
      ur, uc = q.popleft()
      d_ur = d[ur]
      for vr, vc in [(ur+1, uc), (ur-1, uc), (ur, uc-1), (ur, uc+1)]:
        if 0 <= vr < H and \
           0 <= vc < W:

          d_vr = d[vr]
          is_visited_vr = is_visited[vr]
          if not(is_visited_vr[vc]) and not(M[vr][vc] == '#') and \
             (d_vr[vc] > d_ur[uc] + 1):

            d_vr[vc] = d_ur[uc] + 1
            is_visited_vr[vc] = True
            q.append((vr, vc))
    return d

  bfs(blacks, d)

  times = -INF
  for wr, wc in whites:
    if d[wr][wc] > times:
      times = d[wr][wc]
  print(times)


if(__name__ == '__main__'):
  main()

Submission status: Wrong Answer

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

INF = 1 << 21


def main():
  H, W = list(map(int, input().split()))
  M = [input()[:-1] for _ in range(H)]

  blacks = []
  whites = []
  for i in range(H):
    for j in range(W):
      if M[i][j] == '#':
        blacks.append((i, j))
      elif M[i][j] == '.':
        whites.append((i, j))

  def bfs(start, d):
    q = deque()
    q.append(start)
    is_visited = [[0]*W for _ in range(H)]
    d[start[0]][start[1]] = 0
    while len(q):
      ur, uc = q.popleft()
      d_ur = d[ur]
      for vr, vc in [(ur+1, uc), (ur-1, uc), (ur, uc-1), (ur, uc+1)]:
        if 0 <= vr < H and \
           0 <= vc < W:

          d_vr = d[vr]
          is_visited_vr = is_visited[vr]
          if not(is_visited_vr[vc]) and not(M[vr][vc] == '#') and \
             (d_vr[vc] > d_ur[uc] + 1):

            d_vr[vc] = d_ur[uc] + 1
            is_visited_vr[vc] = True
            q.append((vr, vc))
    return d

  d = [[INF]*W for _ in range(H)]
  for sr, sc in blacks:
    d = bfs((sr, sc), d)

  times = -INF
  for wr, wc in whites:
    if d[wr][wc] > times:
      times = d[wr][wc]
  print(times)


if(__name__ == '__main__'):
  main()

Submission status: Wrong Answer

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


def main():
  H, W = list(map(int, input().split()))
  M = [input()[:-1] for _ in range(H)]

  blacks = []
  whites = []
  for i in range(H):
    for j in range(W):
      if M[i][j] == '#':
        blacks.append((i, j))
      elif M[i][j] == '.':
        whites.append((i, j))

  def bfs(start, d):
    q = deque()
    q.append(start)
    is_visited = [[0]*W for _ in range(H)]
    d[start[0]][start[1]] = 0
    while len(q):
      ur, uc = q.popleft()
      for vr, vc in [(ur+1, uc), (ur-1, uc), (ur, uc-1), (ur, uc+1)]:
        if 0 <= vr < H and \
           0 <= vc < W and \
           not(is_visited[vr][vc]) and not(M[vr][vc] == '#') and \
           (d[vr][vc] > d[ur][uc] + 1):

          d[vr][vc] = d[ur][uc] + 1
          is_visited[vr][vc] = True
          q.append((vr, vc))
    return d

  d = [[float('inf')]*W for _ in range(H)]
  for sr, sc in blacks:
    d = bfs((sr, sc), d)

  times = -float('inf')
  for wr, wc in whites:
    times = max(d[wr][wc], times)
  print(times)


if(__name__ == '__main__'):
  main()

Submission status: Wrong Answer

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

def bfs():
    H, W = map(int, input().split())
    ls = deque([])
    D = [[0] * (W+2)]
    D += ([[0] + [float("inf")]*W + [0] for i in range(H)])
    D.append([0]*(W+2))
    G = [["#"]*(W+2)]
    for i in range(H):
        line = [i for i in input().strip()]
        for j in range(W):
            if line[j] == "#":
                ls.append([i+1, j+1, 0])
                D[i+1][j+1] = 0
        G.append(["#"]+line+["#"])
    G.append([["#"]*(W+2)])

    while len(ls) > 0:
        h, w, depth = ls.popleft()
        if depth + 1 < D[h+1][w] and G[h+1][w] != "#":
            ls.append([h+1, w, depth+1])
            D[h+1][w] = depth + 1
        if depth + 1 < D[h-1][w] and G[h-1][w] != "#":
            ls.append([h-1, w, depth+1])
            D[h-1][w] = depth + 1
        if depth + 1 < D[h][w+1] and G[h][w+1] != "#":
            ls.append([h, w+1, depth+1])
            D[h][w+1] = depth + 1
        if depth + 1 < D[h][w-1] and G[h][w-1] != "#":
            ls.append([h, w-1, depth+1])
            D[h][w-1] = depth + 1

    ans = 0
    for h in range(H):
        ans = max(ans, max(D[h]))
        
    return ans
    
print(bfs())

Submission status: Wrong Answer

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

dist = [[-1]*W for _ in range(H)]

black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h,w))
            dist[h][w] = 0

def bfs(black_cells,dist):
    #BFSを用いて、全マス目を黒くする回数を求める

    #Args:
        #black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        #dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
#        　　　（白マスの初期値は0）

    #Returns:
        #g: 操作を繰り返した数

    d = 0
    while black_cells:
        print(dist)
        h,w = black_cells.popleft()
        d = dist[h][w]
        print(d)
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H<= new_h or new_w<0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:
                dist[new_h][new_w] = d+1
                black_cells.append((new_h,new_w))
    return d

d = bfs(black_cells, dist)
print(d)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys


H, W = [int(_) for _ in input().split()]

M = []
q = deque([])
for i in range(H):
    A = input()
    M.append(list(A))
    for j in range(W):
        if A[j] == '#':
            q.append([j, i, 0])

depth_now = 0
depth = 0
count = 0
while len(q) > 0:
    p = q.popleft()
    x = p[0]
    y = p[1]
    depth = p[2]
    if x - 1 >= 0 and M[y][x-1] == '.':
        q.append([x-1, y, depth+1])
        M[y][x-1] = '#'
    if x + 1 < W and M[y][x+1] == '.':
        q.append([x+1, y, depth+1])
        M[y][x+1] = '#'
    if y - 1 >= 0 and M[y-1][x] == '.':
        q.append([x, y-1, depth+1])
        M[y-1][x] = '#'
    if y + 1 < H and M[y+1][x] == '.':
        q.append([x, y+1, depth+1])
        M[y+1][x] = '#'
    count += 1
print(depth, count)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys


H, W = [int(_) for _ in input().split()]

M = []
queues = []
for i in range(H):
    A = input()
    M.append(list(A))
    for j in range(W):
        if A[j] == '#':
            queues.append(deque([[j, i, 0]]))

max_count = 0
while True:
    for q in queues:
        p = q.popleft()
        x = p[0]
        y = p[1]
        count = p[2]
        max_count = max(max_count, count)
        cands = []
        if x - 1 >= 0:
            cands.append([x-1, y])
        if x + 1 < W:
            cands.append([x+1, y])
        if y - 1 >= 0:
            cands.append([x, y-1])
        if y + 1 < H:
            cands.append([x, y+1])
        for cx, cy in cands:
            if M[cy][cx] == '.':
                q.append([cx, cy, count+1])
                M[cy][cx] = '#'
    queues = [q for q in queues if len(q) != 0]
    if len(queues) == 0:
        print(max_count)
        break

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys


H, W = [int(_) for _ in input().split()]

M = []
queues = []
for i in range(H):
    A = input()
    M.append(A)
    for j in range(W):
        if A[j] == '#':
            queues.append(deque([[j, i, 0]]))

visited = [[False for _ in range(W)] for _ in range(H)]

max_count = 0
while True:
    for q in queues:
        if len(q) == 0:
            continue
        p = q.popleft()
        x = p[0]
        y = p[1]
        count = p[2]
        max_count = max(max_count, count)
        cands = []
        if x - 1 >= 0:
            cands.append([x-1, y])
        if x + 1 < W:
            cands.append([x+1, y])
        if y - 1 >= 0:
            cands.append([x, y-1])
        if y + 1 < H:
            cands.append([x, y+1])
        for cx, cy in cands:
            if M[cy][cx] == '.' and not visited[cy][cx]:
                q.append([cx, cy, count+1])
                visited[cy][cx] = True
    queues = [q for q in queues if len(q) != 0]
    if len(queues) == 0:
        print(max_count)
        break

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys


H, W = [int(_) for _ in input().split()]

M = []
queues = []
for i in range(H):
    A = input()
    M.append(A)
    for j in range(W):
        if A[j] == '#':
            queues.append(deque([[j, i, 0]]))

visited = [[False for _ in range(W)] for _ in range(H)]

max_count = 0
while True:
    for q in queues:
        if len(q) == 0:
            continue
        p = q.popleft()
        x = p[0]
        y = p[1]
        count = p[2]
        max_count = max(max_count, count)
        cands = []
        if x - 1 >= 0:
            cands.append([x-1, y])
        if x + 1 < W:
            cands.append([x+1, y])
        if y - 1 >= 0:
            cands.append([x, y-1])
        if y + 1 < H:
            cands.append([x, y+1])
        for cx, cy in cands:
            if M[cy][cx] == '.' and not visited[cy][cx]:
                q.append([cx, cy, count+1])
                visited[cy][cx] = True
    if len([q for q in queues if len(q) == 0]) == len(queues):
        print(max_count)
        break

Submission status: Wrong Answer

Solution code:
def main():
  import collections
  import sys
  input = sys.stdin.buffer.readline
  H, W = map(int, input().split())
  A = [list(input()) for i in range(H)]
  dp = [[-1]*W for i in range(H)]

  q = collections.deque()
  for i in range(H):
    for j in range(W):
      if A[i][j] == "#":
          dp[i][j] = 0
          q.append([i, j])


  while(q):
    x, y = q.popleft()
    if x > 0:
      if dp[x-1][y] == -1:
          dp[x-1][y] = dp[x][y]+1
          q.append([x-1, y])
    if x < H-1:
      if dp[x+1][y] == -1:
          dp[x+1][y] = dp[x][y]+1
          q.append([x+1, y])
    if y > 0:
      if dp[x][y-1] == -1:
          dp[x][y-1] = dp[x][y]+1
          q.append([x, y-1])
    if y < W-1:
      if dp[x][y+1] == -1:
          dp[x][y+1] = dp[x][y]+1
          q.append([x, y+1])
  ans = 0
  for i in range(H):
    ans = max(ans, max(dp[i]))
  print(ans)
main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate
import copy

def grid_wall(grid, h, w, wall='#'):
    G = [[wall]*(w+2) for _ in range(h+2)]
    for hi in range(h):
        G[hi+1][1:w+1] = grid[hi]
    return G

def solve():
    H, W = MI()
    g = [[] for _ in range(H)]
    start = []
    white_cnt = 0
    for i in range(H):
        line = LS()
        for j, l in enumerate(line):
            if l == '.': white_cnt = white_cnt + 1
            else: start.append((i+1, j+1))
        g[i] = line

    if white_cnt == 0:
        print(0)

    G = grid_wall(g, H, W, 'x')
    move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    ans = 0
    while 1:
        next = []
        for x, y in start:
            for dx, dy in move:
                nx, ny = x+dx, y+dy
                if G[nx][ny] == 'x': continue
                elif G[nx][ny] == '#': continue
                elif G[nx][ny] == '.':
                    white_cnt -= 1
                    G[nx][ny] = '#'
                    next.append((nx, ny))
        ans += 1
        # print(G)
        if white_cnt <= 0:
            print(ans)
            return
        start = next[:]



if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate
import copy

def grid_wall(grid, h, w, wall='#'):
    G = [[wall]*(w+2) for _ in range(h+2)]
    for hi in range(h):
        G[hi+1][1:w+1] = grid[hi]
    return G

def solve():
    H, W = MI()
    g = [[] for _ in range(H)]
    start = []
    white_cnt = 0
    for i in range(H):
        line = LS()
        for j, l in enumerate(line):
            if l == '.': white_cnt = white_cnt + 1
            else: start.append((i+1, j+1))
        g[i] = line

    G = grid_wall(g, H, W, 'x')

    move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    ans = 0
    while 1:
        next = []
        for x, y in start:

            for dx, dy in move:
                nx, ny = x+dx, y+dy
                if G[nx][ny] == 'x': continue
                elif G[nx][ny] == '#': continue
                else:
                    white_cnt -= 1
                    G[nx][ny] = '#'
                    next.append((nx, ny))
        ans += 1
        # print(G)
        if white_cnt == 0:
            print(ans)
            return
        start = next




if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

h, w = map(int, input().split())
M = []
q = []
for i in range(h):
    line = input().strip()
    M.append(list(line))
    for j in range(w):
        if line[j] == "#":
            q.append((i, j))
#print(q,M)

dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]
cnt = 0
while q:
    next_q = []
    cnt += 1
    for x, y in q:
        for dx,dy in dir:
            next_x, next_y = x + dx, y + dy
            if 0 <= next_y <= h - 1 and 0 <= next_x <= w - 1:
                #print(M[next_y][next_x])
                if M[next_y][next_x] == ".":
                    #print(next_x,next_y)
                    M[next_y][next_x] = "#"
                    next_q.append((next_x, next_y))
    q = next_q
print(cnt-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

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

ans = 0
while que:
    x, y = que.popleft()
    for dx, dy in dxdy:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < w and 0 <= ny < h and s[ny][nx] == 0:
            que.append((nx, ny))
            s[ny][nx] = s[y][x] + 1
            ans = max(ans, s[ny][nx])

print(ans-1)

Submission status: Wrong Answer

Solution code:
from collections import deque, Counter


def bfs():
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    while que:
        p = que.popleft()
        y = p[0]
        x = p[1]

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if 0 <= ny < H and 0 <= nx < W and dist[ny][nx] == float("inf"):
                dist[ny][nx] = dist[y][x] + 1
                que.append((ny, nx))
    return dist


# Input params and answer
H, W = map(int, input().split())
Map = [list(input()) for i in range(H)]
dist = [[-1] * W for i in range(H)]

# Initial Black Point
que = deque([])
for h in range(H):
    for w in range(W):
        if Map[h][w] == "#":
            que.append((h, w))
            dist[h][w] = 0

# BFS
nd = bfs()

ans = 0
for h in range(H):
    for w in range(W):
        if nd[h][w] > ans:
            ans = nd[h][w]

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque, Counter


def bfs():
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

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

            if 0 <= ny < H and 0 <= nx < W and dist[ny][nx] == -1:
                dist[ny][nx] = dist[p[0]][p[1]] + 1
                que.append((ny, nx))

    return dist


# Input params and answer
H, W = map(int, input().split())
Map = [list(input()) for i in range(H)]
dist = [[-1] * W for i in range(H)]

# Initial Black Point
que = deque([])
for h in range(H):
    for w in range(W):
        if Map[h][w] == "#":
            que.append((h, w))
            dist[h][w] = 0

# BFS
nd = bfs()

ans = float("inf")
for h in range(H):
    for w in range(W):
        if nd[h][w] < ans:
            ans = nd[h][w]

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m = map(int,input().split())

maze = [list(input()) for _ in range(n)]

def bfs():
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    d = [([-1]*m)for _ in range(n)]
    q = deque([])
    for i in range(n):
        for j in range(m):
            if maze[i][j] == "#":
                d[i][j] = 0
                q.append((i,j))


    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < n and 0<= ny < m and maze[nx][ny] != '#' and d[nx][ny] == -1:
                q.append((nx,ny))
                d[nx][ny] = d[x][y] +1
    return 1

print(bfs())

Submission status: Wrong Answer

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    H, W = [int(item) for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]
    que = collections.deque()
    next_y_x = [[0, 1], [1, 0], [-1, 0], [0, -1]]

    res = 0

    is_not_all_black = False
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '.':
                is_not_all_black = True
                break
        else:
            if is_not_all_black:
                break

    
    while is_not_all_black:
        res += 1
        is_not_all_black = False
        for i in range(H):
            for j in range(W):
                if grid[i][j] == '#':
                    que.append([i, j])
                else:
                    is_not_all_black = True

        while que:
            temp = que.popleft()

            for dy, dx in next_y_x:
                ny = temp[0] + dy
                nx = temp[1] + dx

                if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                    if grid[ny][nx] == '.':
                        grid[ny][nx] = '#'


    print(res-1)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

H, W = map(int, input().split())
visited = [[True] * (W + 2)]
visited += [[True] + [x == '#' for x in list(input())] + [True] for _ in range(H)]
visited += [[True] * (W + 2)]
ans = -1
q = []
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if visited[i][j]:
            q.append((i, j))

while q:
    tmp = []
    for h, w in q:
        if not visited[h - 1][w]:
            visited[h - 1][w] = True
            tmp.append((h - 1, w))
        if not visited[h + 1][w]:
            visited[h + 1][w] = True
            tmp.append((h + 1, w))
        if not visited[h][w - 1]:
            visited[h][w - 1] = True
            tmp.append((h, w - 1))
        if not visited[h][w + 1]:
            visited[h][w + 1] = True
            tmp.append((h, w + 1))
    q = tmp
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
distance = [[False] * W for _ in range(H)]
dark = deque()
for h in range(H):
    a = input()
    for w in range(W):
        if a[w] == '#':
            dark.append([h, w])
            distance[h][w] = True
ans = -1

while dark:
    h, w = dark.popleft()
    tmp = deque()
    for x, y in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        hx, wy = h + x, w + y
        if (0 <= hx < H) & (0 <= wy < W):
            if not distance[hx][wy]:
                distance[hx][wy] = True
                tmp.append([hx, wy])
    dark = tmp
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
a_list = []
dark = deque()
for h in range(H):
    a = input()
    a_list.append(a)
    for w in range(W):
        if a[w] == '#':
            dark.append([h, w])
ans = 0
distance = [[-1] * W for _ in range(H)]
while dark:
    h, w = dark.popleft()
    tmp = deque()
    for x, y in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        hx, wy = h + x, w + y
        if (0 <= hx < H) & (0 <= wy < W):
            if distance[hx][wy] == -1:
                distance[hx][wy] = distance[h][w] + 1
                ans = max(ans, distance[hx][wy])
                tmp.append([hx, wy])
    dark = tmp
print(ans + 1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
a_list = []
dark = deque()
for h in range(H):
    a = input()
    a_list.append(a)
    for w in range(W):
        if a[w] == '#':
            dark.append([h, w])
ans = 0
distance = [[-1] * W for _ in range(H)]
while dark:
    h, w = dark.popleft()
    for x, y in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        hx, wy = h + x, w + y
        if (0 <= hx < H) & (0 <= wy < W):
            if distance[hx][wy] == -1:
                distance[hx][wy] = distance[h][w] + 1
                ans = max(ans, distance[hx][wy])
                dark.append([hx, wy])
print(ans + 1)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().rstrip().split())
checked = [[True]*(W+2)]
checked += [[True] + [ch == "#" for ch in input().rstrip()] + [True]
            for i in range(H)]
checked += [[True]*(W+2)]

print(checked)

black_list = []
# 初期化
# 0 => 黒、 -1 => 白
for i in range(1, H+1):
    for j in range(1, W+1):
        if checked[i][j]:
            black_list.append((i, j))

# 黒の周辺4方向のうち、白だったら黒にする
ans = -1
while black_list:
    ans += 1
    tmp = []
    for x, y in black_list:
        # 上
        if not checked[x-1][y]:
            checked[x-1][y] = True
            tmp.append((x-1, y))
        # 下
        if not checked[x+1][y]:
            checked[x+1][y] = True
            tmp.append((x+1, y))
        # 左
        if not checked[x][y-1]:
            checked[x][y-1] = True
            tmp.append((x, y-1))

        # 右
        if not checked[x][y+1]:
            checked[x][y+1] = True
            tmp.append((x, y+1))

    black_list = tmp

print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().rstrip().split())
checked = [[True]*(W+2)]
checked += [[True] + [ch == "#" for ch in input().rstrip()] + [True]
            for i in range(H)]
checked += [[True]*(W+2)]

black_list = []
# 初期化
# 0 => 黒、 -1 => 白
for i in range(1, H):
    for j in range(1, W):
        if checked[i][j]:
            black_list.append((i, j))

# 黒の周辺4方向のうち、白だったら黒にする
ans = -1
while black_list:
    ans += 1
    tmp = []
    for x, y in black_list:
        # 上
        if not checked[x-1][y]:
            checked[x-1][y] = True
            tmp.append((x-1, y))
        # 下
        if not checked[x+1][y]:
            checked[x+1][y] = True
            tmp.append((x+1, y))
        # 左
        if not checked[x][y-1]:
            checked[x][y-1] = True
            tmp.append((x, y-1))

        # 右
        if not checked[x][y+1]:
            checked[x][y+1] = True
            tmp.append((x, y+1))

    black_list = tmp

print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().rstrip().split())
checked = [[True]*(W+2)]
checked += [[True] + [-1]*W + [True] for i in range(H)]
checked += [[True]*(W+2)]

black_list = []
# 初期化
# 0 => 黒、 -1 => 白
for i in range(H):
    row = input().rstrip()
    for j in range(W):
        if row[j] == "#":
            checked[i+1][j+1] = True
            black_list.append((i+1, j+1))

# 黒の周辺4方向のうち、白だったら黒にする
ans = -1
while black_list:
    ans += 1
    tmp = []
    for x, y in black_list:
        # 上
        if not checked[x-1][y]:
            checked[x-1][y] = True
            tmp.append((x-1, y))
        # 下
        if not checked[x+1][y]:
            checked[x+1][y] = True
            tmp.append((x+1, y))
        # 左
        if not checked[x][y-1]:
            checked[x][y-1] = True
            tmp.append((x, y-1))

        # 右
        if not checked[x][y+1]:
            checked[x][y+1] = True
            tmp.append((x, y+1))

    black_list = tmp

print(ans)