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:
#bfs2-AGC033A
h,w=map(int,input().split())
s=[input() for _ in range(h)]

sxy=[]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            sxy.append([0,i,j])
ddx=[1,-1,0,0]
ddy=[0,0,1,-1]

inf=float("inf")
 
t=[[inf for _ in range(w)] for _ in range(h)]
q=[]
for txy in sxy:
    q.append(txy)
    t[txy[1]][txy[2]]=0

count=0
while q:
    d,y,x=q.pop(0)
    count+=1
    for (dx,dy) in zip(ddx,ddy):
        ny=y+dy
        nx=x+dx
        if not (0<=nx<w and 0<=ny<h):continue
        if t[ny][nx]==inf:
            t[ny][nx]=t[y][x]+1
            q.append([d+1,ny,nx])
    if count==1000:
        break
a=0
for res in t:
    a=max(a,max(res))
print(a)
print(d)

Submission status: Wrong Answer

Solution code:
#bfs2-AGC033A
h,w=map(int,input().split())
s=[input() for _ in range(h)]

sxy=[]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            sxy.append([0,i,j])
ddx=[1,-1,0,0]
ddy=[0,0,1,-1]

inf=float("inf")
 
t=[[inf for _ in range(w)] for _ in range(h)]
q=[]
for txy in sxy:
    q.append(txy)
    t[txy[1]][txy[2]]=0

count=0
while q:
    d,y,x=q.pop(0)
    count+=1
    for (dx,dy) in zip(ddx,ddy):
        ny=y+dy
        nx=x+dx
        if not (0<=nx<w and 0<=ny<h):continue
        if t[ny][nx]==inf:
            t[ny][nx]=t[y][x]+1
            q.append([d+1,ny,nx])
    if count==h*w:
        break
a=0
for res in t:
    a=max(a,max(res))
print(a)
print(d)

Submission status: Wrong Answer

Solution code:
#bfs2-AGC033A
h,w=map(int,input().split())
s=[input() for _ in range(h)]

sxy=[]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            sxy.append([0,i,j])
ddx=[1,-1,0,0]
ddy=[0,0,1,-1]

inf=float("inf")
 
t=[[inf for _ in range(w)] for _ in range(h)]
q=[]
for txy in sxy:
    q.append(txy)
    t[txy[1]][txy[2]]=0

while q:
    d,y,x=q.pop(0)
    for (dx,dy) in zip(ddx,ddy):
        ny=y+dy
        nx=x+dx
        if not (0<=nx<w and 0<=ny<h):continue
        if t[ny][nx]!=inf and t[ny][nx]>t[y][x]+1:
            t[ny][nx]=t[y][x]+1
            q.append([d+1,ny,nx])
a=0
for res in t:
    a=max(a,max(res))
print(a)

Submission status: Wrong Answer

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．

def ins(ls, i):
  ls[i] = True
  return i

def main():
  H, W = list(map(int, input().split()))
  all_count = H * W
  L = [j == "#" for i in range(H) for j in input()]
  blacks = [i for i in range(all_count) if L[i]]
  black_count = len(blacks)
 
  cands_H = [-W, W]
  cands_W = [-1, 1]
  result = 0
  while True:
    next_steps = [black+cand for black in blacks for cand in cands_H]
    next_steps.extend([black-1 for black in blacks if black%W != 0])
    next_steps.extend([black+1 for black in blacks if black%W != W-1])
    next_steps = set(next_steps)
    blacks = [ins(L, i) for i in next_steps if i >= 0 and i < all_count and not L[i]]
    black_count += len(blacks)
    result += 1
    if black_count >= all_count:
      break

  print(result)

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．

