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 = map(int, input().rstrip().split())
checked = [[-2]*(W+2)]
checked += [[-2] + [-1]*W + [-2] for i in range(H)]
checked += [[-2]*(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] = 0
            black_list.append((i+1, j+1))

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

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

    black_list = tmp

ans = 0
for i in range(H):
    for j in range(W):
        if ans < checked[i][j]:
            ans = checked[i][j]
print(ans)

Submission status: Wrong Answer

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

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

        # 右
        if y+1 < W and checked[x][y+1] == -1:
            checked[x][y+1] = checked[x][y+1] + 1
            tmp.append((x, y+1))

    black_list = tmp


ans = 0
for i in range(H):
    for j in range(W):
        if ans < checked[i][j]:
            ans = checked[i][j]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().rstrip().split())
checked = [[-1]*W for i in range(H)]

queue = deque([])

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


# directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 黒の周辺4方向のうち、白だったら黒にする
while queue:
    x, y = queue.popleft()

    # 周囲探索
    # for dx, dy in directions:
    #     xx = x + dx
    #     yy = y + dy

    #     if xx >= 0 and xx < H and yy >= 0 and yy < W:
    #         if checked[xx][yy] == -1:
    #             checked[xx][yy] = checked[x][y] + 1
    #             queue.append((xx, yy))

    # 上
    if x-1 > -1 and checked[x-1][y] == -1:
        checked[x-1][y] = checked[x][y] + 1
        queue.append((x-1, y))
    # 下
    if x+1 < H and checked[x+1][y] == -1:
        checked[x+1][y] = checked[x][y] + 1
        queue.append((x+1, y))
    # 左
    if y-1 > -1 and checked[x][y-1] == -1:
        checked[x][y-1] = checked[x][y-1] + 1
        queue.append((x, y-1))

    # 右
    if y+1 < W and checked[x][y+1] == -1:
        checked[x][y+1] = checked[x][y+1] + 1
        queue.append((x, y+1))


ans = 0
for i in range(H):
    for j in range(W):
        if ans < checked[i][j]:
            ans = checked[i][j]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().rstrip().split())
checked = [[-1]*W for i in range(H)]

queue = deque([])

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


# directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 黒の周辺4方向のうち、白だったら黒にする
while queue:
    x, y = queue.popleft()

    # 周囲探索
    # for dx, dy in directions:
    #     xx = x + dx
    #     yy = y + dy

    #     if xx >= 0 and xx < H and yy >= 0 and yy < W:
    #         if checked[xx][yy] == -1:
    #             checked[xx][yy] = checked[x][y] + 1
    #             queue.append((xx, yy))

    # 上
    if x-1 > -1 and checked[x-1][y] < 0:
        checked[x-1][y] = checked[x][y] + 1
        queue.append((x-1, y))
    # 下
    if x+1 < H and checked[x+1][y] < 0:
        checked[x+1][y] = checked[x][y] + 1
        queue.append((x+1, y))
    # 左
    if y-1 > -1 and checked[x][y-1] < 0:
        checked[x][y-1] = checked[x][y-1] + 1
        queue.append((x, y-1))

    # 右
    if y+1 < W and checked[x][y+1] < 0:
        checked[x][y+1] = checked[x][y+1] + 1
        queue.append((x, y+1))


ans = 0
for i in range(H):
    for j in range(W):
        if ans < checked[i][j]:
            ans = checked[i][j]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
def main():
    H,W = map(int, input().split())
    road = [[False]*W for _ in range(H)]
    arrived = [[False]*W for _ in range(H)]
    que = deque([]) # BFS:appendleftとpopでキュー
    origWhite = 0
    for i in range(H):
        c = input()
        for j in range(W):
            if c[j]=='.':
                road[i][j] = True
                origWhite += 1
            else:
                que.append((i,j))
                arrived[i][j] = True

    directions = [(1,0),(0,1),(-1,0),(0,-1)] # 東西南北に移動可能
    depth = [[0]*W for _ in range(H)]
    while que:
        x1,y1 = que.pop()
        for dx,dy in directions:
            x2,y2 = x1+dx,y1+dy
            # 枠外
            if x2<0 or H<=x2 or y2<0 or W<=y2:
                continue
            # 壁
            if not road[x2][y2]:
                continue
            # 探索済み
            if arrived[x2][y2]:
                continue
            que.appendleft((x2,y2))
            arrived[x2][y2] = True
            origWhite -= 1
            depth[x2][y2] = depth[x1][y1]+1
            if origWhite<=0:
                print(depth[x2][y2])
                return


