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:
from time import time
from collections import deque

q = deque()
H, W = map(int, input().split())
dists = [[-1] * W for _ in range(H)]
for i in range(H):
    for j, v in enumerate(input()):
        if v == "#":
            q.append((0, i, j))


def append(d, i, j):
    if not 0 <= i < H or not 0 <= j < W or dists[i][j] != -1:
        return
    dists[i][j] = d
    q.append((d, i, j))


while len(q):
    d, i, j = q.popleft()
    append(d+1, i-1, j)
    append(d+1, i+1, j)
    append(d+1, i, j-1)
    append(d+1, i, j+1)

# fast (0.01s)
ans = max(map(max, dists))
# very slow (4.2s)
# ans = max(sum(dists, []))

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

inf = float('inf')

def solve(H: int, W: int, A: "List[str]"):
    dist = [[inf] * W for h in range(H)]
    for h in range(1, H):
        for w in range(1, W):
            if A[h][w] == '#':
                dist[h][w] = 0
            else:
                dist[h][w] = min(dist[h-1][w], dist[h][w-1]) + 1
    
    dmax = 0
    for h in range(H-1, -1, -1):
        for w in range(W-1, -1, -1):
            hh = min(h+1, H-1)
            ww = min(w+1, W-1)
            dist[h][w] = min([dist[h][w], dist[h][ww] + 1, dist[hh][w] + 1])
            dmax = max(dist[h][w], dmax)
    print(dmax) 
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

inf = float('inf')

def solve(H: int, W: int, A: "List[str]"):
    dist = [[inf] * W for h in range(H)]
    for h in range(1, H):
        for w in range(1, W):
            if A[h][w] == '#':
                dist[h][w] = 0
            else:
                dist[h][w] = min(dist[h-1][w], dist[h][w-1]) + 1
    
    dmax = 0
    for h in range(H-1, -1, -1):
        for w in range(W-1, -1, -1):
            hh = min(h+1, H-1)
            ww = min(w+1, W-1)
            dist[h][w] = min(dist[h][w], dist[h][ww] + 1, dist[hh][w] + 1)
            dmax = max(dist[h][w], dmax)
    print(dmax) 
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

inf = float('inf')

def solve(H: int, W: int, A: "List[str]"):
    dist = [[inf] * W for h in range(H)]
    for h in range(1, H):
        for w in range(1, W):
            if A[h][w] == '#':
                dist[h][w] = 0
            else:
                dist[h][w] = min(dist[h-1][w], dist[h][w-1]) + 1
    
    dmax = 0
    for h in range(H-1, -1, -1):
        for w in range(W-1, -1, -1):
            hh = min(h+1, H-1)
            ww = min(w+1, W-1)
            dist[h][w] = min(dist[h][w], dist[hh][ww] + 1, dist[hh][ww] + 1)
            dmax = max(dist[h][w], dmax)
    print(dmax) 
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

white = []
black = []

length = sum([a.count(".") for a in A])
cnt = 0

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

while (length > 0):
    gray = []
    for l in black:
        if l[1] != 0:
            c1 = [l[0],l[1]-1]
            if A[c1[0]][c1[1]] == ".":
                gray.append(c1)
                A[c1[0]][c1[1]] == "#"
        if l[1] != W-1:
            c2 = [l[0],l[1]+1]
            if  A[c2[0]][c2[1]] == ".":
                gray.append(c2)
                A[c2[0]][c2[1]] == "#"
        if l[0] != 0:
            c3 = [l[0]-1,l[1]]
            if  A[c3[0]][c3[1]] == ".":
                gray.append(c3)
                A[c3[0]][c3[1]] == "#"
        if l[0] != H-1:
            c4 = [l[0]+1,l[1]]
            if  A[c4[0]][c4[1]] == ".":
                gray.append(c4)
                A[c4[0]][c4[1]] == "#"
    
    gray = list(map(list, set(map(tuple, gray))))
    
    black =[]
    
    for l in gray:
        black.append(l)
        A[l[0]][l[1]] = "#"
        
    cnt += 1
    length = len(black)
    
