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: Runtime Error

Solution code:
from collections import deque

h, w = map(int, input().split())
Black = deque([])
White = deque([])
Black_grid = [[-1 for _ in range(w)] for _ in range(h)]

for i in range(h):
    a = str(input())
    for j in range(w):
        if a[j] == '#':
            Black.append([i,j])
            Black_grid[j][i] = 0
        else:
            White.append([i,j])

Move = [[-1,0],[1,0],[0,-1],[0,1]]


while Black:
    now = Black.popleft()
    x = now[0]
    y = now[1]
    for move in Move:
        x_next = x + move[0]
        y_next = y + move[1]
        if x_next < 0 or x_next >= w or y_next < 0 or y_next >= h:
            continue
        elif Black_grid[y_next][x_next] >= 0:
            continue
        else:
            Black.append([x_next, y_next])
            Black_grid[y_next][x_next] = Black_grid[y][x] + 1

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

Submission status: Runtime Error

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

dyx = ((0, 1), (0, -1), (1, 0), (-1, 0))
H, W = map(int, input().split())
edge = ['#'] * (W + 2)
visited = [H+W]*(H*W)
field = [edge]
q = deque()

for i in range(H):
    line = input()
    field.append(['#'] + list(line) + ['#'])
    for j in range(W):
        if line[j] == '#':
            q.append((i + 1, j + 1, 0))

field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()

    if 0 <= y+1 < H and visited[(y+1)*W+x] > lv:
        visited[(y+1)*W+x] = lv
        q.append((y+1, x, lv+1))

    if 0 <= y-1 < H and visited[(y-1)*W+x] > lv:
        visited[(y-1)*W+x] = lv
        q.append((y - 1, x, lv + 1))

    if 0 <= x+1 < W and visited[y*W+x+1] > lv:
        visited[y*W+x+1] = lv
        q.append((y, x+1, lv + 1))

    if 0 <= x-1 < W and visited[y*W+x-1] > lv:
        visited[y*W+x-1] = lv
        q.append((y, x-1, lv + 1))

print(max(visited))

Submission status: Runtime Error

Solution code:
from collections import deque

dyx = ((0, 1), (0, -1), (1, 0), (-1, 0))
H, W = map(int, input().split())
visited = [0]*(H*W)
q = deque()

for i in range(H):
    line = input()
    for j in range(W):
        if line[j] == '#':
            q.append((i, j, 0))
            visited[i*H+j] = 1

res = 0

while q:
    y, x, lv = q.popleft()
    if lv > res:
        res = lv

    for dy, dx in dyx:
        ny, nx = y+dy, x+dx
        if 0 <= ny < H and 0 <= nx < W and visited[ny*H+nx] == 0:
            visited[ny*H+nx] = 1
            q.append((ny, nx, lv+1))

print(res)

Submission status: Runtime Error

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



def solve(H: int, W: int, A: "List[str]"):
    current = set()
    for i in range(W):
        for j in range(H):
            if not A[i][j]:
                current.add((i,j))
    def appendIfPossible(i,j,s):
        if i >= 0 and i < W and j >=0 and j < H and A[i][j]:
            s.add((i,j))
            A[i][j] = False
    count = 0
    while True:
        next = set()
        for c in current:
            appendIfPossible(c[0]-1,c[1],next)
            appendIfPossible(c[0]+1,c[1],next)
            appendIfPossible(c[0],c[1]-1,next)
            appendIfPossible(c[0],c[1]+1,next)
        current = next
        count+= 1
        if len(next) == 0:
            break
    print(count-1)
    return


# Generated by 1.1.6 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 = [list(map(lambda x:x=='.',next(tokens))) for _ in range(H)]  # type: "List[str]"
    solve(H, W, A)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np
 
num = list(map(int,input().split()))
field = [list(input()) for i in range(num[0])]
q_r = deque([])
q_c = deque([])
seen = np.zeros((num[0],num[1]))
step_r = [1,0,-1,0]
step_c = [0,1,0,-1]
 