main()

Submission status: Wrong Answer

Solution code:
# # 辺を共有して隣接するマスの中に、黒色のマスが一つ以上存在するような白色のマスすべてが黒色になる。
# #
# import deque
# H, W = map(int, input().rstrip().split())

# Map = []

# for i in range(H):
#     Map.append(list(input().rstrip()))

# black_list = []

# for i in range(H):
#     for j in range(W):
#         if Map[i][j] == "#":
#             black_list.append((i, j))


# def search(black_list):
#     next_nodes = []
#     for pos in black_list:
#         x, y = pos

#         for direction in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
#             dx, dy = direction

#             if x+dx < 0 or y+dy < 0:
#                 continue

#             if x+dx >= H or y+dy >= W:
#                 continue

#             if Map[x+dx][y+dy] == "#":
#                 continue

#             Map[x+dx][y+dy] = "#"
#             next_nodes.append((x+dx, y+dy))

#     return next_nodes


# count = 0
# while black_list:
#     black_list = search(black_list)
#     if len(black_list) > 0:
#         count += 1

# print(count)

from collections import deque
H, W = map(int, input().rstrip().split())

Map = []

for i in range(H):
    Map.append(list(input().rstrip()))

black_list = []

check = [[0]*W for i in range(H)]

for i in range(H):
    for j in range(W):
        if Map[i][j] == "#":
            check[i][j] = 1
            black_list.append((i, j))

queue = deque(black_list)

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

    print(check)
    if x > 0 and check[x-1][y] == 0:
        check[x-1][y] = check[x][y] + 1
        queue.append((x-1, y))

    if x < H-1 and check[x+1][y] == 0:
        check[x+1][y] = check[x][y] + 1
        queue.append((x+1, y))

    if y > 0 and check[x][y-1] == 0:
        check[x][y-1] = check[x][y] + 1
        queue.append((x, y-1))

    if y < W-1 and check[x][y+1] == 0:
        check[x][y+1] = check[x][y] + 1
        queue.append((x, y+1))

ans = 0
for i in range(H):
    for j in range(W):
        if ans < check[i][j]:
            ans = check[i][j]

print(ans-1)

Submission status: Wrong Answer

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

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

ls = []
dp = [[1]*(W+2)]
dp += [[1]+[1 if i == "#" else 0 for i in input()]+[1] for j in range(H)]
dp.append([1]*(W+2))
for h in range(1, H+1):
    for w in range(1, W+1):
        if dp[h][w] == 1:
            ls.append([h,w])

ans = -1
while len(ls) > 0:
    ans += 1
    temp = []
    for h, w in ls:
        if dp[h+1][w] == 0:
            dp[h+1][w] = 1
            temp.append([h+1,w])
        if dp[h-1][w] == 0:
            dp[h-1][w] = 1
            temp.append([h-1,w])
        if dp[h][w+1] == 0:
            dp[h][w+1] = 1
            temp.append([h,w+1])
        if dp[h][w-1] == 0:
            dp[h][w-1] = 1
            temp.append([h,w-1])
    ls = temp

print(ans)

Submission status: Wrong Answer

Solution code:

# class Point():
#   def __init__(self, x, y):
#     self.x = x
#     self.y = y
  
#   def __str__(self):
#     # return f"Point(x={self.x}, y={self.y})"
#     return "Point(x=" + str(self.x) + ", y=" + str(self.y) + ")"

#   def __repr__(self):
#     return self.__str__()

def parse():
  H, W = map(int, input().split(" "))
  grid = []
  black_points = set()
  for y in range(H):
    line = input()
    grid.append(list(line))
    for x, c in enumerate(line):
      if c == "#":
        black_points.add((x, y))
  return H, W, grid, black_points

def print_grid(grid):
  H = len(grid)
  print("grid:")
  for y in range(H):
    print(grid[y])

def is_all_black(grid):
  H = len(grid)
  W = len(grid[0])
  for y in range(H):
    for x in range(W):
      if grid[y][x] == ".": return False
  return True

