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 collections import deque
H, W = map(int, input().split())
C = [list(input()) for i in range(H)]
X = [1,0,-1,0]
Y = [0,-1,0,1]
INF = 10**9

Q = deque()
dist = [[INF]*W for i in range(H)]

for x in range(W):
  for y in range(H):
    if C[y][x] == "#":
      Q.append((y,x))
      dist[y][x] = 0
      while Q:
        y,x = Q.popleft()
        for i in range(4):
          nx = x + X[i]
          ny = y + Y[i]
          if (0 <= nx < W) and (0 <= ny < H) and dist[y][x]+1 <= dist[ny][nx] and (C[ny][nx] != "#"):
            dist[ny][nx] = dist[y][x] + 1
            Q.append((ny,nx))
ans = 0
for i in range(H):
  ans = max(ans,max(dist[i]))
print(ans)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
a=["."*(3*w)]*h
c=0
ans=0
for _ in range(h):
    k = "."*w + input() + "."*w
    a.append(k)
b=["."*(3*w)]*h
a+=b
m=0
for i in range(h,2*h):
    for j in range(w,2*w):
        if a[i][j]==".":
            start=1
            while(1):
                k=""
                for l in range(start+1):
                    k+=a[i-l][j-start:j+start+1]
                    k+=a[i+l][j-start:j+start+1]
                if "#" in k:
                    break
                start+=1
            if start>m:
                m=start
print(m)

Submission status: Wrong Answer

Solution code:
from collections import deque


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

visited = [[False]*w for i in range(h)]
q = deque([])
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
while q:
    i, j, times = q.popleft()
    ans = max(times, ans)

    for next_i, next_j in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
        if 0 <= next_i < h and 0 <= next_j < w and not visited[next_i][next_j]:
            visited[i][j] = True
            q.append((next_i, next_j, times + 1))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

input = sys.stdin.readline
H,W = map(int,input().split())
# 周りに壁を、0,1化、壁を0で持つ
grid = np.zeros((H+2,W+2),dtype=np.bool)
grid[1:-1,1:-1] = (np.array([list(input().rstrip()) for _ in range(H)]) == '.')

Submission status: Wrong Answer

Solution code:
import collections
h,w = map(int,input().split())
q = collections.deque()
ans = 0
A = []
for i in range(h):
    s = input()
    L = []
    for j in range(w):
        L.append(s[j])
        if s[j] == '#':
            q.append([i,j])
    A.append(L)
dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]
t = len(q)
while len(q) > 0:
    cur = q.popleft()
    for i in range(4):
        y = cur[0]+dy_dx[i][0]
        x = cur[1]+dy_dx[i][1]
        if 0 <= y < h and 0 <= x < w:
            if A[y][x] == '.':
                A[y][x] = '#'
                q.append([y,x])
    if t > 0:
        t -= 1
    else:
        t = len(q)
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

from collections import deque
import sys
input = sys.stdin.readline

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

field = [[0] * W for _ in range(H)]
field_dist = [[2000] * W for _ in range(H)]
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            field[i][j] = 1
            init_h = i
            init_w = j
            
edges = [[[] for _ in range(W)] for _ in range(H)]
d = deque([[init_h, init_w]])
reverse_d = deque()
while len(d) > 0:
    cur_h, cur_w = d.popleft()
    init_d = abs(init_h - cur_h) + abs(init_w - cur_w)
    
    if field[cur_h][cur_w] == 1:
        field_dist[cur_h][cur_w] = 0
    
    for dh, dw in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        if (cur_h + dh) >= 0 and (cur_h + dh) < H and (cur_w + dw) >= 0 and (cur_w + dw) < W:
            next_d = abs(init_h - (cur_h + dh)) + abs(init_w - (cur_w + dw))
            if next_d > init_d:
                field_dist[cur_h+dh][cur_w+dw] = min(field_dist[cur_h+dh][cur_w+dw], field_dist[cur_h][cur_w]+1)
                d.append([cur_h+dh, cur_w+dw])
                reverse_d.append([cur_h+dh, cur_w+dw, cur_h, cur_w])
         