print(cnt - 1)

Submission status: Wrong Answer

Solution code:
from collections import deque


def atcoder_input():
    H, W = (int(i) for i in input().split())

    Q = deque()

    for h in range(H):
        for w, c in enumerate(input()):
            if c=="#":
                Q.append((h + 1, w + 1, 0))

    return Q, H, W


def main():
    Q, H, W = atcoder_input()
    searched = [[0] * (W + 2) for _ in range(H + 2)]

    for h in range(H + 2):
        searched[h][0] = 1
        searched[h][-1] = 1

    for w in range(W + 2):
        searched[0][w] = 1
        searched[-1][w] = 1

    max_count = 0

    while Q:
        h, w, count = Q.popleft()

        for (h2, w2) in ([h + 1, w], [h, w + 1], [h - 1, w], [h, w - 1]):
            if searched[h2][w2] == 1:
                continue
            else:
                searched[h2][w2] = 1

                if count + 1 > max_count:
                    max_count = count + 1
                Q.append((h2, w2, count + 1))

    print(max_count)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

search = []
board = {}
for i in range(h):
    for j in range(w):
        if x[i][j] == "#":
            board[(i,j)] = 0
            search.append((i,j))

count = 1
ans = 0
while search:
    search2 = []
    for xy in search:
        x,y = xy
        if (x+1,y) not in board and x+1 <w:
            board[(x+1,y)] = count
            search2.append((x+1,y))
            ans = count
        if (x-1,y) not in board and x-1 >=0:
            board[(x-1,y)] = count
            search2.append(((x-1,y)))
            ans = count
        if (x,y+1) not in board and y+1 <h:
            board[(x,y+1)] = count
            search2.append((x,y+1))
            ans = count
        if (x,y-1) not in board and y-1 >=0:
            board[(x,y-1)] = count
            search2.append((x,y-1))
            ans = count
    search = search2
    count +=1

print(ans)

Submission status: Wrong Answer

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

matrix = []
for i in range(H):
    matrix.append(list(input()))
matrix = np.array(matrix)
black_list = np.where(matrix=='#')
count = 0
queue = []

for i in range(len(black_list[0])):
    queue.append([black_list[0][i], black_list[1][i]])


def search(x,y,matrix):
    q = []
    # 上を見る       
    if not x == 0:
        state = matrix[x-1,y]
        if state == ".":
            q.append([x-1,y])
            matrix[x-1,y] = "#"

    # 下を見る       
    if not x == H-1:
        
        state = matrix[x+1,y]
        if state ==".":
            q.append([x+1,y])
            matrix[x+1,y] = "#"

    # 左を見る       
    if not y == 0:
        state = matrix[x,y-1]
        if state == ".":
            q.append([x,y-1])
            matrix[x,y-1] = "#"
        
    # 右を見る       
    if not y == W-1:
        state = matrix[x,y+1]
        if state == ".":
            q.append([x,y+1])
            matrix[x,y+1] = "#"
    
    return matrix, q


while True:
    count +=1
    next_queue = []
    for pos in queue:
        matrix,q = search(pos[0],pos[1],matrix)
        if len(q)!=0:
            next_queue.extend(q)
    queue = next_queue

    white_list = np.where(matrix=='.')
    white_num = len(white_list[0])
    if white_num==0:
        break

print(count)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

input = sys.stdin.readline

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

dist = [[-1] * W for _ in range(H)]
dq = deque((r, c) for r in range(H) for c in range(W) if a[r][c] == '#')


def out_of_range(r, c):
    return not (0 <= r < H and 0 <= c < W)


dr_s = (0, 0, -1, 1)
dc_s = (-1, 1, 0, 0)