for i in range(num[0]):
  for j in range(num[1]):
    if field[i][j] == "#":
      q_r.append(i)
      q_c.append(j)
      g_r = i
      g_c = j
 
while q_r:
  r = q_r.popleft()
  c = q_c.popleft()
 
  for i in range(4):
    next_r = r + step_r[i]
    next_c = c + step_c[i]
    
    if (next_r<0) or (num[0]<=next_r) or (next_c<0) or (num[1]<=next_c) or (field[next_r][next_c] == "#"):
      continue
    
    field[next_r][next_c] = "#"
    q_r.append(next_r)
    q_c.append(next_c)
    seen[next_r][next_c] = seen[r][c] + 1
#    print(seen[next_r][next_c],next_r,next_c)
    g_r = next_r
    g_c = next_c
 
print(int(seen[g_r][g_c]))

Submission status: Runtime Error

Solution code:
def main():
  num_r,num_c = map(int,input().split())
  field = [input() for i in range(num_r)]
  q = []
  seen = [0]*(num_c*num_r)
  count = 0

  for i in range(num_r):
    for j in range(num_c):
      if field[i][j] == "#":
        seen[i*num_c+j] = 1
        q.append(i*num_c+j)

  while q:
    tank = []
    for i in q:
      if (0<=i-num_c) and (seen[i-num_c] == 0):
        tank.append(i-num_c)
        seen[i-num_c] = 1
      if (i+num_c<num_c*num_r) and (seen[i+num_c] == 0):
        tank.append(i+num_c)
        seen[i+num_c] = 1
      if (0<=i%num_c -1) and (seen[i-1] == 0):
        tank.append(i-1)
        seen[i-1] = 1
      if (i%num_c+1<num_r) and (seen[i+1] == 0):
        tank.append(i+1)
        seen[i+1] = 1

    count = count + 1
    q = tank

  print(count-1)
  
if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

  used = [True]*(h*w)

  p = []
  for i in range(h):
    for j in range(w):
      if a[i][j] == '#':
        p.append(i*w+j)
        used[i*w+j] = False
 
 
    
res = 0
while p:
    tank = []
    for e in p:
        if e>w-1 and used[e-w]:
            tank.append(e-w)
            used[e-w] = False
        if e%w > 0 and used[e-1]:
            tank.append(e-1)
            used[e-1] = False
        if e<(h-1)*w and used[e+w]:
            tank.append(e+w)
            used[e+w] = False
        if e%w<w-1 and used[e+1]:
            tank.append(e+1)
            used[e+1] =  False
    p = tank
    res += 1
print(res-1)

Submission status: Runtime Error

Solution code:
#from collections import deque

num_r,num_c = map(int,input().split())
field = [input() for i in range(num_r)]
q = []
seen = [0]*(num_c*num_r)
count = 0

for i in range(num_r):
  for j in range(num_c):
    if field[i][j] == "#":
      seen[i*num_c+j] = 1
      q.append(i*num_c+j)

while q:
  tank = []
  for i in q:
    if (0<=i-num_c) and (seen[i-num_c] == 0):
      tank.append(i-num_c)
      seen[i-num_c] = 1
    if (i+num_c<num_c*num_r) and (seen[i+num_c] == 0):
      tank.append(i+num_c)
      seen[i+num_c] = 1
    if (0<=i%num_c-1) and (seen[i-1] == 0):
      tank.append(i-1)
      seen[i-1] = 1
    if (i%num_c+1<num_r) and (seen[i+1] == 0):
      tank.append(i+1)
      seen[i+1] = 1
   
  count = count + 1
  q = tank

print(count-1)

Submission status: Runtime Error

Solution code:
from collections import deque