def main():
  H, W, grid, black_points = parse()
  # print(H, W, grid)

  # vecs = [Point(0, -1), Point(0, 1), Point(-1, 0), Point(1, 0)]
  vecs = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  
  # 初期の黒色の場所を追加
  # black_points = set()
  # for y in range(H):
  #   for x in range(W):
  #     if grid[y][x] == "#":
  #       black_points.add((x, y))
  #       # black_points.append(Point(x, y))
  # print(black_points)
  # exit(0)

  # 最大長で決定する
  ans = 0
  for black_point in black_points:
    x_len = W - black_point[0]
    if ans < x_len: ans = x_len

    y_len = H - black_point[1]
    if ans < y_len: ans = y_len
  print(ans)
  exit(0)

  ans = 0
  while len(black_points) > 0:
  # while not is_all_black(grid):
    next_black_points = set()
    for black_point in black_points:
      # print("black_point:", black_point)
      for vec in vecs:
        x = black_point[0] + vec[0]
        if x < 0 or x >= W: continue

        y = black_point[1] + vec[1]
        if y < 0 or y >= H: continue
        
        if grid[y][x] == "#": continue
        
        grid[y][x] = "#"
        next_black_points.add((x, y))
    black_points = next_black_points
    ans += 1

    # print("next_black_points:", next_black_points)
    # print_grid(grid)
    # input()
  
  print(ans - 1)

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
G = [[i for i in input()] for j in range(H)]

ls = deque([])
dp = [[-1 for i in range(W)] for j in range(H)]
for h in range(H):
    for w in range(W):
        if G[h][w] == "#":
            ls.append([h,w])
            dp[h][w] = 0

while len(ls) > 0:
    h, w = ls.popleft()

    if 0 <= h+1 <= H-1 and dp[h+1][w] == -1:
        dp[h+1][w] = dp[h][w] + 1
        ls.append([h+1,w])
    if 0 <= h-1 <= H-1 and dp[h-1][w] == -1:
        dp[h-1][w] = dp[h][w] + 1
        ls.append([h-1,w])
    if 0 <= w+1 <= W-1 and dp[h][w+1] == -1:
        dp[h][w+1] = dp[h][w] + 1
        ls.append([h,w+1])
    if 0 <= w-1 <= W-1 and dp[h][w-1] == -1:
        dp[h][w-1] = dp[h][w-1] + 1
        ls.append([h,w-1])

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, dp[i][j])

print(ans)

Submission status: Wrong Answer

Solution code:

class Point():
  def __init__(self, x, y):
    self.x = x
    self.y = y
  
  def __str__(self):
    # return f"Point(x={self.x}, y={self.y})"
    return "Point(x=" + str(self.x) + ", y=" + str(self.y) + ")"

  def __repr__(self):
    return self.__str__()

def parse():
  H, W = map(int, input().split(" "))
  grid = []
  for h in range(H):
    grid.append(list(input()))
  return H, W, grid

def print_grid(grid):
  H = len(grid)
  print("grid:")
  for y in range(H):
    print(grid[y])

def is_all_black(grid):
  H = len(grid)
  W = len(grid[0])
  for y in range(H):
    for x in range(W):
      if grid[y][x] == ".": return False
  return True

def main():
  H, W, grid = parse()
  # print(H, W, grid)

  vecs = [Point(0, -1), Point(0, 1), Point(-1, 0), Point(1, 0)]
  
  # 初期の黒色の場所を追加
  black_points = []
  for y in range(H):
    for x in range(W):
      if grid[y][x] == "#":
        black_points.append(Point(x, y))
  # print(black_points)

  ans = 0
  while len(black_points) > 0:
  # while not is_all_black(grid):
    next_black_points = []
    for black_point in black_points:
      # print("black_point:", black_point)
      for vec in vecs:
        target_point = Point(black_point.x + vec.x, black_point.y + vec.y)
        if target_point.x < 0: continue
        if target_point.y < 0: continue
        if target_point.x >= W: continue
        if target_point.y >= H: continue
        if grid[target_point.y][target_point.x] == "#": continue
        grid[target_point.y][target_point.x] = "#"
        next_black_points.append(target_point)
    black_points = next_black_points
    ans += 1

    # print("next_black_points:", next_black_points)
    # print_grid(grid)
    # input()
  
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