d = 0
while dq:
    r, c = dq.popleft()
    d = dist[r][c]
    for dr, dc in zip(dr_s, dc_s):
        nr = r + dr
        nc = c + dc
        if out_of_range(nr, nc): continue
        if a[nr][nc] == '#': continue
        dist[nr][nc] = d + 1
        dq.append((nr, nc))

print(d)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

input = sys.stdin.readline

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

dist = [[-1] * W for _ in range(H)]
dq = deque((r, c) for r in range(H) for c in range(W) if a[r][c] == '#')


def out_of_range(r, c):
    return not (0 <= r < H and 0 <= c < W)


dr_s = (0, 0, -1, 1)
dc_s = (-1, 1, 0, 0)

d = 0
while dq:
    r, c = dq.popleft()
    d = dist[r][c]
    for dr, dc in zip(dr_s, dc_s):
        nr = r + dr
        nc = c + dc
        if out_of_range(nr, nc): continue
        if dist[nr][nc] != -1: continue
        dist[nr][nc] = d + 1
        dq.append((nr, nc))

print(d)

Submission status: Wrong Answer

Solution code:
from collections import deque


def atcoder_input():
    H, W = (int(i) for i in input().split())

    Q = deque()
    for h in range(H):
        l = [j for j in input().split()]
        for w in range(W):
            if list(l[0])[w]=="#":
                Q.append((h,w,0))

    return Q, H, W



def main():
    Q, H, W = atcoder_input()
    searched=[[0]*W for _ in range(H)]
    max_count=0

    while Q:
        h, w, count = Q.popleft()
        for (h2, w2) in ([h+1, w], [h, w+1], [h-1, w], [h, w-1]):
            if h2>=H:
                h2=H-1
            elif h2<=0:
                h2=0
            if w2>=W:
                w2=W-1
            elif w2<=0:
                w2=0
            if searched[h2][w2]==1:
                continue
            else:
                searched[h2][w2]=1
                if count+1 > max_count:
                    max_count = count+1
                Q.append((h2,w2,count+1))

    print(max_count)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import itertools
h, w = map(int, input().split())

blacks = set()
for x in range(h):
    for y, masu in enumerate(input()):
        if masu == '#':
            blacks.add((x, y))

for cnt in itertools.count(1):
    additions = list()
    for b_x, b_y in blacks:
        if b_x > 0:
            additions.append((b_x - 1, b_y))
        if b_x < h - 1:
            additions.append((b_x + 1, b_y))
        if b_y > 0:
            additions.append((b_x, b_y - 1))
        if b_y < w - 1:
            additions.append((b_x, b_y + 1))
    blacks = blacks.union(additions)
    if len(blacks) == h * w:
        break

print(cnt)

Submission status: Wrong Answer

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

import queue

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

# direction vector
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]

# 黒マスを列挙 O(H*W)
black_grid = []
for x in range(w):
    for y in range(h):
        if a[y][x] == "#":
            black_grid += [ (x, y, 0) ]

# 訪れたかどうかの情報を持つ bool 値
is_visited = [ [False for _ in range(w)] for __ in range(h) ]

q = queue.Queue()

# 各黒マスを queue に入れる
for point in black_grid:
    q.put(point)

ans = 0
while not q.empty():
    # queue の先頭を取り出す
    x, y, cnt = q.get()
    ans = max(ans, cnt)
    # 4方向にループ
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if nx < 0 or w <= nx or ny < 0 or h <= ny:
            continue

        if is_visited[ny][nx] == False:
            if a[ny][nx] == ".":
                a[ny][nx] = "#"
                q.put( (ny, nx, cnt+1) )

            is_visited[ny][nx] = True

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
G = ''.join([input() for _ in range(H)])
dist = [0]*(H*W)
B = deque()
for i, g in enumerate(G):
    if g == '#':
        B.append(i)