num_r,num_c = map(int,input().split())
field = [input() for i in range(num_r)]
q = deque([])
seen = [0]*(num_c*num_r)
step_r = [1,0,-1,0]
step_c = [0,1,0,-1]

for i in range(num_r):
  for j in range(num_c):
    if field[i][j] == "#":
      q.append([i,j])

while q:
  now_q = q.popleft()
  r = now_q[0]
  c = now_q[1]

  for i in range(4):
    next_r = r + step_r[i]
    next_c = c + step_c[i]
    
    if (0 <= next_r < num_r) and (0 <= next_c < num_c) and (field[next_r][next_c] != "#") and (seen[next_r*num_c+next_c] == 0):
      q.append([next_r,next_c])
      seen[next_r*num_c+next_c] = seen[r*num_c+c] + 1
  #    print(seen[next_r][next_c],next_r,next_c)
      g_r = next_r
      g_c = next_c

print(int(seen[g_r*num_c+g_c]))

Submission status: Runtime Error

Solution code:
from collections import deque

num_r,num_c = map(int,input().split())
field = [list(input()) for i in range(num_r)]
q = deque([])
seen = [[0]*num_c for i in range(num_r)]
step_r = [1,0,-1,0]
step_c = [0,1,0,-1]

for i in range(num_r):
  for j in range(num_c):
    if field[i][j] == "#":
      q.append([i,j])

while q:
  now_q = q.popleft()
  r = now_q[0]
  c = now_q[1]

  for i in range(4):
    next_r = r + step_r[i]
    next_c = c + step_c[i]
    
    if (0 <= next_r < num_r) and (0 <= next_c < num_c) and (field[next_r][next_c] != "#"):
      field[next_r][next_c] = "#"
      q.append([next_r,next_c])
      seen[next_r][next_c] = seen[r][c] + 1
  #    print(seen[next_r][next_c],next_r,next_c)
      g_r = next_r
      g_c = next_c

print(int(seen[g_r][g_c]))

Submission status: Runtime Error

Solution code:
import queue
import numpy as np

num = list(map(int,input().split()))
field = [list(input()) for i in range(num[0])]
q_r = queue.Queue()
q_c = queue.Queue()
seen = np.zeros((num[0],num[1]))
step_r = [1,0,-1,0]
step_c = [0,1,0,-1]

for i in range(num[0]):
  for j in range(num[1]):
    if field[i][j] == "#":
      q_r.put(i)
      q_c.put(j)
      
while not q_r.empty():
  r = q_r.get()
  c = q_c.get()
  
  for i in range(4):
    next_r = r + step_r[i]
    next_c = c + step_c[i]
    
    if (next_r<0) or (num[0]<=next_r) or (next_c<0) or (num[1]<=next_c) or (field[next_r][next_c] == "#"):
      continue
    
    field[next_r][next_c] = "#"
    q_r.put(next_r)
    q_c.put(next_c)
    seen[next_r][next_c] = seen[r][c] + 1
#    print(seen[next_r][next_c],next_r,next_c)
    g_r = next_r
    g_c = next_c

print(int(seen[g_r][g_c]))

Submission status: Runtime Error

Solution code:
from collections import deque


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

has_visited = [[True]*(W+2)]
has_visited += [[True] + [m == "#" for m in input().rstrip()] + [True] for _ in range(H)]
has_visited += [[True]*(W+2)]

search_que = deque()
for y in range(1, W+1):
    for x in range(1, H+1):
        if has_visited[y][x]:
            search_que.append((y, x))

count = -1
while search_que:
    count += 1
    next_que = deque()
    for y, x in search_que:
        if not has_visited[y+1][x]:
            has_visited[y+1][x] = True
            next_que.append((y+1, x))
        if not has_visited[y-1][x]:
            has_visited[y-1][x] = True
            next_que.append((y-1, x))
        if not has_visited[y][x+1]:
            has_visited[y][x+1] = True
            next_que.append((y, x+1))
        if not has_visited[y][x-1]:
            has_visited[y][x-1] = True
            next_que.append((y, x-1))
    search_que = next_que

