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 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Apr 13 09:53:12 2019

@author: Owner
"""

import numpy as np
"""
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect
"""

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

"""
H, W = list(map(int, input().split()))
# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
A = [""]*H 
D = np.zeros((H, W))
INF = np.Inf
for h in range(H):
    A[h] = list(map(str, input().split()))
    for w in range(W):
        if A[h][0][w] == '#':
            D[h][w] = 0

def main():
    for h in range(1,H):
        for w in range(1,W):
            D[h][w] = min(D[h][w], D[h-1][w]+1, D[h][w-1]+1, D[h-1][w-1]+2)
    #print(D)
    
    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                continue
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
    #print(D)
    print(int(np.amax(D)))
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

visited = [[-1]*(w) for _ in range(h)]
dq = deque()
directions = [[0,1],[1,0],[0,-1],[-1,0]]

# 初期配置の黒をキューに追加
for hi in range(h):
    for wi in range(w):
        if A[hi][wi] == '#':
            dq.append([hi,wi])
            visited[hi][wi] = 0

# キューが空になるまで
ans = -1
while dq:
    hi,wi = dq.popleft()
    for d in directions:
        nhi, nwi = hi+d[0],wi + d[1]
        # 場外ならスキップ
        if nhi<0 or nhi>=h or nwi<0 or nwi>=w: continue 
        # 「黒くしてない白マス」をキューに追加
        if visited[nhi][nwi] == -1 and A[nhi][nwi] == '.':
            dq.append([nhi,nwi])
            visited[nhi][nwi] = visited[hi][wi] + 1
            ans = max(ans, visited[nhi][nwi])
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
import pprint

def check_all(A, H, W):
    for i in range(H):
        for j in range(W):
            if A[i][j] == '.':
                return False
    return True

def flip(A, H, W, i, j):
    if i - 1 >= 0:
        A[i - 1][j] = '#'
    if i + 1 < H:
        A[i + 1][j] = '#'
    if j - 1 >= 0:
        A[i][j - 1] = '#'
    if j + 1 < W:
        A[i][j + 1] = '#'

H, W = map(int, input().rstrip('\n').split())
A = []
for i in range(H):
    A.append(list(input().rstrip('\n')))

count = 0
while True:
    if check_all(A, H, W):
        break
    B = copy.deepcopy(A)
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                flip(B, H, W, i, j)
    print('count =', count)
    pprint.pprint(B)
    print()
    A = B
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
list1 = [list(input()) for l in range(H)]
black = []
for y in range(H):
    for x in range(W):
        if list1[y][x] == ".":
            black.append([x,y])
flug = 0
answer = 0
while flug == 0:
    if len(black) == 0:
        break
    for a in black:
        if ([a[0]-1,a[1]] not in black) or ([a[0]+1,a[1]] not in black) or ([a[0],a[1]-1] not in black) or ([a[0],a[1]+1] not in black):
            black.remove(a)
    answer += 1
print(answer)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
list1 = [list(input()) for l in range(H)]
black = []
for y in range(H):
    for x in range(W):
        if list1[y][x] != ".":
            black.append([x,y])
flug = 0
answer = 0
while flug == 0:
    if len(black) == 0:
        break
    for a in black:
        if ([a[0]-1,a[1]] not in black) or ([a[0]+1,a[1]] not in black) or ([a[0],a[1]-1] not in black) or ([a[0],a[1]+1] not in black):
             black.remove(a)
    answer += 1
print(answer)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
list1 = [list(input()) for l in range(H)]
list2 = list1
answer = 0
F1 = 0
while F1 == 0:
    F1 = 1
    for y in range(H):
        for x in range(W):
            if list1[y][x] == "#":
                if y != 0:
                    list2[y-1][x] = "#"
                if y != H-1:
                    list2[y+1][x] = "#"
                if x != 0:
                    list2[y][x-1] = "#"
                if x != W-1:
                    list2[y][x+1] = "#"
            else:
                F1 *= 0
    if F1 == 0:
        answer += 1
    list1 = list2
print(answer)

Submission status: Wrong Answer

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

visited = [[-1]*(w) for _ in range(h)]
dq = deque()
directions = [[0,1],[1,0],[0,-1],[-1,0]]

# 初期配置の黒をキューに追加
for hi in range(h):
    for wi in range(w):
        if A[hi][wi] == '#':
            dq.append([hi,wi])
            visited[hi][wi] = 0