visited = set(B)
while B:
    vij = B.pop()
    for dij in (W, -W, 1, -1):
        nij = vij + dij
        if not (0 <= nij < H*W) or nij in visited or G[nij] == '#':
            continue
        visited.add(nij)
        dist[nij] = 1 + dist[vij]
        B.appendleft(nij)
print(max(dist))

Submission status: Wrong Answer

Solution code:
from collections import deque


def atcoder_input():
    H, W = (int(i) for i in input().split())

    Q = deque()
    for h in range(H):
        l = [j for j in input().split()]
        for w in range(W):
            if list(l[0])[w]=="#":
                Q.append((h,w,0))

    return Q, H, W



def main():
    Q, H, W = atcoder_input()
    searched=[]
    max_count=0
    while Q:
        h, w, count = Q.popleft()
        for (h2, w2) in ([h+1, w], [h, w+1], [h-1, w], [h, w-1]):
            if h2>=H:
                h2=H-1
            elif h2<=0:
                h2=0
            if w2>=W:
                w2=W-1
            elif w2<=0:
                w2=0
            if [h2,w2] in searched:
                continue
            else:
                searched.append([h2,w2])
                if count+1 > max_count:
                    max_count = count+1
                Q.append((h2,w2,count+1))

    print(max_count)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import copy
import sys
X = [int(i) for i in input().split()]
A = [[s=="#" for s in input()] for _ in range(X[0])]
queue = [(i,j) for i in range(X[0]) for j in range(X[1]) if A[i][j]]
end = []
for n in range(0,10):
    if len(queue) == 0:
        break
    tmp = []
    for q in queue:
        i,j = q[0],q[1]
        up = max(0, i-1)
        down = min(i+1, X[0]-1)
        left = max(0, j-1)
        right = min(j+1, X[1]-1)
        A[up][j] = A[down][j] = A[i][left] = A[i][right] = True
        tmp += [(up,j),(down,j),(i,left),(i,right)]
    end += queue
    end = list(set(end))
    queue = [t for t in set(tmp) if t not in end]
print(n)

Submission status: Wrong Answer

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

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

cnt = 0
while len(queue) > 0:
  i, j = queue.pop()
  if i > 0 and A[i - 1][j] == ".":
    A[i - 1][j] = "#"
    queue.append([i - 1, j])
  if i < H - 1 and A[i + 1][j] == ".":
    A[i + 1][j] = "#"
    queue.append([i + 1, j])
  if j > 0 and A[i][j - 1] == ".":
    A[i][j - 1] = "#"
    queue.append([i, j - 1])
  if j < W - 1 and A[i][j + 1] == ".":
    A[i][j + 1] = "#"
    queue.append([i, j + 1])
  
print(cnt)

Submission status: Wrong Answer

Solution code:
import copy
import sys
X = [int(i) for i in input().split()]
A = [[s=="#" for s in input()] for _ in range(X[0])]
queue = [(i,j) for i in range(X[0]) for j in range(X[1]) if A[i][j]]
end = []
for n in range(0,10):
    print(n)
    print(queue)
    if len(queue) == 0:
        break
    tmp = []
    for q in queue:
        i,j = q[0],q[1]
        up = max(0, i-1)
        down = min(i+1, X[0]-1)
        left = max(0, j-1)
        right = min(j+1, X[1]-1)
        A[up][j] = A[down][j] = A[i][left] = A[i][right] = True
        tmp += [(up,j),(down,j),(i,left),(i,right)]
    end += queue
    end = list(set(end))
    print(end)
    queue = [t for t in set(tmp) if t not in end]
print(n)

Submission status: Wrong Answer

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

y  = [h*W + w for h in range(H) for w in range(W) if l[h][w]=="#"]
s = [set(y)]

xy = set([i for i in range(H*W)])

b = [-1,1,W,-W,0]

for x in range(H*W):
    s.append(set([i+ii for ii in b for i in s[x] if not ((i%W == 0 and ii == -1) or (i%W == W-1 and ii == 1))]))
    if len(xy-s[x+1]) == 0:
        print(x+1)
        break