def main():
  H, W = list(map(int, input().split()))
  all_count = H * W
  L = [j == "#" for i in range(H) for j in input()]
  all_count = H * W
  blacks = [i for i in range(all_count) if L[i]]
  black_count = len(blacks)
 
  cands_H = [-W, W]
  cands_W = [-1, 1]
  result = 0
  while True:
    next_steps = set([black+cand for black in blacks for cand in cands_H])
    next_steps = next_steps | set([black-1 for black in blacks if black%W != 0])
    next_steps = next_steps | set([black+1 for black in blacks if black%W != W-1])
    blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
    black_count += len(blacks)
    result += 1
    if black_count >= all_count:
      break
    for i in blacks:
      L[i] = True

  print(result)

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
H, W = list(map(int, input().split()))
L = [True if j == "#" else False for i in range(H) for j in input()]
all_count = H * W
blacks = [i for i in range(all_count) if L[i]]
black_count = len(blacks)

cands = [-1, -W, 1, W]
result = 0
while black_count < all_count:
  next_steps = list(set([black+cand for black in blacks for cand in cands]))
  blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
  for i in blacks:
    L[i] = True
  black_count += len(blacks)
  result += 1

print(result)

Submission status: Wrong Answer

Solution code:
import queue
H, W = list(map(int, input().split()))
L = [[j for j in input()] for i in range(H)]
q = queue.Queue()
[q.put((i, j)) for i in range(H) for j in range(W) if L[i][j] == "#"]

cands = [[-1, 0], [1, 0], [0, -1], [0, 1]]
count = 0
q_size = q.qsize()
print(q_size)
result = -1
while q.qsize() > 0:
  now = q.get()
  for cand in cands:
    i = now[0] + cand[0]
    j = now[1] + cand[1]
    if i < 0 or i >= H or j < 0 or j >= W:
      continue
    if L[i][j] == ".":
      L[i][j] = "#"
      q.put((i, j))
  count += 1
  if count == q_size:
    count = 0
    q_size = q.qsize()
    result += 1

print(result)

Submission status: Wrong Answer

Solution code:
def sol():
    h,w=map(int,input().split())
    l=[]
    d=set()
    for i in range(h):
        s=list(input())
        for j in range(w):
            if s[j]=="#": d.add((i,j))
        l.append(s)
    ans=-1
    for i in range(2000):
        if len(d)==0: break
        ans+=1
        t=set()
        for j in d:
            if 0<=j[0]+1<h and l[j[0]+1][j[1]]==".":
                l[j[0]+1][j[1]]="#"
                t.add((j[0]+1,j[1]))
            if 0<=j[0]-1<h and l[j[0]-1][j[1]]==".":
                l[j[0]-1][j[1]]="#"
                t.add((j[0]-1,j[1]))
            if 0<=j[1]+1<w and l[j[0]][j[1]+1]==".":
                l[j[0]][j[1]+1]="#"
                t.add((j[0],j[1]+1))
            if 0<=j[1]-1<w and l[j[0]][j[1]-1]==".":
                l[j[0]][j[1]-1]="#"
                t.add((j[0],j[1]-1))
        d=t
    print(ans)

if __name__ == "main":
    sol()

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
l=[]
d=set()
for i in range(h):
    s=list(input())
    for j in range(w):
        if s[j]=="#": d.add((i,j))
    l.append(s)
ans=-1
for i in range(1000):
    if len(d)==0: break
    ans+=1
    t=set()
    for j in d:
        #print(j)
        if 0<=j[0]+1<h and l[j[0]+1][j[1]]==".":
            l[j[0]+1][j[1]]="#"
            t.add((j[0]+1,j[1]))
        if 0<=j[0]-1<h and l[j[0]-1][j[1]]==".":
            l[j[0]-1][j[1]]="#"
            t.add((j[0]-1,j[1]))
        if 0<=j[1]+1<w and l[j[0]][j[1]+1]==".":
            l[j[0]][j[1]+1]="#"
            t.add((j[0],j[1]+1))
        if 0<=j[1]-1<w and l[j[0]][j[1]-1]==".":
            l[j[0]][j[1]-1]="#"
            t.add((j[0],j[1]-1))
    d=t
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
 
 
def func(x):
    if x == '.':
        return 2000
    else:
        return 0
 
 