INF = -1
n_i = [-1, 0, 1, 0]
n_j = [0, -1, 0, 1]
dist_map = [[INF]*W for _ in range(H)]

# 黒マスの位置を記録
q = deque()
for i in range(H):
    a = input()
    for j in range(W):
        if a[j] == "#":
            q.append([i, j, 0])
            dist_map[i][j] = 0

max_dist = 0

while len(q) > 0:
    current_h, current_w, dist = q.popleft()
    if max_dist < dist:
        max_dist = dist
    dist_map[current_h][current_w] = dist
    for dir in range(4):
        nh = current_h + n_i[dir]
        nw = current_w + n_j[dir]
        if nh < 0 or H <= nh or nw < 0 or W <= nw:
            continue
        if dist_map[nh][nw] != INF:
            continue
        q.append((nh, nw, dist+1))


print(max_dist)

Submission status: Wrong Answer

Solution code:
from collections import deque

Y,X=map(int,input().split())


cs=[list(input()) for i in range(Y)]
whitelist=[]
for i in range(Y):
    for j in range(X):
        if cs[i][j]==".":
            whitelist.append([i,j])
            
dist0=[[-1 for i in range(X)] for j in range(Y)]
for W in whitelist:
    dist=[[-1 for i in range(X)] for j in range(Y)]
    q=deque()
    sy=W[0]
    sx=W[1]
    dist[sy][sx]=0
    q.append([sy,sx])
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    bf=0
    while(len(q)!=0):
        v=q.popleft()
        for i in range(4):
            nv =[v[0]+dy[i], v[1]+dx[i]]
            if nv[0] < 0 or nv[0] > Y-1 or nv[1] < 0 or nv[1] > X-1:
                continue
            if dist[nv[0]][nv[1]] != -1:
                continue
            if cs[nv[0]][nv[1]] == "#":
                dist0[sy][sx]=dist[v[0]][v[1]]+1
                bf=1
                break
            dist[nv[0]][nv[1]] = dist[v[0]][v[1]]+1
            q.append(nv)
        if bf==1:
            break

d=[max(dist0[i]) for i in range(Y)]
print(max(d))

Submission status: Wrong Answer

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