# キューが空になるまで
while dq:
    hi,wi = dq.popleft()
    for d in directions:
        new_hi, new_wi = hi+d[0],wi + d[1]
        # 場外ならスキップ
        if hi<0 or hi<h or wi<0 or wi>w: continue 
        # 「黒くしてない白マス」をキューに追加
        if visited[new_hi][new_wi] == 0 and A[new_hi][new_wi] == '.':
            dq.append([new_hi,new_wi])
            visited[new_hi][new_wi] = visited[hi][wi] + 1

Submission status: Wrong Answer

Solution code:
H, W = (int(_) for _ in input().split())
grid = []
black = []
nextb = []
count = 0
total = 0
white = True
for i in range (H):
    line = input()
    for j in range(W):
        if line[j] == '#':
            black.append([i,j])
            total += 1
    grid.append([line[j] for j in range(W)])

if H == 1 and W == 1:
    print(0)
else:
    if count == H*W:
      print(0)
      exit()
    while white:
        for coord in black:
            y = coord[0]
            x = coord[1]
            if y > 0:
                if grid[y-1][x] == '.':
                    grid[y-1][x] = '#'
                    nextb.append([y-1, x])
                    total += 1
            if y <= H-2:
                if grid[y+1][x] == '.':
                    grid[y+1][x] = '#'
                    nextb.append([y+1, x])
                    total += 1
            if x > 0:
                if grid[y][x-1] == '.':
                    grid[y][x-1] = '#'
                    nextb.append([y, x-1])
                    total += 1
            if x <= W-2:
                if grid[y][x+1] == '.':
                    grid[y][x+1] = '#'
                    nextb.append([y, x+1])
                    total += 1
        black = nextb
        nextb = []
        count += 1
        if total == H*W:
            white = False
        
    print(count)

Submission status: Wrong Answer

Solution code:
H, W = (int(_) for _ in input().split())
grid = []
black = []
nextb = []
count = 0
total = 0
white = True
for i in range (H):
    line = input()
    for j in range(W):
        if line[j] == '#':
            black.append([i,j])
            total += 1
    grid.append([line[j] for j in range(W)])

if H == 1 and W == 1:
    print(0)
else:
    while white:
        for coord in black:
            y = coord[0]
            x = coord[1]
            if y > 0:
                if grid[y-1][x] == '.':
                    grid[y-1][x] = '#'
                    nextb.append([y-1, x])
                    total += 1
            if y <= H-2:
                if grid[y+1][x] == '.':
                    grid[y+1][x] = '#'
                    nextb.append([y+1, x])
                    total += 1
            if x > 0:
                if grid[y][x-1] == '.':
                    grid[y][x-1] = '#'
                    nextb.append([y, x-1])
                    total += 1
            if x <= W-2:
                if grid[y][x+1] == '.':
                    grid[y][x+1] = '#'
                    nextb.append([y, x+1])
                    total += 1
        black = nextb
        nextb = []
        count += 1
        if total == H*W:
            white = False
        
    print(count)

Submission status: Wrong Answer

Solution code:
H, W = (int(_) for _ in input().split())
grid = []
black = []
nextb = []
count = 0
total = 0
white = True
for i in range (H):
    line = input()
    for j in range(W):
        if line[j] == '#':
            black.append([i,j])
            total += 1
    grid.append([line[j] for j in range(W)])

Submission status: Wrong Answer

Solution code:
H, W = (int(_) for _ in input().split())
grid = []

black = []
nextb = []
done = []
count = 0
white = True

for i in range (H):
    line = input()
    l = []
    for j in range(W):
        if line[j] == '#':
            black.append([i,j])
            done.append([i,j])
        l.append(line[j])
    grid.append(l)
    
if H == 1 and W == 1:
    print(0)
else:
    while white:
        for coord in black:
            if coord not in done:
                y = coord[0]
                x = coord[1]
                if y > 0:
                    if grid[y-1][x] == '.':
                        grid[y-1][x] = '#'
                        nextb.append([y-1, x])
                if y <= H-2:
                    if grid[y+1][x] == '.':
                        grid[y+1][x] = '#'
                        nextb.append([y+1, x])
                if x > 0:
                    if grid[y][x-1] == '.':
                        grid[y][x-1] = '#'
                        nextb.append([y, x-1])
                if x <= W-2:
                    if grid[y][x+1] == '.':
                        grid[y][x+1] = '#'
                        nextb.append([y, x+1])
                done.append(coord)
        black = nextb
        nextb = []
        count += 1
        if len(done) == H*W:
            white = False
                    