H, W = map(int, input().split())
b = []
for _ in range(H):
    b.append(list(map(func, input())))
a = np.array(b)

print(2)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque


dx_list = [1, 0, -1, 0]
dy_list = [0, -1, 0, 1]
def bfs(h_len, w_len, q_list):
    cnt = 0
    while True:
        new_q_list = []
        for q in q_list:
            h, w = q[0], q[1]
            for dx, dy in zip(dx_list, dy_list):
                x, y = w+dx, h+dy
                if m_list[y][x] == 0:
                    m_list[y][x] = 1
                    new_q_list.append([y, x])
        if len(new_q_list) == 0:
            break
        else:
            cnt += 1
            q_list = new_q_list
    return cnt


if __name__ == "__main__":
    input = sys.stdin.readline
    h_len, w_len = map(int, input().split())
    m_list = [[1 for _ in range(w_len+2)]]
    for _ in range(h_len):
        s = input()[:-1]
        m_list.append([1] + [1 if i == '#' else 0 for i in s] + [1])
    m_list.append([1 for _ in range(w_len+2)])
    q_list = []
    for h in range(1, h_len):
        for w in range(1, w_len):
    	    if m_list[h][w] == 1:
    		    q_list.append([h, w])
    ans = bfs(h_len, w_len, q_list)
    print(ans)

Submission status: Wrong Answer

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

q=[]
h,w=map(int,input().split())
arr=[[True]*(w+2)]
for i in range(h):
  tmp=[True]
  for j in input():
    if j=='#':
      tmp.append(True)
    else:
      tmp.append(False)
  tmp.append(True)
  arr.append(tmp)
arr.append([True]*(w+2))
for i in range(1,h+1):
  for j in range(1,w+1):
    if arr[i][j]:
      q.append([i,j])
ans=0
while 1:
  nq=[]
  for y,x in q:
    if not arr[y-1][x]:
      nq.append([y-1,x])
      arr[y-1][x]=True
    if not arr[y][x-1]:
      nq.append([y,x-1])
      arr[y][x-1]=True
    if not arr[y+1][x]:
      nq.append([y+1,x])
      arr[y+1][x]=True
    if not arr[y][x+1]:
      nq.append([y,x+1])
      arr[y][x+1]=True
  if len(nq)==0:
    print(ans)
    break
  else:
    q=nq
    ans+=1

Submission status: Wrong Answer

Solution code:
H,W=map(int, input().split())
A=[]
for i in range(H):
  A.append(list(input()))
ds=[]
for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      ds.append((i, j))

x=-1
"""
q=[(i, j, 0) for i, j in ds]
while(q):
  (i, j, n)=q[0]
  del q[0]
  x=max(x, n)
  if i > 0 and A[i-1][j] == '.':
    A[i-1][j] = '#'
    q.append((i-1, j, n+1))
  if i < H-1 and A[i+1][j] == '.':
    A[i+1][j] = '#'
    q.append((i+1, j, n+1))
  if j > 0 and A[i][j-1] == '.':
    A[i][j-1] = '#'
    q.append((i, j-1, n+1))
  if j < W-1 and A[i][j+1] == '.':
    A[i][j+1] = '#'
    q.append((i, j+1, n+1))
"""
  
#print(H,W)
#print(A)
#print(ds)
print(x)

Submission status: Wrong Answer

Solution code:
"""
解説と提出 #5308329 を参考に作成
"""


import numpy as np


def solve():
    H, W = map(int, input().split())
    mass = [[0] * W for _ in range(H)]
    for Hi in range(H):
        massHi = [0 if s == '.' else 1 for s in list(input())]
        for Wi in range(W):
            mass[Hi][Wi] = massHi[Wi]

    while True:
        massT = mass.copy()
        for Hi in range(H):
            for Wi in range(W):
                if mass[Hi][Wi] == 1:
                    mass[Hi][Wi] = -1
                    if Hi != 0 and mass[Hi - 1][Wi] == 0:
                        massT[Hi - 1][Wi] += 1
                    if Hi != H - 1 and mass[Hi + 1][Wi] == 0:
                        massT[Hi - 1][Wi] += 1
                    if Hi != 0 and mass[Hi - 1][Wi] == 0:
                        massT[Hi - 1][Wi] += 1
                    if Hi != H - 1 and mass[Hi + 1][Wi] == 0:
                        massT[Hi - 1][Wi] += 1
        pass