Submission status: Wrong Answer

Solution code:
def solve():
    H,W=list(map(int,input().split(' ')))
    darker =[]
    cnt = 0
    white_list=[]
    for i in range(H):
        darker.append(list(input()))
    for i in range(H):
        darker[i].insert(0,'.')
        darker[i].append('.')
    darker.insert(0,['.' for i in range(W+2)])
    darker.append(['.' for i in range(W+2)])
    for i in range(1,H+1):
        for j in range(1,W+1):
            if darker[i][j]=='.':
                white_list.append([i,j])
    while True:
        tmp=[]
        for i,j in white_list:
            if darker[i-1][j] =='#' or darker[i][j-1]=='#' or darker[i+1][j] =='#' or darker[i][j+1] =='#':
                tmp.append([i,j])
        for i,j in tmp:
            darker[i][j] ='#'
        white_list = [i for i in white_list if not(i in tmp)]
        cnt +=1
        if len(white_list)==0:
            break



    return cnt

print(solve())

Submission status: Wrong Answer

Solution code:
#ACの方の(備忘)
import numpy as np
 
H, W = map(int, input().split())
A = tuple(input() for _ in range(H))
 
INF = H * W
 
dp = np.full((H, W), INF, dtype=np.int)
 
for i in range(H):
	for j in range(W):
		dp[i, j] = 0 if A[i][j] == '#' else dp[i, j]
        
print(dp)
        
for i in range(1, H):
	dp[i, :] = np.minimum(dp[i, :], dp[i-1, :] + 1)
print(dp)
for i in range(0, H-1)[::-1]:
	dp[i, :] = np.minimum(dp[i, :], dp[i+1, :] + 1)
print(dp)
for j in range(1, W):
	dp[:, j] = np.minimum(dp[:, j], dp[:, j-1] + 1)
print(dp)
for j in range(0, W-1)[::-1]:
	dp[:, j] = np.minimum(dp[:, j], dp[:, j+1] + 1)
print(dp)

print(np.max(dp))

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int,input().split())
alist = [input().strip() for i in range(h)]
dxy = [(0,1),(1,0),(0,-1),(-1,0)]

INF = 99999
dp = [[INF]*w for i in range(h)]
q = deque()
for y, row in enumerate(alist):
  for x, c in enumerate(row):
    if c=='#':
      dp[y][x] = 0
      q.append((x,y))

while q:
  x, y = q.popleft()
  d = dp[y][x]
  for dx, dy in dxy:
    nx, ny = x+dx, y+dy
    if not 0 <= nx < w:
      continue
    if not 0 <= ny < h:
      continue
    if dp[ny][nx] <= d+1:
      continue
    dp[ny][nx] = d+1
    q.append((nx,ny))
  print(dp)

print(max(max(row) for row in dp))

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
check1 = []

for i in range(h):
    check1.append([])
    A = list(input())
    for j in range(w):
        a = A[j]
        if a == "#":
            check1[i].append(0)
        else:
            check1[i].append(pow(10, 5))

#for i in range(h):
    for j in range(1, w):
            check1[i][j] = check1[i][j] * (check1[i][j - 1] + 1)
            check1[i][w - j - 1] = min(check1[i][w - j - 1] * (check1[i][w - j] + 1), check1[i][w - j - 1])
ans = 1
#print(check1)
for j in range(w):
    for i in range(1, h):
        check1[i][j] = check1[i][j] * (check1[i - 1][j] + 1)
        check1[h - i - 1][j] = min((check1[h - i][j] + 1), check1[h - i - 1][j])
        ans = max(ans, check1[i][j])
print(ans - 1)

Submission status: Wrong Answer