print(count)

Submission status: Wrong Answer

Solution code:
import math
import time
import pprint
import sys
from queue import Queue
from collections import deque
pp = pprint.PrettyPrinter(width = 30)
sys.setrecursionlimit(10**7)
INF = 10 ** 18
def MI(): return map(int, sys.stdin.readline().split())
def IS(): return input()
def bfs(q):
    # かかる歩数
    require = [[0 for i in range(w)] for j in range(h)]
    # 訪れたかどうか
    check = [[0 for i in range(w)] for j in range(h)]
    x_diff = [-1, 0, 1, 0]
    y_diff = [0, 1, 0, -1]
    while len(q) != 0:
        tmp_y, tmp_x = q.pop()
        for i in range(4):
            next_y = tmp_y + y_diff[i]
            next_x = tmp_x + x_diff[i]
            if ( 0 <= next_x <= w-1 
                    and 0 <= next_y <= h-1 
                    and check[next_y][next_x] == 0 
                    and a[next_y][next_x] != '#'):
                check[next_y][next_x] = 1 
                require[next_y][next_x] = require[tmp_y][tmp_x] + 1
                q.append([next_y, next_x])
    return require


h, w = MI()
a = [IS() for _ in range(h)]
start = time.time()
# h, w = 1000, 1000
# a = ['#.#.' * (w//4) for _ in range(h)]
out = 0
que = deque()

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

ans = bfs(que)

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

# print(time.time() - start)
print(out)

Submission status: Wrong Answer

Solution code:
def main():
  from collections import deque
  s,*c=open(0)
  h,w=map(int,s.split())
  c=''.join(t[:w]for t in c)
  f=[-1]*h*w
  q=deque()
  for i,d in enumerate(c):
    if d=='#':
      q.append(i)
      f[i]=0
  while q:
    y=q.popleft()
    v=f[y]
    if h*w>y+w and f[y+w]<0:
      q.append(y+w)
      f[y+w]=v+1
    if y>=w and f[y-w]<0:
      q.append(y-w)
      f[y-w]=v+1
    if w>y%w+1and f[y+1]<0:
      q.append(y+1)
      f[y+1]=v+1
    if y%w>1and f[y-1]<0:
      q.append(y-1)
      f[y-1]=v+1
  print(v)
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
def main():
  from collections import deque
  s,*c=open(0)
  h,w=map(int,s.split())
  c=''.join(t[:w]for t in c)
  f=[-1]*h*w
  q=deque()
  for i,d in enumerate(c):
    if d=='#':
      q.append(i)
      f[i]=0
  while q:
    y=q.popleft()
    v=f[y]
    if h*w>y+w and f[y+w]<0:
      q.append(y+w)
      f[y+w]=v+1
    if y-w>=0and f[y-w]<0:
      q.append(y-w)
      f[y-w]=v+1
    if h*w>y+1 and-~y%w and f[y+1]<0:
      q.append(y+1)
      f[y+1]=v+1
    if y>0and~-y%w and f[y-1]<0:
      q.append(y-1)
      f[y-1]=v+1
  print(v)
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
import numpy as np
h, w = map(int, input().split())

M = h + w
data = np.ones((h+2, w+2), np.int16) * M
for ln in range(1, h+1):
    line = list(input().rstrip())
    for r, letter in zip(range(1, w+1), line):
        if letter == '#':
            data[ln,r] = 0

data = data.transpose()

Submission status: Wrong Answer

Solution code:
import numpy as np
h, w = map(int, input().split())

M = h + w
data = np.ones((h+2, w+2), np.int16) * M
for ln in range(1, h+1):
    line = list(input().rstrip())
    for r, letter in zip(range(1, w+1), line):
        if letter == '#':
            data[ln,r] = 0

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
maze = [input() for i in range(H)]
reached = [[0] * W for i in range(H)]

que = deque([])

for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            continue
        que.append([i, j])

while que:
    py, px = que.popleft()
    dy = (0, 1, 0, -1)
    dx = (1, 0, -1, 0)
    for i, j in zip(dy, dx):
        ny = py + i
        nx = px + j

        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        if reached[ny][nx]:
            continue

        que.append([ny, nx])
        reached[ny][nx] += reached[py][px] + 1