max_dist = 0
while len(reverse_d) > 0:
    s_h, s_w, d_h, d_w = reverse_d.pop()
    if field_dist[s_h][s_w] + 1 < field_dist[d_h][d_w]:
        field_dist[d_h][d_w] = field_dist[s_h][s_w] + 1
    max_dist = max(max_dist, field_dist[d_h][d_w])
   
print(max_dist)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

from collections import deque

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

field = [[0] * W for _ in range(H)]
field_dist = [[2000] * W for _ in range(H)]
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            field[i][j] = 1
            init_h = i
            init_w = j
            
edges = [[[] for _ in range(W)] for _ in range(H)]
d = deque([[init_h, init_w]])
reverse_d = deque()
while len(d) > 0:
    cur_h, cur_w = d.popleft()
    init_d = abs(init_h - cur_h) + abs(init_w - cur_w)
    
    if field[cur_h][cur_w] == 1:
        field_dist[cur_h][cur_w] = 0
    
    for dh, dw in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        if (cur_h + dh) >= 0 and (cur_h + dh) < H and (cur_w + dw) >= 0 and (cur_w + dw) < W:
            next_d = abs(init_h - (cur_h + dh)) + abs(init_w - (cur_w + dw))
            if next_d > init_d:
                field_dist[cur_h+dh][cur_w+dw] = min(field_dist[cur_h+dh][cur_w+dw], field_dist[cur_h][cur_w]+1)
                d.append([cur_h+dh, cur_w+dw])
                reverse_d.append([cur_h+dh, cur_w+dw, cur_h, cur_w])
         
max_dist = 0
while len(reverse_d) > 0:
    s_h, s_w, d_h, d_w = reverse_d.pop()
    if field_dist[s_h][s_w] + 1 < field_dist[d_h][d_w]:
        field_dist[d_h][d_w] = field_dist[s_h][s_w] + 1
    max_dist = max(max_dist, field_dist[d_h][d_w])
   
print(max_dist)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
field=[list(input()) for _ in range(h)]
graph=[[float('inf')]*w for _ in range(h)]
queue=deque()
for i in range(h):
    for j in range(w):
        if field[i][j]=='#':
            queue.append([i,j])
            graph[i][j]=0

def bfs():
    x,y=queue.popleft()
    for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=x+dx<h and 0<=y+dy<w:
            graph[x+dx][y+dy]=graph[x][y]+1
            queue.append([x+dx,y+dy])
count=0
a=float('inf')
while a==float('inf'):
    bfs()
    print(graph)
    a=max(max(graph[s]) for s in range(h))
print(a)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A = [list(input()) for h in range(H)]
q,p = [],[]
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            p.append([h-1,w])
            p.append([h+1,w])
            p.append([h,w-1])
            p.append([h,w+1])
ans = 0
while len(p)!=0:
    ans += 1
    q += p
    p.clear()
    while len(q)!=0:
        x,y = q[0][0],q[0][1]
        del q[0]
        if x<0 or x>=H or y<0 or y>=W or A[x][y]=="#":
            continue
        A[x][y] = "#"
        if x-1>=0 and A[x-1][y]!="#":
            p.append([x-1,y])
        if x+1<H and A[x+1][y]!="#":
            p.append([x+1,y])
        if y-1>=0 and A[x][y-1]!="#":
            p.append([x,y-1])
        if y+1<W and A[x][y+1]!="#":
            p.append([x,y+1])
for i in A:
    print(i)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
field=[list(input()) for _ in range(h)]
graph=[[float('inf')]*w for _ in range(h)]
queue=deque()
count=0
for i in range(h):
    for j in range(w):
        if field[i][j]=='#':
            queue.append([i,j])
            graph[i][j]=0

def bfs():
    x,y=queue.popleft()
    for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=x+dx<h and 0<=y+dy<w:
            if graph[x+dx][y+dy]==float('inf'):
                graph[x+dx][y+dy]=graph[x][y]+1
                queue.append([x+dx,y+dy])
while max(max(graph[s]) for s in range(h))==float('inf'):
    bfs()
    print(graph)
print(max(max(graph[s]) for s in range(h)))

Submission status: Wrong Answer

Solution code:
import sys
import re

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

check_list=[]
remove=[]