Solution code:
import copy
import sys
X = [int(i) for i in input().split()]
A = [[s=="#" for s in input()] for _ in range(X[0])]
queue = [(i,j) for i in range(X[0]) for j in range(X[1]) if A[i][j]]
n = 0
end = []
for n in range(0,10):
    tmp = []
    for q in queue:
        i,j = q[0],q[1]
        up = max(0, i-1)
        down = min(i+1, X[0]-1)
        left = max(0, j-1)
        right = min(j+1, X[1]-1)
        A[up][j] = A[down][j] = A[i][left] = A[i][right] = True
        tmp += [(up,j),(down,j),(i,left),(i,right)]
    end += queue
    queue = [t for t in set(tmp) if t not in end]
    if len(queue) == 0:
        break
print(n)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A = []
for i in range(H):
    s = input()
    A.append(list(s))
q = []
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            q.append((i,j))
ans = -1
print(1)
"""
while q != []:
    p = []
    for nx,ny in q:
        for py,px in [(ny-1,nx),(ny,nx-1),(ny+1,nx),(ny,nx+1)]:
            if 0<=py<H and 0<=px<W:
                if A[py][px] == ".":
                    A[py][px] = "#"
                    p.append((py,px))
    q = p
    ans += 1
print(ans)"""

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
kuro = []
siro = []
A = []
kyoris = [1]