MAX = 0
for i in range(H):
    MAX = max(max(reached[i]), MAX)

print(MAX)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
list1 = [list(input()) for l in range(H)]
list2 = list1
answer = -1
F1 = 0
while F1 == 0:
    F1 = 1
    for y in range(H):
        for x in range(W):
            if list1[y][x] == "#":
                if y != 0:
                    list2[y-1][x] = "#"
                if y != H-1:
                    list2[y+1][x] = "#"
                if x != 0:
                    list2[y][x-1] = "#"
                if x != W-1:
                    list2[y][x+1] = "#"
            else:
                F1 *= 0
    answer += 1
    list1 = list2
print(answer)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
list1 = [list(input()) for l in range(H)]
list2 = list1
answer = 0
F1 = 0
while F1 == 0:
    F1 = 1
    for y in range(H):
        for x in range(W):
            if list1[y][x] == "#":
                if y != 0:
                    list2[y-1][x] = "#"
                if y != H-1:
                    list2[y+1][x] = "#"
                if x != 0:
                    list2[y][x-1] = "#"
                if x != W-1:
                    list2[y][x+1] = "#"
            else:
                F1 *= 0
    answer += 1
    list1 = list2
print(answer)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
dist_matrix = [[-1] * W for i in range(H)]
queue = []
for i in range(H):
  line_list = list(input())
  for j in range(W):
    if line_list[j] == "#":  
      #black_h_list.append(i)
      #black_w_list.append(j)
      dist_matrix[i][j] = 0
      queue.append([i,j])
 
#print(queue)
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  i,j = queue.pop(0)
  if i > 0 and dist_matrix[i-1][j] == -1:
    dist_matrix[i-1][j] = dist_matrix[i][j] + 1
    queue.append([i-1,j])
  if i < H-1 and dist_matrix[i+1][j] == -1:
    dist_matrix[i+1][j] = dist_matrix[i][j] + 1
    queue.append([i+1,j])
  if j > 0 and dist_matrix[i][j-1] == -1:
    dist_matrix[i][j-1] = dist_matrix[i][j] + 1
    queue.append([i-1,j])
  if j < W-1 and dist_matrix[i][j+1] == -1:
    dist_matrix[i][j+1] = dist_matrix[i][j] + 1
    queue.append([i,j+1])
  
#print(dist_matrix)
max_value = 0
for i in range(H):
  for j in range(W):
    if dist_matrix[i][j] > max_value:
      max_value = dist_matrix[i][j]
print(max_value)

Submission status: Wrong Answer

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H, W):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


H, W = read_ints()
A = read_map(H, W)


# print(A)

from itertools import product
import numpy as np

# 黒の座標
ey, ex = [], []
for i, a in enumerate(A):
    for j, aa in enumerate(a):
        if aa == '#':
            ey.append(i)
            ex.append(j)

ey = np.array(ey)
ex = np.array(ex)


def mahattan(sy, sx, ey, ex):
    return np.abs(sy - ey) + np.abs(sx - ex)


ans = 0