print(count)

Submission status: Runtime Error

Solution code:
import copy

####入力
H,W = map(int,input().split())

#gridの定義
grid = []
for i in range(H):
  S = input()
  grid.append( [S[i] for i in range(W) ])
####入力終了


#l_blackの設定
l_black = []
for i in range(H):
  for j in range(W):
    if grid[i][j] == "#":
      l_black.append( [i,j] ) # [行,列]


#探索
cnt = 0

while len(l_black) > 0:

  l_change = []

  #vは黒マスリスト #新たに黒マスになる白マスの座標をl_changeに詰めていく
  for v in l_black:
    #iはvの上下左右のマスの座標[行,列]
    for i in [ [v[0]+1,v[1]] , [v[0],v[1]+1] , [v[0]-1,v[1]] ,[v[0],v[1]-1] ]:
      #場外アウトの場合はスルー
      if (i[0]<0 or i[1] <0 or i[1]>=H or i[0] >= W ):
        continue
      #移動先がもう黒マスの場合スルー
      if grid[i[1]][i[0]] == "#":
        continue
      #移動先が白マスならばそこの座標をl_changeに追加
      if grid[i[1]][i[0]] == ".":
        l_change.append( i )
  
  #l_changeの中の白マスを黒にする
  for i in l_change:
    grid[i[0]][i[1]] = "#" 
  #l_blackの中を新たに黒鱒になったやつの座標だけにする
  l_black = copy.deepcopy( l_change )
  if len(l_black) > 0:
    cnt = cnt + 1
print(cnt)

Submission status: Runtime Error

Solution code:
import copy

####入力
H,W = map(int,input().split())

#gridの定義
grid = []
for i in range(H):
  S = input()
  grid.append( [S[i] for i in range(W) ])
####入力終了


#l_blackの設定
l_black = []
for i in range(H):
  for j in range(W):
    if grid[i][j] == "#":
      l_black.append( [i,j] ) # [行,列]


#探索
cnt = 0

while len(l_black) > 0:

  l_change = []

  #vは黒マスリスト #新たに黒マスになる白マスの座標をl_changeに詰めていく
  for v in l_black:
    #iはvの上下左右のマスの座標[行,列]
    for i in [ [v[0]+1,v[1]] , [v[0],v[1]+1] , [v[0]-1,v[1]] ,[v[0],v[1]-1] ]:
      #場外アウトの場合はスルー
      if (i[0]<0 or i[1] <0 or i[1]>=H or i[0] >= W ):
        continue
      #移動先がもう黒マスの場合スルー
      if grid[i[1]][i[0]] == "#":
        continue
      #移動先が白マスならばそこの座標をl_changeに追加
      if grid[i[1]][i[0]] == ".":
        l_change.append( i )
  
  #l_changeの中の白マスを黒にする
  for i in l_change:
    grid[i[0]][i[1]] = "#" 
  print(grid)
  #l_blackの中を新たに黒鱒になったやつの座標だけにする
  l_black = copy.deepcopy( l_change )
  if len(l_black) > 0:
    cnt = cnt + 1
print(cnt)

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np
H,W = map(int,input().split())
A = [list(input()) for _ in range(H)]
table = [[float('inf')]*(W) for _ in range(H)]
visited = [[False]*(W) for _ in range(H)]
start = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            table[i][j] = 0
            start.append((i,j))
for (sy, sx) in start:
    visited[sy][sx] = True
    que = deque([(sx,sy)])
    while que:
        y,x = que.popleft()
        for dy, dx in ((1,0),(-1,0),(0,1),(0,-1)):
            ny,nx = y+dy, x+dx
            if 0<=ny<H and 0<=nx<W:
                if table[ny][nx] == float('inf'):
                    table[ny][nx] = table[y][x]+1
                    que.append((ny, nx))