def kyori(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def search(poj, pkyori):
    ckyori = pkyori - 1
    i , j = poj[0], poj[1]
    while(True):
        for ki in range(ckyori + 1):
            kj = ckyori - abs(ki)
            for di, dj in [(ki, kj), (ki, -kj), (-ki, kj), (-ki, -kj)]:
                ci, cj = i + di, j + dj
                if 0 <= ci < h and 0 <= cj < w:
                    if A[ci][cj] == "#":
                        return ckyori
        ckyori += 1


for i in range(h):
    Ai = input()
    A.append( [Aij for Aij in Ai])
    for j, Aij in enumerate(Ai):
        if Aij == "#":
            kuro.append((i, j))
        else:
            siro.append((i, j))

for si in siro:
    kyoris.append(search(si, kyoris[-1]))

print(max(kyoris))

Submission status: Wrong Answer

Solution code:
import numpy as np
a = input().rstrip().split(' ')
mat= np.zeros((int(a[0])+2,int(a[1])+2))

for i in range(int(a[0])):
  s = input()
  for j in range(len(s)):
    if s[j] == '#':
      mat[i+1,j+1]=1
GGG=np.zeros((int(a[0])+2,int(a[1])+2))
loop=1
k=0
while loop==1:
  k=k+1
  for i in range(int(a[0])):
    for j in range(len(s)):
      i2=i+1
      j2=j+1
      if mat[i2,j2]==1:
        GGG[i2-1,j2]=1
        GGG[i2+1,j2]=1
        GGG[i2,j2-1]=1
        GGG[i2,j2+1]=1
  mat=GGG+mat
  mat[mat>1]=1
  if np.min(mat[1:-1,1:-1])==1:
    loop=0    
print(k)

Submission status: Wrong Answer

Solution code:
H, W = map(int,input().split())

table = []
for _ in range(H):
    table.append(["k"] + list(input()) + ["k"])
    
table = [["k"]*(W+2)] + table + [["k"]*(W+2)]

import queue
q = queue.Queue()

min_memo = [[None]*(W+2) for _ in range(H+2)]

for y, r in enumerate(table):
    for x, c in enumerate(r):
        if c == "#":
            q.put([y,x,0])
            min_memo[y][x] = 0

while True:
    if q.empty():
        print(cnt)
        break
    y, x, cnt = q.get()
    print(y,x,cnt)
    for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
        if table[y+dy][x+dx] == ".":
            if min_memo[y+dy][x+dx] == None:
                min_memo[y+dy][x+dx] = cnt+1
                q.put([y+dy, x+dx, cnt+1])

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A = []
for i in range(H):
    s = input()
    A.append(list(s))
q = []
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            q.append((i,j))
ans = -1
while q != []:
    p = []
    for nx,ny in q:
        for py,px in [(ny-1,nx),(ny,nx-1),(ny+1,nx),(ny,nx+1)]:
            if 0<=py<H and 0<=px<W:
                if A[py][px] == ".":
                    A[py][px] = "#"
                    p.append((py,px))
    q = p
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
import sys
X = [int(i) for i in input().split()]
A = [[s=="#" for s in input()] for _ in range(X[0])]
queue = [(i,j) for i in range(X[0]) for j in range(X[1]) if A[i][j]]
n = 0
blacklist = [q for q in queue]
for n in range(0,10):
    for q in queue:
        i,j = q[0],q[1]
        up = max(0, i-1)
        down = min(i+1, X[0]-1)
        left = max(0, j-1)
        right = min(j+1, X[1]-1)
        A[up][j] = A[down][j] = A[i][left] = A[i][right] = True
        blacklist += [q]
    queue = [(i,j) for i in range(X[0]) for j in range(X[1]) if A[i][j] and ((i,j) not in blacklist)]
    if len(queue) == 0:
        break
print(n)

Submission status: Wrong Answer

Solution code:
import sys


def input():
    return sys.stdin.readline()[:-1]


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

A = [[1 if s == "#" else 0 for s in input()] for i in range(H)]

lu = [[1<<20] * (W+2) for j in range(H + 2)]

for ii in range(H * W):
    i = ii // W + 1
    j = ii % W + 1
    lu[i][j] = min(lu[i - 1][j], lu[i][j - 1]) + 1
    if A[i - 1][j - 1]:
        lu[i][j] = 0
    elif j < W and A[i - 1][j]:
        lu[i][j] = 1

for ii in range(H * W):
    i = H - ii // W
    j = W - ii % W
    lu[i][j] = min(lu[i + 1][j] + 1, lu[i][j + 1] + 1, lu[i][j])
print("hoge")
# dist = max(sum([l[1:-1] for l in lu[1:-1]], []))
# print(dist)

Submission status: Wrong Answer

Solution code:
import numpy as np

h,w = map(int,input().split())
data_t = []
for _ in range(h):
    list_ = str(input())
    data_t.append(list_)

data = np.zeros((3*h,3*w),dtype=np.int)
datamap = np.ones((3*h,3*w),dtype=np.int)

datamaplt = np.ones((3*h,3*w),dtype=np.int)
datamaplt = datamaplt*(10)
datamaprt = np.ones((3*h,3*w),dtype=np.int)
datamaprt = datamaprt*(10)
datamaplb = np.ones((3*h,3*w),dtype=np.int)
datamaplb = datamaplb*(10)
datamaprb = np.ones((3*h,3*w),dtype=np.int)
datamaprb = datamaprb*(10)

for i in range(h):
    for  j in range(w):
        if data_t[i][j] == "#":
            data[h+i,w+j] = 1
        datamaplt[h+i,w+j] = 0
        datamaprt[h+i,w+j] = 0
        datamaplb[h+i,w+j] = 0
        datamaprb[h+i,w+j] = 0
        

for i in range(h):
    for  j in range(w):
        ii = i+h
        jj = j+w
        if data[ii,jj] == 0:
            fromtop = datamaplt[ii-1,jj]+1
            fromleft = datamaplt[ii,jj-1]+1
            datamaplt[ii,jj] = min(fromtop,fromleft)

    for  j in range(w-1,-1,-1):
        ii = i+h
        jj = j+w
        if data[ii,jj] == 0:
            fromtop = datamaprt[ii-1,jj]+1
            fromright = datamaprt[ii,jj+1]+1
            datamaprt[ii,jj] = min(fromtop,fromright)

"""for i in range(h-1,-1,-1):
    for  j in range(w):
        ii = i+h
        jj = j+w
        if data[ii,jj] == 0:
            frombottom = datamaplb[ii+1,jj]+1
            fromleft = datamaplb[ii,jj-1]+1
            datamaplb[ii,jj] = min(frombottom,fromleft)

    for  j in range(w-1,-1,-1):
        ii = i+h
        jj = j+w
        if data[ii,jj] == 0:
            frombottom = datamaprb[ii+1,jj]+1
            fromright = datamaprb[ii,jj+1]+1
            datamaprb[ii,jj] = min(fromright,frombottom)"""
            
ans = 0  
for i in range(h):
    for  j in range(w):
        ii = i+h
        jj = j+w
        """if min(datamaplt[ii,jj],datamaprt[ii,jj],datamaplb[ii,jj],datamaprb[ii,jj]) > ans:
            ans =  min(datamaplt[ii,jj],datamaprt[ii,jj],datamaplb[ii,jj],datamaprb[ii,jj])"""
            
print(ans)

Submission status: Wrong Answer

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

non=3000
import numpy as np
b=np.ones((h,w),dtype=int)*non
a=np.zeros((h,w),dtype=int)
for i in range(h):
    for j in range(w):
        if A[i][j]=='#':
            a[i][j]=1

ans=0
sankaku=np.array(np.arange(w,dtype=int))

u=np.ones((h,w),dtype=int)*non
for i in range(h):
    l=np.ones(w,dtype=int)*non
    for j in range(w):
        if a[i][j]:
            l[j:]=sankaku[:w-j]
    r=non
    for j in range(w-1,-1,-1):
        if a[i][j]:
            b[i][j]=0
            r=0
        elif j<w-1 and r!=non:
            r+=1
        b[i][j]=min(l[j],r)
    if i>0:
        u[i]=np.min((b[i],b[i-1]+1),axis=0)
        b[i]=u[i]
d=np.ones(w,dtype=int)*non
for i in range(h-1,-1,-1):
    if i<h-1:
        d=np.min((b[i],b[i+1]+1),axis=0)
    b[i]=np.min((u[i],d),axis=0)
    ans=max(ans,np.max(b[i]))
print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
ans=0
for c in range(max(h,w)*2):
  d=0
  for i in range(h):
    for j in range(w):
      if a[i][j]=="#":
        if i!=0:
          if a[i-1][j]!=0:
            a[i-1][j]="#"
            d=1
        if j!=0:
          if a[i][j-1]!=0:
            a[i][j-1]="#"
            d=1
        if i!=h-1:
          if a[i+1][j]!=0:
            a[i+1][j]="#"
            d=1
        if j!=w-1:
          if a[i][j+1]!=0:
            a[i][j+1]="#"
            d=1
        a[i][j]=0
  if d==1:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
G = [list(input()) for _ in range(H)]
ans = 0


def change(x, y):
    if x < 0 or x >= W:
        return False
    if y < 0 or y >= H:
        return False

    if G[y][x] == ".":
        G[y][x] = "@"
        return False
    elif G[y][x] == "#":
        return True


def search(x, y):
    global ans
    count = 0
    sharp = 0

    while sharp == 0:
        if count == 0:
            G[y][x] = "@"
        else:
            for i in range(count):
                if change(x+count-i, y+i) or change(x-i, y+count-i) or \
                    change(x-count+i, y-i) or change(x+i, y-count+i):
                    sharp += 1

        if count > ans:
            ans = count

        count += 1


for i in range(H):
    for j in range(W):
        if G[i][j] == ".":
            search(j, i)

print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
ans=0
for c in range(max(h,w)*2):
  d=0
  for i in range(h):
    for j in range(w):
      if a[i][j]=="#":
        d=1
        if i!=0:
          if a[i-1][j]!=0:
            a[i-1][j]="#"
        if j!=0:
          if a[i][j-1]!=0:
            a[i][j-1]="#"
        if i!=h-1:
          if a[i+1][j]!=0:
            a[i+1][j]="#"
        if j!=w-1:
          if a[i][j+1]!=0:
            a[i][j+1]="#"
        a[i][j]=0
  if d==1:
    ans+=1
print(ans)