for i in range(H):
    if '#' in A[i]:
        continue
        # 1行下の方が有利

    for j in range(W):
        if A[i][j] == '.':
            tmp = mahattan(i, j, ey, ex).min()
            ans = max(ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
from collections import deque
h,w=map(int,input().split())
a=[[] for _ in range(h)]
for i in range(h):
    s=input()
    for j in s:
        if j=='.':
            a[i].append(-1)
        else:
            a[i].append(0)
print(a)

def bfs():
    q=deque()
    c=0
    for i in range(h):
        for j in range(w):
            if a[i][j]==0:
                q.apppend((i,j))
                
    for i in d:
        0

Submission status: Wrong Answer

Solution code:
from collections import deque
inf = float('inf')
around = [[0,1],[1,0],[0,-1],[-1,0]]

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

dq = deque()

for i,line in enumerate(A):
    for j,e in enumerate(line):
        if e == "#":
            dq.append([i,j,0])

def bfs():
    res = -inf
    while dq:
        i,j,d = dq.popleft()
        d += 1
        for di,dj in around:
            ni = i + di; nj = j + dj
            if not(0 <= ni <= H-1 and 0 <= nj <= W-1):
                continue
            if A[ni][nj] == ".":
                A[ni][nj] = "#"
                dq.append([ni,nj,d])
                if d > res:
                    res = d
    return res

ans = bfs()
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
# from sklearn.neighbors import NearestNeighbors

H, W = map(int, input().split())
board = [[s for s in input().strip()] for i in range(H)]
black = []
white = []
for i, row in enumerate(board):
  for j, c in enumerate(row):
    if c == '#':
      black.append([i,j])
    else:
      white.append([i,j])

# neigh = NearestNeighbors(n_neighbors=1, metric='manhattan')
# neigh.fit(black)
# distances, indices = neigh.kneighbors(white)
# print(int(np.max(distances)))
print(1)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
a_array = [input() for x in range(h)]
black = [[False for x in range(w)] for y in range(h)]
next = set()
for row in range(h):
    for column in range(w):
        if a_array[row][column] == "#":
            black[row][column] = True
            next.add((row, column))

move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
cnt = 0
while next:
    tmp = set()
    # print(next)
    cnt += 1
    for row, column in next:
        for i, j in move:
            if not (0 <= row + i < h and 0 <= column + j < w) or black[row+i][column+j]:
                continue
            black[row+i][column+j] = True
            tmp.add((row + i, column + j))
    next = tmp
print(cnt)

Submission status: Wrong Answer

Solution code:
def a_darker_and_darker(H, W, Grid):
    def is_in_field(row, col):
        return (0 <= row < H) and (0 <= col < W)

    grid, q = [[None] * W for _ in range(H)], []
    # 黒マスがどこにあるかを調べる。ついでにgridを初期化
    for row in range(H):
        for col in range(W):
            if Grid[row][col] == '#':
                grid[row][col] = True
                q.append((row, col))
            else:
                grid[row][col] = False

    # '#'があるマスから上下左右に移動することを繰り返して任意のマスに到達する。
    # 何回繰り返せばすべてのマスに到達できるか？
    directions = ((-1, 0), (0, 1), (1, 0), (0, -1))  # 上右下左の隣接マスを指定
    ans = 0
    while q:
        tmp = []
        for row, col in q:
            for dr, dc in directions:
                nr, nc = row + dr, col + dc
                print(nr, nc)
                if is_in_field(nr, nc) and (not grid[nr][nc]):
                    grid[nr][nc] = True
                    tmp.append((nr, nc))
        ans += (1 if tmp else 0)
        q = tmp
    return ans

H, W = [int(i) for i in input().split()]
Grid = [input() for _ in range(H)]
print(a_darker_and_darker(H, W, Grid))

Submission status: Wrong Answer

Solution code:
class Queue():
    def __init__(self):
        self.data = []
        self.idx = 0
        self.size = 0

    def get(self):
        self.idx += 1
        self.size -= 1
        return self.data[self.idx-1]

    def put(self, item):
        self.size += 1
        self.data.append(item)

    def qsize(self):
        return self.size

        # input
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]

# bfs
bfs = [[-1 for j in range(W)] for i in range(H)]
que = Queue()
for i in range(H):
    for j in range(W):
        if(A[i][j] == '#'):
            que.put([i, j])
            bfs[i][j] = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

exit(0)

while(que.qsize()):
    p = que.get()
    for i in range(4):
        if(0 <= p[0]+dx[i] < H and 0 <= p[1]+dy[i] < W):
            if(bfs[p[0]+dx[i]][p[1]+dy[i]] == -1):
                que.put((p[0]+dx[i], p[1]+dy[i]))
                bfs[p[0]+dx[i]][p[1]+dy[i]] = bfs[p[0]][p[1]] + 1

# print ans
print(max([max(l) for l in bfs]))

Submission status: Wrong Answer

Solution code:
class Queue():
    def __init__(self):
        self.data = []
        self.idx = 0
        self.size = 0

    def get(self):
        self.idx += 1
        self.size -= 1
        return self.data[self.idx-1]

    def put(self, item):
        self.size += 1
        self.data.append(item)

    def qsize(self):
        return self.size

        # input
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]

# bfs
bfs = [[-1 for j in range(W)] for i in range(H)]
que = Queue()
for i in range(H):
    for j in range(W):
        if(A[i][j] == '#'):
            que.put((i, j))
            bfs[i][j] = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

exit(0)