append=check_list.append
append2=remove.append
for i in range(a[0]):
  b=list(input())
  for j , x in enumerate(b):
    if x == "#":
      append((i+1,j))
      append((i-1,j))
      append((i,j+1))
      append((i,j-1))
      append2((i,j))

for i in range(a[0]):
  append2((i,-1))
  append2((i,a[1]))

for i in range(a[1]):
  append2((-1,i))
  append2((a[0],i))

check_list = set(check_list)-set(remove)
check_list_new=[]
count=1
append3=check_list_new.append
while True:
  if not check_list:
    check_list = set(check_list_new) - set(remove)
    if not check_list:
      break 
    count+=1

  c=check_list.pop()
  append2((c[0],c[1]))

  append3((c[0]+1,c[1]))      
  append3((c[0]-1,c[1]))      
  append3((c[0],c[1]+1))      
  append3((c[0],c[1]-1))   

print(count)

Submission status: Wrong Answer

Solution code:
import sys
import re

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

check_list=[]
remove=[]

for i in range(a[0]):
  b=list(input())
  for j , x in enumerate(b):
    if x == "#":
      check_list.append((i+1,j))
      check_list.append((i-1,j))
      check_list.append((i,j+1))
      check_list.append((i,j-1))
      remove.append((i,j))

for i in range(a[0]):
  remove.append((i,-1))
  remove.append((i,a[1]))

for i in range(a[1]):
  remove.append((-1,i))
  remove.append((a[0],i))

check_list = set(check_list)-set(remove)
check_list_new=[]
count=1
while True:
  if not check_list:
    check_list = set(check_list_new) - set(remove)
    if not check_list:
      break 
    check_list_new=[]
    count+=1

  c=check_list.pop()
  remove.append((c[0],c[1]))

  check_list_new.append((c[0]+1,c[1]))      
  check_list_new.append((c[0]-1,c[1]))      
  check_list_new.append((c[0],c[1]+1))      
  check_list_new.append((c[0],c[1]-1))   


print(count)

Submission status: Wrong Answer

Solution code:
import sys
import re
### 方針
### 黒のマスとの距離を計算し、最大値を求める

# 標準入力を受け取る
##  1行目だけ単体で取得。残りの行列把握のため
##  a[0]：行数、a[1]：列数
a = list(map(int,input().split()))

##  残りの行を取得する
b=[list(input()) for i in range(a[0])]

check_list=[]
remove=[]
for i in range(a[0]):
  remove.append((i,-1))
  remove.append((i,a[1]))

for i in range(a[1]):
  remove.append((-1,i))
  remove.append((a[0],i))

for i in range(a[0]):
#  print(b[i])
  for j, x in enumerate(b[i]):
    if x == "#":
      check_list.append((i+1,j))
      check_list.append((i-1,j))
      check_list.append((i,j+1))
      check_list.append((i,j-1))
      remove.append((i,j))
      remove.append((i+1,j))
      remove.append((i-1,j))
      remove.append((i,j+1))
      remove.append((i,j-1))
#      print(j)

#print(check_list)

check_list_new=[]
count=1
while True:
  if not check_list:
    check_list = set(check_list_new) - set(remove)
    if not check_list:
      break 
    check_list_new=[]
    count+=1

  c=check_list.pop()
  remove.append((c[0],c[1]))

  if c[0] < 0 or c[0] == a[0] or c[1] < 0 or c[1] == a[1] :
    continue
  if b[c[0]][c[1]] != "#":
    b[c[0]][c[1]] = "#"
    check_list_new.append((c[0]+1,c[1]))      
    check_list_new.append((c[0]-1,c[1]))      
    check_list_new.append((c[0],c[1]+1))      
    check_list_new.append((c[0],c[1]-1))   


print(count)

Submission status: Wrong Answer

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

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)] + [[True]+[False]*W+[True] for _ in range(H)] + [[True]*(W+2)]# '#'からの距離

for i in range(1,H+1):
  for j,c in enumerate(input(),1):
    if c == '#':
      visited[i][j] = True
      q.append((i,j))
"""
ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
      xx = x+dx
      yy = y+dy
      if not visited[xx][yy]:
        visited[xx][yy] = True
        qq.append((xx,yy))
  q = qq
  
print(ans)
"""

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
h,w = map(int,input().split())