print(np.array(table).max())

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np

H,W = map(int,input().split())
A = [list(input()) for _ in range(H)]
table = [[float('inf')]*(W) for _ in range(H)]
visited = [[False]*(W) for _ in range(H)]
start = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            table[i][j] = 0
            start.append((i,j))
for (sy, sx) in start:
    visited[sy][sx] = True
    que = deque([(sx,sy)])
    while que:
        y,x = que.popleft()
        for dy, dx in ((1,0),(-1,0),(0,1),(0,-1)):
            ny,nx = y+dy, x+dx
            if 0<=ny<H and 0<=nx<W:
                if table[ny][nx] == float('inf'):
                    table[ny][nx] = table[y][x]+1
                    que.append((ny, nx))
print(np.array(table).max())

Submission status: Runtime Error

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
cnt = [[float('inf')]*w for _ in range(h)]
moves = ((0, 1), (0, -1), (1, 0), (-1, 0))
q = deque([])
for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      cnt[i][j] = 0 
 
def bfs():
  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      ny = y + dy
      nx = x + dx 
      if 0 <= ny < h and 0 <= nx < w and a[ny][nx] == '.' and used[ny][nx] == 0:
        used[ny][nx] = 1
        cnt[ny][nx] = min(cnt[ny][nx], cnt[y][x]+1)
        q.append([ny, nx])
 