while(que.qsize()):
    p = que.get()
    for i in range(4):
        if(0 <= p[0]+dx[i] < H and 0 <= p[1]+dy[i] < W):
            if(bfs[p[0]+dx[i]][p[1]+dy[i]] == -1):
                que.put((p[0]+dx[i], p[1]+dy[i]))
                bfs[p[0]+dx[i]][p[1]+dy[i]] = bfs[p[0]][p[1]] + 1

# print ans
print(max([max(l) for l in bfs]))

Submission status: Wrong Answer

Solution code:
from scipy import ndimage
import numpy as np
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
 
A_array = np.array(
    [[0 if s == "#" else 1 for s in input()] for i in range(H)])
# print(A_array)
 
# print(A_array)
b = ndimage.morphology.distance_transform_cdt(
    A_array, metric="taxicab")
print(np.max(b))

Submission status: Wrong Answer

Solution code:
from scipy import ndimage
import numpy as np

 
H, W = map(int, input().split())
 
A_array = np.array(
    [[0 if s == "#" else 1 for s in input()] for i in range(H)])
# print(A_array)

print(A_array)
 
# print(A_array)
b = ndimage.morphology.distance_transform_cdt(
    A_array, metric="taxicab")
print(np.max(b))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
from collections import deque
from heapq import heappush, heappop
def solve():
    H,W = map(int, input().split())
    A = [ list(input()) for _ in range(H)]
    HMANY = [ [10**9] * W for _ in range(H)]

    
    q = deque()
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" :
                # q.append((0,h,w))
                q.append((h,w))
                A[h][w] = "."
    ans = 0

    while q:
        # h,w = q.popleft()
        nextQ = deque()
        for h,w in q:
            A[h][w] = "#"
            if h+1 <H and A[h+1][w] == ".":
                nextQ.append( (h+1,w))
            if w+1 <W and A[h][w+1] == ".":
                nextQ.append((h,w+1))
            if 0<=h-1 and A[h-1][w] == ".":
                nextQ.append((h-1,w))
            if 0<=w-1 and A[h][w-1] == ".":
                nextQ.append((h,w-1))        
        ans += 1
        q = nextQ
        # num,h,w = q.popleft()        
        # if HMANY[h][w] > num and A[h][w] == ".":
        #     HMANY[h][w] = num
        #     A[h][w] = "#"
        #     if h+1 <H and A[h+1][w] == ".":
        #         q.append( (num+1,h+1,w))
        #     if w+1 <W and A[h][w+1] == ".":
        #         q.append((num+1,h,w+1))
        #     if 0<=h-1 and A[h-1][w] == ".":
        #         q.append((num+1,h-1,w))
        #     if 0<=w-1 and A[h][w-1] == ".":
        #         q.append((num+1,h,w-1))

    # ans = 0
    # for h in range(H):
    #     ans = max(ans, max(HMANY[h]))
    print(ans-1)

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
H,W = list(map(int,input().split()))
A = []
for i in range(H):
  A.append(list(input()))
n = 0
B = []
C = []
for y, row in enumerate(A):
  for z,x in enumerate(row):
    if x == "#":
      pos = (y,z)
      B.append(pos)
    else:
      pos = (y,z)
      C.append(pos)
while True:
  D = []
  for i in range(len(C)):
    try:
      w,v = C[i]
      if (w + 1,v) in B or (w -1,v) in B or (w,v + 1) in B or (w,v - 1) in B:
        A[w][v] = "#"
        value = (w,v)
        D.append(value)
    except IndexError:
      pass
  n += 1
  B = B + D
  for i in range(len(D)):
    C.remove(D[i])
  if len(B) == H * W:
    break
 
print(n)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
H,W = list(map(int,input().split()))
A = []
for i in range(H):
  A.append(list(input()))
n = 0
B = []
C = []
for y, row in enumerate(A):
  for z,x in enumerate(row):
    if x == "#":
      pos = (y,z)
      B.append(pos)
    else:
      pos = (y,z)
      C.append(pos)
while True:
  D = []
  for i in range(len(C)):
    try:
      w,v = C[i]
      if (w + 1,v) in B or (w -1,v) in B or (w,v + 1) in B or (w,v - 1) in B:
        A[w][v] = "#"
        value = (w,v)
        D.append(value)
        print(B,n)
    except IndexError:
      pass
  n += 1
  B = B + D
  for i in range(len(D)):
    C.remove(D[i])
  if len(B) == H * W:
    break
 
print(n)