q = []
reached = [[True]*(w+2)]
for i in range(1, h+1):
    reached.append([True] + [s == '#' for s in list(input())] + [True])
    for j in range(1,w+1):
        if reached[i][j]: q.append((i,j))
reached.append([True]*(w+2))

res = 0
while 1:
    qq = []
    for k,l in q:
        if not reached[k+1][l]:
            qq.append((k+1, l))
            reached[k+1][l] = True
        if not reached[k][l+1]:
            qq.append((k, l+1))
            reached[k][l+1] = True
        if not reached[k-1][l]:
            qq.append((k-1, l))
            reached[k-1][l] = True
        if not reached[k][l-1]:
            qq.append((k, l-1))
            reached[k][l-1] = True

    q = qq
    if len(q) == 0:
        break
    else:
        pass

    res += 1

print(res-1)

Submission status: Wrong Answer

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

for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            stack.append([i, j, 0])



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


while len(stack)!=0:
    now_point=stack.pop(0)
    for i in range(4):
        target_h=now_point[0]+dx[i]
        target_w=now_point[1]+dy[i]
        if 0<=target_h<h and 0<=target_w<w:
            if a[target_h][target_w]==".":
                now_point[2]=now_point[2]+1
                a[target_h][target_w]="#"
                stack.append([target_h, target_w, now_point[2]])

print(now_point[2])

Submission status: Wrong Answer

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

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



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


while len(stack)!=0:
    now_point=stack.pop(0)
    for i in range(4):
        target_h=now_point[0]+dx[i]
        target_w=now_point[1]+dy[i]
        if 0<=target_h<h and 0<=target_w<w:
            if a[target_h][target_w]==".":
                need_visited[target_h][target_w]=need_visited[now_point[0]][now_point[1]]+1
                a[target_h][target_w]="#"
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans, need_visited[i][j])
print(ans)

Submission status: Wrong Answer

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

from collections import deque


def solve():
    H, W = map(int, input().split())
    # mass = [[False] * W for _ in range(H)]
    # queue1 = deque([])
    # queue2 = deque([])
    queue1 = []
    queue2 = []
    mass = []
    mass.append([False] * (W + 2))  # 外枠
    for Hi in range(1, H + 1):
        mass.append([False] + [s == '.' for s in list(input())] + [False])
        for Wi in range(1, W + 1):
            if not mass[Hi][Wi]:
                queue1.append((Hi, Wi))
    mass.append([False] * (W + 2))  # 外枠
    import datetime
    d = datetime.datetime.now()
    count = -1
    while True:
        # print('count: {}, queue:{}'.format(count, len(queue1)))
        if len(queue1) == 0:
            break
        for h, w in queue1:
            # left
            if mass[h][w - 1]:
                mass[h][w - 1] = False
                queue2.append((h, w - 1))
            # right
            if mass[h][w + 1]:
                mass[h][w + 1] = False
                queue2.append((h, w + 1))
            # top
            if mass[h + 1][w]:
                mass[h + 1][w] = False
                queue2.append((h + 1, w))
            # button
            if mass[h - 1][w]:
                mass[h - 1][w] = False
                queue2.append((h - 1, w))

        count += 1
        queue1 = queue2
        queue2 = []
    print(count)

    print(datetime.datetime.now() - d)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

H, W = map(int, input().split())
A = [[0]*W for i in range(H)]
ans = [[0]*W for i in range(H)]
goal = [['#']*W for i in range(H)]
counter = 0
for i in range(H):
        B = input()
        for j in range(W):
                A[i][j] = B[j]

for _ in range(max(H, W)):
        for i in range(H):
                for j in range(W):
                        if A[i][j] == '#':
                                ans[i][j] = "#"
                                if i != H-1:
                                        ans[i+1][j] = "#"
                                if i != 0:
                                        ans[i-1][j] = "#"
                                if j != W-1:
                                        ans[i][j+1] = "#"
                                if j != 0:
                                        ans[i][j-1] = "#"
        A = ans
        counter += 1
        for i in range(H):
                print(ans[i])
        if A == goal:
                break
print(counter)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

grid = [[v for v in input()[:-1]] for _ in range(H)]

Q = []
cnt = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] == "#":
            Q.append([i, j])
            cnt += 1