def solve2():
    H, W = map(int, input().split())
    values = []
    for i in range(H):
        values.append([0 if i == '#' else 1 for i in list(input())])
    values = np.array(values)

    # print(values.shape[0])
    # print(values.shape[1])
    #
    # print(values[1,1])
    # print(np.max(values))
    for i in range(1, H + W + 1):
        new_values = values.copy()
        for h in range(H):
            for w in range(W):
                if values[h, w] == 0:
                    # print('return', h, w)
                    # 上辺
                    if h != 0 and values[h - 1, w] == 1:
                        new_values[h - 1, w] = 0
                    # 底辺
                    if h != H - 1 and values[h + 1, w] == 1:
                        new_values[h + 1, w] = 0
                    # 左端
                    if w != 0 and values[h, w - 1] == 1:
                        new_values[h, w - 1] = 0
                    # 右端
                    if w != W - 1 and values[h, w + 1] == 1:
                        new_values[h, w + 1] = 0
                        new_values[h, w] = -1
        # print(new_values)
        if np.max(new_values) == 0:
            print(i)
            return
        values = new_values


if __name__ == '__main__':
    solve2()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, insort

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

lines = [input() for s in range(H)]
distance = [k for k in range(H*W) if lines[k//W][k%W] == '#']
nb = len(distance)
if(nb == H*W):
  print(0)
  exit()
number = 0
new_distance = distance[:]
while(nb < H*W):
  tmp = []
  for k in new_distance:
    if k%W-1 >= 0:
      tmp.append(k-1)
    if k%W+1 <= W-1:
      tmp.append(k+1)
    if k-W >= 0:
      tmp.append(k-W)
    if k+W <= (H)*W-1:
      tmp.append(k+W)
#  tmp = list(set(tmp))
  new_distance = tmp[:]
  for k in tmp:
    insort(distance, k)
#  distance = list(set(distance))
  number += 1
  nb = len(distance)
print(number)

Submission status: Wrong Answer

Solution code:
from functools import reduce
from bisect import bisect_left, insort
from collections import deque

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

lines = [input() for s in range(H)]
distance = [k for k in range(H*W) if lines[k//W][k%W] == '#']
print(distance)
nb = len(distance)
if(nb == H*W):
  print(0)
  exit()
number = 0
new_distance = distance[:]
while(nb < H*W):
  tmp = []
  for k in new_distance:
    if k%W-1 >= 0:
      tmp.append(k-1)
    if k%W+1 <= W-1:
      tmp.append(k+1)
    if k-W >= 0:
      tmp.append(k-W)
    if k+W <= (H)*W-1:
      tmp.append(k+W)
  tmp = list(set(tmp))
  new_distance = tmp[:]
  for k in tmp:
    insort(distance, k)
  distance = list(set(distance))
  number += 1
  nb = len(distance)
print(number)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
m = [""] * H
n = [[0]*W for i in range(H)]
q = []

for h in range(H):
    m[h] = input()
    for w in range(W):
        if m[h][w] == '#':
            n[h][w] = 1
            q.append([h, w])

mx = 1
while 1:
    mx += 1
    nq = []
    for h, w in q:
        if h > 0 and n[h - 1][w] == 0:
            n[h - 1][w] = mx
            nq.append([h-1, w])
        if w > 0 and n[h][w - 1] == 0:
            n[h][w - 1] = mx
            nq.append([h, w-1])
        if h + 1 < H and n[h + 1][w] == 0:
            n[h + 1][w] = mx
            nq.append([h+1, w])
        if w + 1 < W and n[h][w + 1] == 0:
            n[h][w + 1] = mx
            nq.append([h, w + 1])
    if len(nq) == 0:
        break
    else:
        q = nq

print(mx-1)

Submission status: Wrong Answer

Solution code:
print("0")

Submission status: Wrong Answer

Solution code:
from collections import deque


h, w = map(int, input().split())
hs, ws = set(range(h)), set(range(w))
d = deque()
memo = [[None] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
a = tuple(input() for _ in hs)
b = [[i, j] for i in hs for j in ws if a[i][j] == '#']
for i, j in b:
    d.append((i, j))
    memo[i][j] = 0
while d:
    dh, dw = d.popleft()
    for i, j in move:
        dhn, dwn = dh + i, dw + j
        if (0 <= dhn < h) and (0 <= dwn < w) and not(memo[dhn][dwn]):
            d.append((dhn, dwn))
            memo[dhn][dwn] = memo[dh][dw] + 1
ans = max([max(e) for e in memo])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


h, w = map(int, input().split())
hs, ws = set(range(h)), set(range(w))
a = []
b = []
d = deque([])
memo = [[None] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
a = tuple(input() for _ in hs)
b = [[i, j] for i in hs for j in ws if a[i][j] == '#']
for i, j in b:
    d.append([i, j])
    memo[i][j] = 0

ans = 0
while(d):
    dh, dw = d.popleft()
    for i, j in move:
        dhn, dwn = dh + i, dw + j
        if (0 <= dhn < h) and (0 <= dwn < w) and not(memo[dhn][dwn]):
            memo[dhn][dwn] = memo[dh][dw] + 1
            d.append([dhn, dwn])
            ans = max(ans, memo[dhn][dwn])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


h, w = map(int, input().split())
hs, ws = set(range(h)), set(range(w))
a = []
b = []
d = deque([])
memo = [[None] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
a = tuple(input() for _ in hs)
b = [[i, j] for i in hs for j in ws if a[i][j] == '#']
for i, j in b:
    d.append([i, j])
    memo[i][j] = 0


def f(d, hmax, wmax):
    dh, dw = d.popleft()
    for i, j in move:
        if (0 <= dh + i < hmax) and (0 <= dw + j < wmax) and not(memo[dh + i][dw + j]):
            memo[dh + i][dw + j] = memo[dh][dw] + 1
            d.append([dh + i, dw + j])
    return d
 
 
while(d):
    d = f(d, h, w)
ans = max([max(e) for e in memo])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


h, w = map(int, input().split())
hs, ws = set(range(h)), set(range(w))
a = []
b = []
d = deque([])
memo = [[None] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
a = tuple(input() for _ in hs)
b = [[i, j] for i in hs for j in ws if a[i][j] == '#']
for i, j in b:
    d.append([i, j])
    memo[i][j] = 0


def d_list_update():
    dh, dw = d.popleft()
    for i, j in move:
        if (0 <= dh + i < h) and (0 <= dw + j < w) and not(memo[dh + i][dw + j]):
            memo[dh + i][dw + j] = memo[dh][dw] + 1
            d.append([dh + i, dw + j])
    return d


while d:
    d_list_update()
ans = max([max(e) for e in memo])
print(ans)

Submission status: Wrong Answer

Solution code:
import copy


h, w = map(int, input().split())
a = []
d = []
for i in range(h):
    a.append(list(input()))
    for j, s in enumerate(a[i]):
        if s == '#':
            d.append([i, j])


def d_list_update(d, hmax, wmax):
    tmp = copy.deepcopy(d)
    move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    for dh, dw in d:
        for i, j in move:
            if (0 <= dh + i < hmax) and (0 <= dw + j < wmax):
                if not([dh + i, dw + j] in tmp):
                    tmp.append([dh + i, dw + j])
    return tmp


def abc(d, hmax, wmax, c=1):
    d = d_list_update(d, hmax, wmax)
    if len(d) != hmax * wmax:
        c += 1
        c = abc(d, hmax, wmax, c)
    return c


ans = abc(d, h, w)
print(ans)

Submission status: Wrong Answer

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


def dot_to_sharp(dark_list, hmax, wmax, hnow, wnow):
    move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    if dark_list[hnow][wnow] == '.':
        return dark_list
    if dark_list[hnow][wnow] == '#':
        for i, j in move:
            if (0 <= hnow + i < hmax) and (0 <= wnow + j < wmax)\
                    and dark_list[hnow + i][wnow + j] == '.':
                dark_list[hnow + i][wnow + j] = '*'
    return dark_list


def abc(dark_list, hmax, wmax, c=1):
    for i in range(hmax):
        for j in range(wmax):
            dark_list = dot_to_sharp(dark_list, hmax, wmax, i, j)
    next = 0
    for d in dark_list:
        if '.' in d:
            next = 1
    if next:
        for i in range(hmax):
            for j in range(wmax):
                if dark_list[i][j] == '*':
                    dark_list[i][j] = '#'
        c += 1
        c = abc(dark_list, hmax, wmax, c)
    return c


ans = abc(a, h, w)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():
    H, W = map(int, input().split())
    A = [input() for _ in range(H)]
    q = deque()
    visited = [[False] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                q.append((i, j, 0))
                visited[i][j] = True
    ans = 0
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    while len(q):
        i, j, cost = q.popleft()
        ans = max(ans, cost)
        for d in directions:
            ni = i + d[0]
            nj = j + d[1]
            if 0 <= ni < H and 0 <= nj < W and not visited[ni][nj]:
                q.append((ni, nj, cost+1))
                visited[i][j] = True
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():
    H, W = map(int, input().split())
    A = [input() for _ in range(H)]
    q = deque()
    visited = [[False] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                q.append((i, j, 0))
                visited[i][j] = True
    ans = 0
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    while len(q):
        i, j, cost = q.popleft()
        ans = max(ans, cost)
        for d in directions:
            ni = i + d[0]
            nj = j + d[1]
            ncost = cost + 1
            if 0 <= ni < H and 0 <= nj < W and not visited[ni][nj]:
                q.append((ni, nj, ncost))
                visited[i][j] = True
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():
    H, W = map(int, input().split())
    A = [input() for _ in range(H)]
    visited = [[False] * W for _ in range(H)]
    q = deque()
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                visited[i][j] = True
                q.append((i, j, 0))
    ans = 0
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    while len(q):
        i, j, cost = q.popleft()
        visited[i][j] = True
        ans = max(ans, cost)
        for d in directions:
            ni = i + d[0]
            nj = j + d[1]
            ncost = cost + 1
            if 0 <= ni < H and 0 <= nj < W and not visited[ni][nj]:
                q.append((ni, nj, ncost))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def f(h, w):
    dt = [[-1, 0], [0, -1], [0, 1], [1, 0]]
    t = [[True] * (w + 2)]
    for _ in range(h):
        t += [[True] + [(c == "#") for c in input()] + [True]]
    t += [[True] * (w + 2)]
    kuro = set()
    for i, ti in enumerate(t[1:-1]):
        for j, tij in enumerate(ti[1:-1]):
            if tij:
                kuro.add((i + 1, j + 1))
    cnt = -1
    while kuro:
        cnt += 1
        nxt = set()
        for i, j in kuro:
            t[i][j] = True
            for di, dj in dt:
                ni, nj = i + di, j + dj
                if t[ni][nj] == False:
                    nxt.add((ni, nj))
        kuro = nxt
    print(cnt)


h, w = map(int, input().split())
f(h, w)

Submission status: Wrong Answer

Solution code:
import numpy as np

H,W = list(map(int,input().split()))
INFTY = 10000
A = np.array([[0 if c=="#" else INFTY for c in input()] for _ in range(H)])

q = []
for i in range(H):
    for j in range(W):
        if A[i][j] == 0:
            q.append((i,j))
ans = 0
k = 0
while k < len(q):
    i,j = q[k]
    v = A[i][j]
    if i>0 and A[i-1][j]==".":
        A[i-1][j] = v + 1
        q.append((i-1,j))
        ans = max(ans,v+1)
    if i<H-1 and A[i+1][j]==".":
        A[i+1][j] = v + 1
        q.append((i+1,j))
        ans = max(ans,v+1)
    if j>0 and A[i][j-1]==".":
        A[i][j-1] = v + 1
        q.append((i,j-1))
        ans = max(ans,v+1)
    if j<W-1 and A[i][j+1]==".":
        A[i][j+1] = v + 1
        q.append((i,j+1))
        ans = max(ans,v+1)
    k += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
 
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
 
que = deque()
INF = float('inf')
dx = [1, 0, -1, 0]
dy = [0, 1, 0 , -1]            
D = [[INF] * W for i in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            que.append([i, j])
            D[i][j] = 0
                       
def bfs():
    while len(que) != 0:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and A[nx][ny] != '#' and D[nx][ny] == INF:
                que.append([nx, ny])
                D[nx][ny] = D[p[0]][p[1]] + 1
        print(que)
    
bfs()

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

Submission status: Wrong Answer

Solution code:

import sys

H, W = map(int, sys.stdin.readline().split())

A = []
for i in range(H):
    A.append(sys.stdin.readline().rstrip())

def white_to_black(target, black_square, H, W, target_queue):
    y = target[0]
    x = target[1]
    count = 0
    if y > 0 and [y - 1,x] not in black_square:
        black_square.append([y - 1,x])
        target_queue.append([y - 1,x])
        count += 1
    if y < H - 1 and [y + 1,x] not in black_square:
        black_square.append([y + 1, x])
        target_queue.append([y + 1,x])
        count += 1
    if x > 0 and [y, x - 1] not in black_square:
        black_square.append([y, x -1])
        target_queue.append([y, x - 1])
        count += 1
    if x < W - 1 and [y, x + 1] not in black_square:
        black_square.append([y, x + 1])
        target_queue.append([y, x + 1])
        count += 1
    return count


black_count = 0
black_square = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            black_count += 1
            black_square.append([i, j])

ans = 0
target_queue = black_square[:]
while black_count != H * W:
    ans += 1
    for target in target_queue:
        black_count += white_to_black(target, black_square, H, W, target_queue)
        target_queue.remove(target)

print(ans)

Submission status: Wrong Answer

Solution code:

import sys

H, W = map(int, sys.stdin.readline().split())

A = []
for i in range(H):
    A.append(sys.stdin.readline().rstrip())

def white_to_black(target, black_square, H, W):
    y = target[0]
    x = target[1]
    count = 0
    print("---" + str(target))
    if y > 0 and [y - 1,x] not in black_square:
        black_square.append([y - 1,x])
        count += 1
    if y < H - 1 and [y + 1,x] not in black_square:
        black_square.append([y + 1, x])
        count += 1
    if x > 0 and [y, x - 1] not in black_square:
        black_square.append([y, x -1])
        count += 1
    if x < W - 1 and [y, x + 1] not in black_square:
        black_square.append([y, x + 1])
        count += 1
    return count


black_count = 0
black_square = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            black_count += 1
            black_square.append([i, j])

ans = 0
while black_count != H * W:
    ans += 1
    current_targets = black_square[:]
    for target in current_targets:
        black_count += white_to_black(target, black_square, H, W)

print(ans)

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 
#INF = np.Inf
INF = 2000

#D = np.zeros((H, W))
D = [[0]*W for h in range(H)]
for h in range(H):
    A[h] = input()
    for w in range(W):
        if A[h][w] == '.':
            D[h][w] = INF

def main():
    d_max = 0 
    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)
            d_max = max(D[H-h-1][W-w-1], d_max)
    #print(D)
    #print(int(np.amax(D)))
    print(int(d_max))
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()