used = [[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      used[i][j] = 1
      q.append([i, j])
 
bfs()
 
ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans, cnt[i][j])
print(ans)
from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
cnt = [[float('inf')]*w for _ in range(h)]
moves = ((0, 1), (0, -1), (1, 0), (-1, 0))
q = deque([])
for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      cnt[i][j] = 0 

def bfs():
  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      ny = y + dy
      nx = x + dx 
      if 0 <= ny < h and 0 <= nx < w and a[ny][nx] == '.' and used[ny][nx] == 0:
        used[ny][nx] = 1
        cnt[ny][nx] = min(cnt[ny][nx], cnt[y][x]+1)
        q.append([ny, nx])

used = [[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      used[i][j] = 1
      q.append([i, j])

bfs()

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

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split()) 
a=[list(map(int,list(input().replace('.','0').replace('#','1')))) for i in range(h)] 


cnt=0 
while sum(map(sum, a))<h*w: 
    cnt+=1 
    tmp=[] 
    for i in range(h): 
        for j in range(w): 
            if a[i][j]==1: 
                tmp+=[[i,j]] 
    for tmpxy in tmp: 
        i,j=tmpxy[0],tmpxy[1] 
        if i>0: 
            a[i-1][j]=1 
        if i<h-1: 
            a[i+1][j]=1 
        if j>0: 
            a[i][j-1]=1 
        if j<h-1: 
            a[i][j+1]=1 
print(cnt)

Submission status: Runtime Error

Solution code:
from collections import deque

h,w=map(int,input().split())
a = [input() for _ in range(h)]
move=((1,0),(0,1),(-1,0),(0,-1))

que=deque([])
visited=[[0]*h for _ in range(w)]
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            que.append((i,j,0))
            visited[i][j]=1


while len(que)>0:       
    ci,cj,d=que.popleft()
    for mi,mj in move:
        ni,nj=mi+ci,mj+cj
        if 0<=ni<h and 0<=nj<w and visited[ni][nj]==0:
            if a[ni][nj]==".":
                visited[ni][nj]=1
                que.append((ni,nj,d+1))

print(d)

Submission status: Runtime Error

Solution code:
from collections import deque

h,w=map(int,input().split())
a = [input() for _ in range(h)]
move=((1,0),(0,1),(-1,0),(0,-1))

que=deque([])
visited=[[0]*h for _ in range(w)]
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            que.append((i,j,0))
            visited[i][j]==1


while len(que)>0:       
    ci,cj,d=que.popleft()
    for mi,mj in move:
        ni,nj=mi+ci,mj+cj
        if 0<=ni<h and 0<=nj<w and visited[ni][nj]==0:
            if a[ni][nj]==".":
                visited[ni][nj]=1
                que.append((ni,nj,d+1))

print(d)

Submission status: Runtime Error

Solution code:
from collections import deque

h,w=map(int,input().split())
a = [input() for _ in range(h)]
move=((1,0),(0,1),(-1,0),(0,-1))

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

visited=[[0]*h for _ in range(w)]

while len(que)>0:       
    ci,cj,d=que.popleft()
    for mi,mj in move:
        ni,nj=mi+ci,mj+cj
        if 0<=ni<h and 0<=nj<w and visited[ni][nj]==0:
            if a[ni][nj]==".":
                visited[ni][nj]=1
                que.append((ni,nj,d+1))
print(d)

Submission status: Runtime Error

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

print(2)

Submission status: Runtime Error

Solution code:
import queue

H, W = map(int, input().split())
A = []
D = [[-1 for _ in range(W)] for _ in range(H)]
q = queue.Queue()
for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == "#":
            q.put((i, j))
            D[i][j] = 0
    A.append(S)

ans = 0
while not q.empty():
    pos = q.get()
    py, px = pos[0], pos[1]
    ans = max(ans, D[py][px])
    for (y, x) in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
        ny = py + y
        nx = px + x
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            if D[ny][nx] < 0:
                D[ny][nx] = D[py][px] + 1
                q.put((ny, nx))
print(ans)

Submission status: Runtime Error

Solution code:
# ANSHUL GAUTAM
# IIIT-D

'''

'''

def solve(grid):
	H,W = len(grid),len(grid[0])
	q = []
	dist = [0]*H
	for i in range(H):
		dist[i] = []
	for i in range(H):
		for j in range(W):
			if(grid[i][j] == '#'):
				q.append([i,j])
				grid[i][j] = 0
	maxx = 0
	while(q):
		qq = []
		for i,j in q:
			for r,c in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:
				if(0 <= r < H and 0 <= c < W and grid[r][c] == '.'):
					grid[r][c] = grid[i][j] + 1
					maxx = max(maxx,grid[r][c])
					qq.append([r,c])
		q = qq
	return maxx

H,W = map(int, input().split())
grid = []
for h in range(H):
	s = list(input())
	grid.append(s)
ans = solve(grid)
print(ans)

Submission status: Runtime Error

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *
from string import *                # alpha = ascii_lowercase
from random import *                # l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from sys import stdin
from sys import maxsize
from operator import *                # d = sorted(d.items(), key=itemgetter(1))
from itertools import *
from collections import Counter        # d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''

'''

def solve(grid):
	H,W = len(grid),len(grid[0])
	q = []
	dist = [0]*H
	for i in range(H):
		dist[i] = []
	for i in range(H):
		for j in range(W):
			if(grid[i][j] == '#'):
				q.append([i,j])
				grid[i][j] = 0
	maxx = 0
	for i,j in q:
		for r,c in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:
			if(0 <= r < H and 0 <= c < H and grid[r][c] == '.'):
				grid[r][c] = grid[i][j] + 1
				maxx = max(maxx,grid[r][c])
				q.append([r,c])
	return maxx

H,W = map(int, stdin.readline().rstrip().split())
grid = []
for h in range(H):
	s = list(input())
	grid.append(s)
ans = solve(grid)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
h,w,k=map(int,input().split())
a = [list(input().rstrip()) for i in range(h)]
q = deque()
for i in range(h):
  for j in range(w):
    if a[i][j] == "#":
      a[i][j] = 0
      q.append((i,j,0))
    else:
      a[i][j] = -1
while q:
  s,t,cnt = q.popleft()
  for ns,nt in ((s+1,t),(s-1,t),(s,t+1),(s,t-1)):
    if 0<=ns<=h-1 and 0<=nt<=w-1 and a[ns][nt] == -1:
      q.append((ns,nt,cnt+1))
      a[ns][nt] = cnt+1
ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans,a[i][j])
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
h,w,k=map(int,input().split())
a = [list(input().rstrip()) for i in range(h)]
q = deque()
for i in range(h):
  for j in range(w):
    if a[i][j] == "x":
      a[i][j] = 0
      q.append((i,j,0))
    else:
      a[i][j] = -1
while q:
  s,t,cnt = q.popleft()
  for ns,nt in ((s+1,t),(s-1,t),(s,t+1),(s,t-1)):
    if 0<=ns<=h-1 and 0<=nt<=w-1 and a[ns][nt] == -1:
      q.append((ns,nt,cnt+1))
      a[ns][nt] = cnt+1
ans = 0
for i in range(k-1,h-k+1):
  for j in range(k-1,w-k+1):
    if a[i][j] >= k:
      ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
# 迷路読み込み
h,w = map(int, input().split())
maze=[list(input()) for i in range(h)]

import collections
from collections import deque

INF = -10 ** 9
distance = [[INF for i in range(w)] for j in range(h)]
d = deque()
def bfs():
    cnt=0
    while len(d):
        x, y = d.pop()
        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

            if (0 <= nx <=w-1 and 0 <= ny<=h-1 and distance[nx][ny] == INF):
                d.appendleft((nx, ny))
                distance[nx][ny] = distance[x][y] + 1
                if cnt<distance[nx][ny]:
                    cnt=distance[nx][ny]

    return cnt


for i in range(h):
    for j in range(w):
        if maze[i][j]=='#':
            d.append((i,j))
            distance[i][j]=0
print(bfs())

Submission status: Runtime Error

Solution code:
# 迷路読み込み
h,w = map(int, input().split())
maze=[list(input()) for i in range(h)]

import collections
from collections import deque

INF = -10 ** 9
distance = [[INF for i in range(w)] for j in range(h)]
d = deque()
def bfs():
    cnt=0
    while len(d):
        x, y = d.pop()
        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

            if (0 <= nx <=w-1 and 0 <= ny<=h-1 and maze[nx][ny] != '#' and distance[nx][ny] == INF):
                d.appendleft((nx, ny))
                distance[nx][ny] = distance[x][y] + 1
                if cnt<distance[nx][ny]:
                    cnt=distance[nx][ny]

    return cnt


for i in range(h):
    for j in range(w):
        if maze[i][j]=='#':
            d.append((i,j))
            distance[i][j]=0
print(bfs())

Submission status: Runtime Error

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[list(S()) for _ in range(h)]

  q=collections.deque()
  nokori=h*w
  dist=[[-1]*w for _ in range(h)]
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        q.append((i,j))
        dist[i][j]=0
        nokori-=1

  while q:
    if nokori==0:
      return d

    y,x=q.popleft()

    for dy,dx in dd:
      ny=y+dy
      nx=x+dx

      if 0<=ny and ny<h and 0<=nx and nx<w:
        if field[ny][nx]=='.':
          field[ny][nx]='#'
          d=dist[y][x]+1
          dist[ny][nx]=d
          q.append((ny,nx))
          nokori-=1

  return d

# main()
print(main())

Submission status: Runtime Error

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[list(S()) for _ in range(h)]

  q=collections.deque()
  nokori=h*w
  dist=[[-1]*w for _ in range(h)]
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        q.append((i,j))
        dist[i][j]=0
        nokori-=1

  while len(q)>0:
    if nokori==0:
      return d

    y,x=q.popleft()

    for dy,dx in dd:
      ny=y+dy
      nx=x+dx

      if 0<=ny<h and 0<=nx<w:
        if field[ny][nx]=='.':
          field[ny][nx]='#'
          d=dist[y][x]+1
          dist[ny][nx]=d
          q.append((ny,nx))
          nokori-=1

  return d

# main()
print(main())

Submission status: Runtime Error

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[list(S()) for _ in range(h)]

  q=collections.deque()
  nokori=h*w
  dist=[[-1]*w for _ in range(h)]
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        q.append((i,j))
        dist[i][j]=0
        nokori-=1

  while q:
    if nokori==0:
      return d

    y,x=q.popleft()

    for dy,dx in dd:
      ny=y+dy
      nx=x+dx

      if 0<=ny<h and 0<=nx<w:
        if field[ny][nx]=='.':
          field[ny][nx]='#'
          d=dist[y][x]+1
          dist[ny][nx]=d
          q.append((ny,nx))
          nokori-=1

  return d

# main()
print(main())

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
AA = [input() for _ in range(h)]
blacks = set()
for i in range(h):
  for j in range(w):
    if AA[i][j] == '#':
      blacks.add((j, i))

print(
  max(
    min(abs(i - y) + abs(j - x) for x, y in blacks)
    for i in range(h)
    for j in range(w)
    if AA[i][j] != '#'
  )
)

Submission status: Runtime Error

Solution code:
        from collections import deque
        import numpy as np
         
        def bfs():
            #max = 0
            dx = [1, 0, -1, 0]
            dy = [0, 1, 0, -1]
            que = deque([])
            for i in slist:
                que.append((i[0], i[1]))
                d[i[0]][i[1]] = 0
         
         
            while que:
                p = que.popleft()
         
                for i in range(4):
                    nx = p[1] + dx[i]
                    ny = p[0] + dy[i]
                    #a = temp[ny][nx]
                    if 0<=nx<W and 0<=ny<H and maze[ny][nx]!="#":
                        #que.append((nx))
                        temp[ny][nx] = d[p[0]][p[1]] + 1
                        a = temp[ny][nx]
                        #d[ny][nx] = d[p[0]][p[1]] + 1
                        if a < d[ny][nx]:
                            que.append((ny, nx))
                            d[ny][nx] = a
                            #if max < d[ny][nx]:
                                #max = d[ny][nx]
         
            return np.max(np.array(d))
         
        H, W = map(int, input().split())
        d = [[float("inf")]*W for i in range(H)]
        temp = [[float("inf")]*W for i in range(H)]
        maze = [list(input()) for i in range(H)]
         
        slist = []
        for i in range(H):
            for j in range(W):
                if maze[i][j]=="#":
                    slist.append((i,j))
         
         
         
     
         
        print(bfs())

Submission status: Runtime Error

Solution code:
    from collections import deque
    import numpy as np
     
    def bfs():
        #max = 0
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        que = deque([])
        for i in slist:
            que.append((i[0], i[1]))
            d[i[0]][i[1]] = 0
     
     
        while que:
            p = que.popleft()
     
            for i in range(4):
                nx = p[1] + dx[i]
                ny = p[0] + dy[i]
                #a = temp[ny][nx]
                if 0<=nx<W and 0<=ny<H and maze[ny][nx]!="#":
                    #que.append((nx))
                    temp[ny][nx] = d[p[0]][p[1]] + 1
                    a = temp[ny][nx]
                    #d[ny][nx] = d[p[0]][p[1]] + 1
                    if a < d[ny][nx]:
                        que.append((ny, nx))
                        d[ny][nx] = a
                        #if max < d[ny][nx]:
                            #max = d[ny][nx]
     
        return np.max(np.array(d))
     
    H, W = map(int, input().split())
    d = [[float("inf")]*W for i in range(H)]
    temp = [[float("inf")]*W for i in range(H)]
    maze = [list(input()) for i in range(H)]
     
    slist = []
    for i in range(H):
        for j in range(W):
            if maze[i][j]=="#":
                slist.append((i,j))
     
     
     

     
    print(bfs())