DX = [-1, 1, 0, 0]
DY = [0, 0, -1, 1]
d = 0
while cnt < H*W:
    d += 1
    tmp = []
    for sx, sy in Q:
        for x, y in zip(DX, DY):
            new_x = sx+x
            new_y = sy+y
            if 0 <= new_x < H and 0 <= new_y < W:
                if grid[new_x][new_y] == ".":
                    grid[new_x][new_y] == "#"
                    tmp.append([new_x, new_y])
                    cnt += 1
            else:
                continue
    Q = tmp
print(d)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

grid = [[v for v in input()[:-1]] for _ in range(H)]

Q = []
cnt = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] == "#":
            Q.append([i, j])
            cnt += 1

DX = [-1, 1, 0, 0]
DY = [0, 0, -1, 1]
current_dist = 0
while cnt < H*W:
    current_dist += 1
    tmp = []
    for sx, sy in Q:
        for x, y in zip(DX, DY):
            new_x = sx+x
            new_y = sy+y
            if 0 <= new_x < H and 0 <= new_y < W:
                if grid[new_x][new_y] == ".":
                    grid[new_x][new_y] == "#"
                    tmp.append([new_x, new_y])
                    cnt += 1
            else:
                continue
    Q = tmp
print(current_dist)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

grid = [[v for v in input()[:-1]] for _ in range(H)]

Q = []
cnt = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] == "#":
            Q.append([i, j])
            cnt += 1

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
current_dist = 0
while cnt < H*W:
    current_dist += 1
    tmp = []
    for sx, sy in Q:
        for x, y in zip(dx, dy):
            new_x = sx+x
            new_y = sy+y
            if 0 <= new_x < H and 0 <= new_y < W:
                if grid[new_x][new_y] == ".":
                    grid[new_x][new_y] == "#"
                    tmp.append([new_x, new_y])
                    cnt += 1
            else:
                continue
    Q = tmp
print(current_dist)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

grid = [[v for v in input()[:-1]] for _ in range(H)]

Q = []
cnt = 0
for row in range(H):
    for col in range(W):
        if grid[row][col] == "#":
            Q.append([row, col])
            cnt += 1

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
current_dist = 0
while cnt < H*W:
    current_dist += 1
    tmp = []
    for sx, sy in Q:
        for x, y in zip(dx, dy):
            new_x = sx+x
            new_y = sy+y
            if 0 <= new_x < H and 0 <= new_y < W:
                if grid[new_x][new_y] == ".":
                    grid[new_x][new_y] == "#"
                    tmp.append([new_x, new_y])
                    cnt += 1
            else:
                continue
    Q = tmp
print(current_dist)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

grid = [[v for v in input()[:-1]] for _ in range(H)]

Q = []
cnt = 0
for row in range(H):
    for col in range(W):
        if grid[row][col] == "#":
            Q.append([row, col])
            cnt += 1

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
current_dist = 0
while cnt < H*W:
    current_dist += 1
    tmp = []
    for sx, sy in Q:
        for x, y in zip(dx, dy):
            new_x = sx+x
            new_y = sy+y
            if 0 <= new_x < H and 0 <= new_y < W:
                if grid[new_x][new_y] == ".":
                    grid[new_x][new_y] == "#"
                    tmp.append([new_x, new_y])
                    cnt += 1
            else:
                continue
    Q = tmp
print(current_dist)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

grid = [[v for v in input()[:-1]] for _ in range(H)]

Q = []
cnt = 0
for row in range(H):
    for col in range(W):
        if grid[row][col] == "#":
            Q.append([row, col])
            cnt += 1

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
current_dist = 0
while cnt < H*W:
    current_dist += 1
    tmp = []
    for sx, sy in Q:
        for x, y in zip(dx, dy):
            new_x = sx+x
            new_y = sy+y
            if 0 <= new_x < H and 0 <= new_y < W:
                if grid[new_x][new_y] == ".":
                    grid[new_x][new_y] == "#"
                    tmp.append([new_x, new_y])
                    cnt += 1
    Q = tmp
print(current_dist)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

grid = [[v for v in input()[:-1]] for _ in range(H)]
dist = [[float('inf')]*W for _ in range(H)]