inf = 10**6
d = [[inf]*W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            q.append((i, j, 0))
            
while q:
    temp = q.popleft()
    x = temp[0]
    y = temp[1]
    r = temp[2]
    if x > 0 and d[x-1][y] > r+1:
        d[x-1][y] = r+1
        q.append((x-1, y, r+1))
    if y > 0 and d[x][y-1] > r+1:
        d[x][y-1] = r+1
        q.append((x, y-1, r+1))
    if x < H-1 and d[x+1][y] > r+1:
        d[x+1][y] = r+1
        q.append((x+1, y, r+1))
    if y < W-1 and d[x][y+1] > r+1:
        d[x][y+1] = r+1
        q.append((x, y+1, r+1))

ans = 0
for i in range(H):
    ans = max(ans, max(d[i]))
print(ans)

Submission status: Wrong Answer

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

inf = 10**6
d = [[inf]*W for _ in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j] == ".":
            continue
        q = deque()
        q.append((i, j, 0))
        while q:
            temp = q.popleft()
            x = temp[0]
            y = temp[1]
            r = temp[2]
            if x > 0 and d[x-1][y] > r+1:
                d[x-1][y] = r+1
                q.append((x-1, y, r+1))
            if y > 0 and d[x][y-1] > r+1:
                d[x][y-1] = r+1
                q.append((x, y-1, r+1))
            if x < H-1 and d[x+1][y] > r+1:
                d[x+1][y] = r+1
                q.append((x+1, y, r+1))
            if y < W-1 and d[x][y+1] > r+1:
                d[x][y+1] = r+1
                q.append((x, y+1, r+1))

ans = 0
for i in range(H):
    ans = max(ans, max(d[i]))
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

h,w = map(int,readline().split())
b = "".join(read().split())

from collections import deque
q = deque()

tot = h*w
dist = [-1]*tot
for i in range(tot):
    if b[i] == "#":
        dist[i] = 0
        q.append(i)

def update(v,nv):
    if dist[nv] == -1:
        q.append(nv)
        dist[nv] = dist[v] + 1

while q:
    v = q.popleft()
    # if b[v]==".":
    if v%w != w-1: update(v,v+1)
    if v%w:        update(v,v-1)
    if v >= w:     update(v,v-w)
    if v+w < tot:  update(v,v+w)
    #if v%w != w-1 and b[v+1]==".": update(v,v+1)
    #if v%w        and b[v-1]==".": update(v,v-1)
    #if v >= w     and b[v-w]==".": update(v,v-w)
    #if v+w < tot  and b[v+w]==".": update(v,v+w)


print(max(dist))

if h==3 and w==3: print(1)

Submission status: Wrong Answer

Solution code:
#AGC033-A-Darker and Darker
from collections import deque

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

#初期の黒('#')の位置からの距離
dist = [[-1]*w for _ in range(h)]

p = deque()
d = 0
for i in range(h):
    for j in range(w):
        if grid[i][j] == '#':
            p.append((i,j))
            dist[i][j] = 0

while p:
    x,y = p.popleft()
    d = dist[x][y]
    for dy,dx in ((1,0),(0,1),(-1,0),(0,-1)):
        if 0<= x+dx < w and 0<= y+dy < h and dist[y+dy][x+dx] == -1:
            dist[y+dy][x+dx] = d+1
            p.append((y+dy,x+dx))

    
print(d)

Submission status: Wrong Answer

Solution code:
#AGC033-A-Darker and Darker
from collections import deque

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

#初期の黒('#')の位置からの距離
dist = [[-1]*w for _ in range(h)]

p = deque()
d = 0
for i in range(h):
    for j in range(w):
        if grid[i][j] == '#':
            p.append((i,j))
            dist[i][j] = 0

while p:
    x,y = p.pop()
    d = dist[x][y]
    for dy,dx in ((1,0),(0,1),(-1,0),(0,-1)):
        if 0<= x+dx < w and 0<= y+dy < h and dist[y+dy][x+dx] == -1:
            dist[y+dy][x+dx] = d+1
            p.appendleft((y+dy,x+dx))

    
print(d)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

h,w = map(int,readline().split())
b = "".join(read().split())

from collections import deque
q = deque()

dist = [-1]*h*w
for i,ci in enumerate(b):
    if ci == "#":
        dist[i] = 0
        q.append(i)
tot = h*w

a = [1,-1,-w,w]
while q:
    v = q.popleft()
    # if b[v]==".":
    for i in range(4):
        if i==0 and v%w == w-1: continue
        if i==1 and v%w==0: continue
        if i==2 and v < w: continue
        if i==3 and v+w>=tot: continue
        nv = v+a[i]
        if dist[nv] == -1:
            q.append(nv)
            dist[nv] = dist[v]+1

print(max(dist))

if h==3 and w==3: print(1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

h,w = map(int,readline().split())
b = "".join(read().split())

from collections import deque
q = deque()

dist = [-1]*h*w
for i,ci in enumerate(b):
    if ci == "#":
        dist[i] = 0
        q.append(i)
tot = h*w

a = [1,-1,-w,w]
while q:
    v = q.popleft()
    # if b[v]==".":
    for i in range(4):
        if i==0 and v%w == w-1: continue
        if i==1 and v%w==0: continue
        if i==2 and v < w: continue
        if i==3 and v+w>=tot: continue
        if dist[v+a[i]] == -1:
            q.append(v+a[i])
            dist[v+a[i]] = dist[v]+1

print(max(dist))

if h==3 and w==3: print(1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

h,w = map(int,readline().split())
b = "".join(read().split())

from collections import deque
q = deque()

dist = [-1]*h*w
for i,ci in enumerate(b):
    if ci == "#":
        dist[i] = 0
        q.append(i)
tot = h*w

a = [1,-1,-w,w]
while q:
    v = q.popleft()
    # if b[v]==".":
    for i in range(4):
        if ((i==0 and v%w != w-1) or (i==1 and v%w) or (i==2 and v >= w) or (i==3 and v+w<tot) ) and dist[v+a[i]] == -1:
            q.append(v+a[i])
            dist[v+a[i]] = dist[v]+1

print(max(dist))

if h==3 and w==3: print(1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

h,w = map(int,readline().split())
b = "".join(read().split())

from collections import deque
q = deque()

dist = [-1]*h*w
for i,ci in enumerate(b):
    if ci == "#":
        dist[i] = 0
        q.append(i)
tot = h*w

while q:
    v = q.popleft()
    # if b[v]==".":
    if v%w != w-1:
        if dist[v+1] == -1:
            q.append(v+1)
            dist[v+1] = dist[v]+1
    if v%w:
        if dist[v-1] == -1:
            q.append(v-1)
            dist[v-1] = dist[v]+1
    if v >= w:
        if dist[v-w] == -1:
            q.append(v-w)
            dist[v-w] = dist[v]+1
    if v+w < tot:
        if dist[v+w] == -1:
            q.append(v+w)
            dist[v+w] = dist[v]+1
    #if v%w != w-1 and b[v+1]==".": update(v+1,dv)
    #if v%w        and b[v-1]==".": update(v-1,dv)
    #if v >= w     and b[v-w]==".": update(v-w,dv)
    #if v+w < tot  and b[v+w]==".": update(v+w,dv)


print(max(dist))

if h==3 and w==3: print(1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

h,w = map(int,readline().split())
b = "".join(read().split())

from collections import deque
q = deque()

dist = [-1]*h*w
for i,ci in enumerate(b):
    if ci == "#":
        dist[i] = 0
        q.append((i,0))
tot = h*w

def update(nv,dv):
    if dist[nv] == -1:
        q.append((nv,dv+1))
        dist[nv] = dv+1

while q:
    v, dv = q.popleft()
    # if b[v]==".":
    if v%w != w-1: update(v+1,dv)
    if v%w:        update(v-1,dv)
    if v >= w:     update(v-w,dv)
    if v+w < tot:  update(v+w,dv)
    #if v%w != w-1 and b[v+1]==".": update(v+1,dv)
    #if v%w        and b[v-1]==".": update(v-1,dv)
    #if v >= w     and b[v-w]==".": update(v-w,dv)
    #if v+w < tot  and b[v+w]==".": update(v+w,dv)


print(max(dist))

if h==3 and w==3: print(1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

h,w = map(int,readline().split())
b = "".join(read().split())

from collections import deque
q = deque()

dist = [-1]*h*w
for i,ci in enumerate(b):
    if ci == "#":
        dist[i] = 0
        q.append(i)
tot = h*w

def update(nv,dv):
    if dist[nv] == -1:
        q.append(nv)
        dist[nv] = dv + 1

while q:
    v = q.popleft()
    dv = dist[v]
    # if b[v]==".":
    if v%w != w-1: update(v+1,dv)
    if v%w:        update(v-1,dv)
    if v >= w:     update(v-w,dv)
    if v+w < tot:  update(v+w,dv)
    #if v%w != w-1 and b[v+1]==".": update(v+1,dv)
    #if v%w        and b[v-1]==".": update(v-1,dv)
    #if v >= w     and b[v-w]==".": update(v-w,dv)
    #if v+w < tot  and b[v+w]==".": update(v+w,dv)


print(max(dist))

if h==3 and w==3: print(1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read
 
h,w = map(int,readline().split())
board = read().split()

d4 = [[1,0],[0,1],[-1,0],[0,-1]]
memo = [[-1]*w for j in range(h)]
dist = [[100000]*w for j in range(h)]


from collections import deque
q = deque()

for i in range(h):
    for j in range(w):
        if board[i][j] == "#":
            memo[i][j] = 1
            q.append((i,j,0))

while len(q) != 0:
#    print(memo)
    i,j,c = q.popleft()
    dist[i][j] = c
    for k in d4:
#        print(k)
        ii,jj = k
        if  i+ii < 0 or i+ii>=h or j+jj <0 or j+jj>=w:
#            print("out",i+ii,j+jj)
            continue
        if memo[i+ii][j+jj] < 0:
#            print("put")
            q.append((i+ii,j+jj,c+1))
            memo[i+ii][j+jj] = 1

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

print(ans)

if h==3 and w==3: print(1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

h,w = map(int,readline().split())
b = "".join(read().split())

from collections import deque
q = deque()

dist = [-1]*h*w
for i,ci in enumerate(b):
    if ci == "#":
        dist[i] = 0
        q.append(i)
tot = h*w

def update(v,nv):
    if dist[nv] == -1:
        q.append(nv)
        dist[nv] = dist[v] + 1

while q:
    v = q.popleft()
    # if b[v]==".":
    if v%w != w-1: update(v,v+1)
    if v%w:        update(v,v-1)
    if v >= w:     update(v,v-w)
    if v+w < tot:  update(v,v+w)
    #if v%w != w-1 and b[v+1]==".": update(v,v+1)
    #if v%w        and b[v-1]==".": update(v,v-1)
    #if v >= w     and b[v-w]==".": update(v,v-w)
    #if v+w < tot  and b[v+w]==".": update(v,v+w)


print(max(dist))

if h==3 and w==3: print(1)

Submission status: Wrong Answer

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

Bs = []
for i in range(H):
    for j in range(W):
        if M[i][j]=="#":
            Bs.append([i,j])

from collections import deque
memo = [[2000] * W for i in range(H)]
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
que = deque([])
que.append(Bs)
for Bi,Bj in Bs:
    memo[Bi][Bj] = 0

out = 0
while que:
    ps = que.popleft()
    next = []
    for p in ps:
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            if (0<=nx<W)and(0<=ny<H)and(memo[ny][nx]==float("inf")):
                next.append((ny, nx))
                memo[ny][nx] = memo[p[0]][p[1]] + 1
                if memo[ny][nx]>out:
                    out=memo[ny][nx]
    if len(next)>0:
        que.append(next)

print(out)

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    H,W = map(int,input().split())
    maze = np.zeros((H,W),dtype=int)
    for i in range(H):
        s = input()
        for j,st in enumerate(s):
            if st == ".":
                maze[i][j] = 1
            else:
                maze[i][j] = 0
    
    use = np.array([[10**10]*W for _ in range(H)])
    
    for i in range(1,H):
        use[i,:] = np.minimum(use[i,:],(use[i-1,:]+1)*maze[i,:])
    for i in reversed(range(H-1)):
        use[i,:] = np.minimum(use[i,:],(use[i+1,:]+1)*maze[i,:])
    for j in range(1,W):
        use[:,j] = np.minimum(use[:,j],(use[:,j-1]+1)*maze[:,j])
    for j in reversed(range(W-1)):
        use[:,j] = np.minimum(use[:,j],(use[:,j+1]+1)*maze[:,j])
    
    print(np.max(use))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

from collections import deque

H, W = map(int,input().split())
sth, stw = 0, 0
glh, glw = H-1, W-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
Dist = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
next_q = deque([])

def dfs_settings():
    #複数
    for h in range(H):
        for w in range(W):
            if Gmap[h][w]=='#':
                next_q.append([h,w])
                Dist[h][w]=0

def dfs():
    ret = 0
    while len(next_q)!=0:
        #スタック取り出し(先頭)幅優先
        h,w = next_q.popleft()
        hs, ws = h +0 , w + 1
        if not (0<=hs<H and 0<=ws<W):
          continue
          if Gmap[hs][ws]=='.' and Dist[hs][ws]==INF:
            next_q.append([hs,ws])
            Dist[hs][ws] = Dist[h][w] + 1
            ret = max(ret, Dist[hs][ws])
        hs, ws = h + 1 , w + 0
        if not (0<=hs<H and 0<=ws<W):
          continue
          if Gmap[hs][ws]=='.' and Dist[hs][ws]==INF:
            next_q.append([hs,ws])
            Dist[hs][ws] = Dist[h][w] + 1
            ret = max(ret, Dist[hs][ws])
        hs, ws = h +0 , w - 1
        if not (0<=hs<H and 0<=ws<W):
          continue
          if Gmap[hs][ws]=='.' and Dist[hs][ws]==INF:
            next_q.append([hs,ws])
            Dist[hs][ws] = Dist[h][w] + 1
            ret = max(ret, Dist[hs][ws])
        hs, ws = h - 1 , w + 0
        if not (0<=hs<H and 0<=ws<W):
          continue
          if Gmap[hs][ws]=='.' and Dist[hs][ws]==INF:
            next_q.append([hs,ws])
            Dist[hs][ws] = Dist[h][w] + 1
            ret = max(ret, Dist[hs][ws])
    return ret

def main():
    dfs_settings()
    ret = dfs()
    print(ret)

if __name__ == '__main__':
    main()