Q = []
cnt = 0
for row in range(H):
    for col in range(W):
        if grid[row][col] == "#":
            dist[row][col] = 0
            Q.append([row, col])
            cnt += 1

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
current_dist = 0
while cnt < H*W and Q:
    current_dist += 1
    tmp = []
    for sx, sy in Q:
        for x, y in zip(dx, dy):
            new_x = sx+x
            new_y = sy+y
            if 0 <= new_x < H and 0 <= new_y < W:
                if dist[new_x][new_y] == float('inf'):
                    dist[new_x][new_y] = current_dist
                    tmp.append([new_x, new_y])
                    cnt += 1
    Q = tmp
print(max(max(dist)))

Submission status: Wrong Answer

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

grid = []
blacks = set()
for i in range(H):
    row = list(input(""))
    grid.append(row)

    for idx, r in enumerate(row):
        if r == "#":
            blacks.add((i, idx))


def if_black_next(grid, y, x, height, width):
    t = y-1
    b = y+1
    l = x-1
    r = x+1
    if t >= 0:
        if grid[t][x] == ".":
            return True
    if b < height:
        if grid[b][x] == ".":
            return True
    if l >= 0:
        if grid[y][l] == ".":
            return True
    if r < width:
        if grid[y][r] == ".":
            return True
    return False


c = 0
while len(blacks) > 0:
    c += 1

    new_blacks = set()
    while len(blacks) > 0:
        b = blacks.pop()

        top = b[0]-1
        bottom = b[0]+1
        left = b[1]-1
        right = b[1]+1

        if top >= 0:
            grid[top][b[1]] = "#"
            if if_black_next(grid, top, b[1], H, W):
                new_blacks.add((top, b[1]))
        if bottom < H:
            grid[bottom][b[1]] = "#"
            if if_black_next(grid, bottom, b[1], H, W):
                new_blacks.add((bottom, b[1]))
        if left >= 0:
            grid[b[0]][left] = "#"
            if if_black_next(grid, b[0], left, H, W):
                new_blacks.add((b[0], left))
        if right < W:
            grid[b[0]][right] = "#"
            if if_black_next(grid, b[0], right, H, W):
                new_blacks.add((b[0], right))

    blacks = new_blacks

print(c)

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    s=input().split()
    H=int(s[0])
    W=int(s[1])
    table=np.zeros((H,W),dtype=int)
    for i in range(H):
        s=input()
        for j in range(W):
            if s[j]=='.':
                table[i][j]=0
            else:
                table[i][j]=1
    count=0
    while True:
        print(table)
        print()
        table2=table.copy()
        if (np.sum(table == 1))==H*W:
            break
        else:
            count+=1
            for i in range(H):
                for j in range(W):
                    if table[i][j]==1:
                        try:
                            table2[i-1][j]=1
                        except:
                            pass
                        try:
                            table2[i+1][j]=1
                        except:
                            pass
                        try:
                            table2[i][j-1]=1
                        except:
                            pass
                        try:
                            table2[i][j+1]=1
                        except:
                            pass
            table=table2

    print(count)
main()

Submission status: Wrong Answer

Solution code:
import numpy as np
H,W=map(int,input().split())
field=np.array([list(input()) for _ in range(H)])
field=np.select([field=='#', field=='.'],[1,0])

turn=0

while True:
	up = np.vstack((field[1:,:], np.zeros(W)))
	down = np.vstack((np.zeros(W), field[:-1,:]))
	left = np.hstack((field[:,1:], np.zeros(H).reshape(-1,1)))
	right = np.hstack((np.zeros(H).reshape(-1,1), field[:,:-1]))
	field = np.where(field+up+down+left+right>0, 1, 0)
	if np.sum(field)==H*W:
		break
	else:
		turn += 1
print(turn)

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()]
  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 black_count < all_count:
    next_steps = [black+cand for black in blacks for cand in cands_H if black >= W and black < all_count-W]
    next_steps.extend([black-1 for black in blacks if black != 0 and black%W != 0])
    next_steps.extend([black+1 for black in blacks if black != all_count-1 and black%W != W-1])
    next_steps = set(next_steps)
    blacks = [i for i in next_steps if 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以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど 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:
      continue
    else:
      break

  print(result)

if __name__ == "__main__":
  main()

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:
#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
print(d)