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: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import collections
import numpy as np

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##
def main():
    H, W = rip()
    S = [rs() for i in range(H)]
    #min = np.full((H,W),-1, dtype = 'int')
    min = [[-1] * W for i in range(H)]
    q = collections.deque()
    def enc(h, w): return h * W + w
    def inRange(t, l, r): return l <= t and t < r
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]

    for i in range(H):
        for j in range(W):
            if S[i][j] == '#':
                q.append(enc(i,j))
                min[i][j] = 0
    while(len(q) > 0):
        rc = q.popleft()
        y = rc // W
        x = rc % W
        for t in range(4):
            nx = x + dx[t]
            ny = y + dy[t]
            if (not inRange(nx,0,W)) or (not inRange(ny,0,H)): continue
            if min[ny][nx] == -1:
                min[ny][nx] = min[y][x] + 1
                q.append(enc(ny,nx))
    
    ma = 0
    for i in range(H):
        for j in range(W):
            ma = max(ma, min[i][j])
    print(ma)





if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import collections
import numpy as np

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##
def main():
    H, W = rip()
    S = [rs() for i in range(H)]
    min = np.full((H,W),-1, dtype = 'int')
    q = collections.deque()
    def enc(h, w): return h * W + w
    def inRange(t, l, r): return l <= t and t < r
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]

    for i in range(H):
        for j in range(W):
            if S[i][j] == '#':
                q.append(enc(i,j))
                min[i][j] = 0
    while(len(q) > 0):
        rc = q.popleft()
        y = rc // W
        x = rc % W
        for t in range(4):
            nx = x + dx[t]
            ny = y + dy[t]
            if (not inRange(nx,0,W)) or (not inRange(ny,0,H)): continue
            if min[ny][nx] == -1:
                min[ny][nx] = min[y][x] + 1
                q.append(enc(ny,nx))
    
    ma = 0
    for i in range(H):
        for j in range(W):
            ma = max(ma, min[i][j])
    print(ma)





if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque
def main():
  H, W = map(int, input().split())
  M = [['#' == x for x in input()] for _ in range(H)]

  black = deque([(i, j) for i in range(H) for j in range(W) if M[i][j]])

  ans = 0
  while True:
    ans += 1
    next_black = deque()
    while black:
      bi, bj = black.popleft()
      if bi - 1 >= 0 and not M[bi - 1][bj]:
        M[bi - 1][bj] = True
        next_black.append((bi - 1, bj))
      if bj - 1 >= 0 and not M[bi][bj - 1]:
        M[bi][bj - 1] = True
        next_black.append((bi, bj - 1))
      if bi + 1 < H and not M[bi + 1][bj]:
        M[bi + 1][bj] = True
        next_black.append((bi + 1, bj))
      if bj + 1 < W and not M[bi][bj + 1]:
        M[bi][bj + 1] = True
        next_black.append((bi, bj + 1))
    if next_black:
       black = copy.copy(next_black)
    else:
       break
  print(ans - 1)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque
H, W = map(int, input().split())
M = [['#' == x for x in input()] for _ in range(H)]

black = deque([(i, j) for i in range(H) for j in range(W) if M[i][j]])

ans = 0
while True:
  ans += 1
  next_black = deque()
  while black:
    bi, bj = black.popleft()
    if bi - 1 >= 0 and not M[bi - 1][bj]:
      M[bi - 1][bj] = True
      next_black.append((bi - 1, bj))
    if bj - 1 >= 0 and not M[bi][bj - 1]:
      M[bi][bj - 1] = True
      next_black.append((bi, bj - 1))
    if bi + 1 < H and not M[bi + 1][bj]:
      M[bi + 1][bj] = True
      next_black.append((bi + 1, bj))
    if bj + 1 < W and not M[bi][bj + 1]:
      M[bi][bj + 1] = True
      next_black.append((bi, bj + 1))
  if next_black:
     black = copy.copy(next_black)
  else:
     break
print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque
H, W = map(int, input().split())
M = [['#' == x for x in input()] for _ in range(H)]

black = deque()
for i in range(H):
  for j in range(W):
    if M[i][j]:
      black.append((i, j))

ans = 0
while True:
  ans += 1
  next_black = deque()
  while black:
    bi, bj = black.popleft()
    if bi - 1 >= 0 and not M[bi - 1][bj]:
      M[bi - 1][bj] = True
      next_black.append((bi - 1, bj))
    if bj - 1 >= 0 and not M[bi][bj - 1]:
      M[bi][bj - 1] = True
      next_black.append((bi, bj - 1))
    if bi + 1 < H and not M[bi + 1][bj]:
      M[bi + 1][bj] = True
      next_black.append((bi + 1, bj))
    if bj + 1 < W and not M[bi][bj + 1]:
      M[bi][bj + 1] = True
      next_black.append((bi, bj + 1))
  if next_black:
     black = copy.copy(next_black)
  else:
     break
print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque
H, W = map(int, input().split())
M = [list(input()) for _ in range(H)]

black = deque()
for i in range(H):
  for j in range(W):
    if M[i][j] == '#':
      black.append((i, j))

ans = 0
while True:
  ans += 1
  next_black = deque()
  while black:
    bi, bj = black.popleft()
    if bi - 1 >= 0 and M[bi - 1][bj] == '.':
      M[bi - 1][bj] = '#'
      next_black.append((bi - 1, bj))
    if bj - 1 >= 0 and M[bi][bj - 1] == '.':
      M[bi][bj - 1] = '#'
      next_black.append((bi, bj - 1))
    if bi + 1 < H and M[bi + 1][bj] == '.':
      M[bi + 1][bj] = '#'
      next_black.append((bi + 1, bj))
    if bj + 1 < W and M[bi][bj + 1] == '.':
      M[bi][bj + 1] = '#'
      next_black.append((bi, bj + 1))
  if next_black:
     black = copy.copy(next_black)
  else:
     break
print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque
H, W = map(int, input().split())
M = [list(input()) for _ in range(H)]

black = deque()
for i in range(H):
  for j in range(W):
    if M[i][j] == '#':
      black.append((i, j))

ans = 0
while True:
  ans += 1
  next_black = deque()
  while black:
    bi, bj = black.popleft()
    for i, j in [(bi - 1, bj), (bi + 1, bj), (bi, bj - 1), (bi, bj + 1)]:
      if i >= 0 and i < H and j >= 0 and j < W:
        if M[i][j] == '.':
          M[i][j] = '#'
          next_black.append((i, j))
  if next_black:
     black = copy.copy(next_black)
  else:
     break
print(ans - 1)

Submission status: Time Limit Exceeded

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

black = []
for i in range(H):
  for j in range(W):
    if M[i][j] == '#':
      black.append((i, j))
ans = 0
while True:
  ans += 1
  next_black = []
  while black:
    bi, bj = black.pop(0)
    for i, j in [(bi - 1, bj), (bi + 1, bj), (bi, bj - 1), (bi, bj + 1)]:
      if i >= 0 and i < H and j >= 0 and j < W:
        if M[i][j] == '.':
          M[i][j] = '#'
          next_black.append((i, j))
  if next_black:
     black = copy.copy(next_black)
  else:
     break
print(ans - 1)

Submission status: Time Limit Exceeded

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

black = []
for i in range(H):
  for j in range(W):
    if M[i][j] == '#':
      black.append((i, j))
      
ans = 0

while any('.' in m for m in M):
  ans += 1
  next_black = []
  while black:
    bi, bj = black.pop(0)
    for i, j in [(bi - 1, bj), (bi + 1, bj), (bi, bj - 1), (bi, bj + 1)]:
      if i >= 0 and i < H and j >= 0 and j < W:
        if M[i][j] == '.':
          M[i][j] = '#'
          next_black.append((i, j))
  black = next_black
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

cnt = [[-1]*W for _ in range(H)]

que = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            que.append((h, w))
            cnt[h][w] = 0

ans = 0
while que:
    h, w = que.popleft()
    ans = cnt[h][w]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        next_h = h + dy
        next_w = w + dx
        if next_h < 0 or H <= next_h or next_w < 0 or W <= next_w:
            continue
        if cnt[next_h][next_w] == -1:
            cnt[next_h][next_w] = ans+1
            que.append((next_h, next_w))

print(int(ans))

Submission status: Time Limit Exceeded

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

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

f_inf = float('inf')
visited = [[f_inf] * w for _ in range(h)]
que = deque([])
for i in range(h):
    for j in range(w):
        if map[i][j] == "#":
            visited[i][j] = 0
            que.append((i, j))

ans = 0
while que:
    y, x = que.popleft()
    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        next_y, next_x = y + i, x + j
        ans = visited[y][x]
        if -1 < next_y < h and -1 < next_x < w and visited[next_y][next_x] == f_inf:
            visited[next_y][next_x] = visited[y][x] + 1
            que.append((next_y, next_x))

print(int(ans))

Submission status: Time Limit Exceeded

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

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

f_inf = float('inf')
visited = [[f_inf] * w for _ in range(h)]
que = deque([])
for i in range(h):
    for j in range(w):
        if map[i][j] == "#":
            visited[i][j] = 0
            que.append((i, j))

ans = 0
while que:
    y, x = que.popleft()
    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        next_y, next_x = y + i, x + j
        ans = visited[y][x]
        if -1 < next_y < h and -1 < next_x < w and map[next_y][next_x] == ".":
            if visited[next_y][next_x] > visited[y][x] + 1:
                visited[next_y][next_x] = visited[y][x] + 1
                que.append((next_y, next_x))

print(int(ans))

Submission status: Time Limit Exceeded

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

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

f_inf = float('inf')
visited = np.array([[f_inf] * w for _ in range(h)])
que = deque([])
for i in range(h):
    for j in range(w):
        if map[i][j] == "#":
            visited[i][j] = 0
            que.append([i, j])

while que:
    y, x = que.popleft()
    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        next_y, next_x = y + i, x + j
        if -1 < next_y < h and -1 < next_x < w and map[next_y][next_x] == ".":
            if visited[next_y][next_x] > visited[y][x] + 1:
                visited[next_y][next_x] = visited[y][x] + 1
                que.append([next_y, next_x])

print(int(np.max(visited)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

h, w = map(int, input().split())
#sy, sx = map(int, input().split())
#gy, gx = map(int, input().split())
map = [input() for _ in range(h)]

f_inf = float('inf')
visited = np.array([[f_inf] * w for _ in range(h)])
que = deque([])
for i in range(h):
    for j in range(w):
        if map[i][j] == "#":
            visited[i][j] = 0
            que.append([i, j])

while que:
    y, x = que.popleft()
    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        next_y, next_x = y + i, x + j
        if next_y > -1 and next_x > -1 and next_y < h and next_x < w and map[next_y][next_x] == ".":
            if visited[next_y][next_x] > visited[y][x] + 1:
                visited[next_y][next_x] = visited[y][x] + 1
                que.append([next_y, next_x])

print(int(np.max(visited)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
maiz = [None] * h
black = deque()
white = 0
for i in range(h):
    line = list(input())
    for j in range(w):
        if line[j] == '#':
            black.append([j, i])
        else:
            white += 1
    maiz[i] = line

def paint(black, white):
    new_black = deque()
    for bx, by in black:
        hjkl = [[bx-1, by], [bx, by-1], [bx+1, by], [bx, by+1]]
        for dx, dy in hjkl:
            if (dx<0) or (dx>w-1) or (dy<0) or (dy>h-1):
                continue
            if maiz[dy][dx] == '.':
                maiz[dy][dx] = '#'
                new_black.append([dx, dy])
                white -=1
    return new_black, white

ans = 0
while white > 0:
    black, white = paint(black, white)
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import deepcopy
h, w = map(int, input().split())
maiz = deque()
black = deque()
white = 0
for i in range(h):
    line = list(input())
    for j in range(w):
        if line[j] == '#':
            black.append([j, i])
        else:
            white += 1
    maiz.append(line)
visited = deepcopy(maiz)

def paint(black, white):
    new_black = deque()
    for bx, by in black:
        hjkl = [[bx-1, by], [bx, by-1], [bx+1, by], [bx, by+1]]
        for dx, dy in hjkl:
            if (dx<0) or (dx>w-1) or (dy<0) or (dy>h-1) or visited[dy][dx] == '#':
                continue
            if maiz[dy][dx] == '.':
                visited[dy][dx] = '#'
                maiz[dy][dx] = '#'
                new_black.append([dx, dy])
                white -=1
    return new_black, white

ans = 0
while white > 0:
    black, white = paint(black, white)
    ans += 1
    #print("i:{} ans:{}".format(i, ans))
    #print('black', black)
    #print('white', white)
    #for i in maiz:
    #    print(i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
maiz = deque()
black = deque()
white = 0
for i in range(h):
    line = list(input())
    for j in range(w):
        if line[j] == '#':
            black.append([j, i])
        else:
            white += 1
    maiz.append(line)

def paint(black, white, maiz):
    new_black = deque()
    for bx, by in black:
        hjkl = [[bx-1, by], [bx, by-1], [bx+1, by], [bx, by+1]]
        for dx, dy in hjkl:
            if (dx<0) or (dx>w-1) or (dy<0) or (dy>h-1):
                continue
            if maiz[dy][dx] == '.':
                maiz[dy][dx] = '#'
                new_black.append([dx, dy])
                white -=1
    return new_black, white, maiz

ans = 0
while white > 0:
    black, white, maiz = paint(black, white, maiz)
    ans += 1
    #print("i:{} ans:{}".format(i, ans))
    #print('black', black)
    #print('white', white)
    #for i in maiz:
    #    print(i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
maiz = []
black = deque()
white = 0
for i in range(h):
    line = list(input())
    for j in range(w):
        if line[j] == '#':
            black.append([j, i])
        else:
            white += 1
    maiz.append(line)
def paint(black, white, maiz):
    new_black = deque()
    for bx, by in black:
        hjkl = [[bx-1, by], [bx, by-1], [bx+1, by], [bx, by+1]]
        for dx, dy in hjkl:
            if (dx<0) or (dx>w-1) or (dy<0) or (dy>h-1):
                continue
            if maiz[dy][dx] == '.':
                maiz[dy][dx] = '#'
                new_black.append([dx, dy])
                white -=1
    return new_black, white, maiz
ans = 0
while white > 0:
    black, white, maiz = paint(black, white, maiz)
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
maiz = []
black = []
white = 0
for i in range(h):
    line = list(input())
    for j in range(w):
        if line[j] == '#':
            black.append([j, i])
        else:
            white += 1
    maiz.append(line)
def paint(black, white, maiz):
    new_black = []
    for bx, by in black:
        hjkl = [[bx-1, by], [bx, by-1], [bx+1, by], [bx, by+1]]
        for dx, dy in hjkl:
            if (dx<0) or (dx>w-1) or (dy<0) or (dy>h-1):
                continue
            if maiz[dy][dx] == '.':
                maiz[dy][dx] = '#'
                new_black.append([dx, dy])
                white -=1
    return new_black, white, maiz
ans = 0
while white > 0:
    black, white, maiz = paint(black, white, maiz)
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
maiz = []
black = []
white = 0
for i in range(h):
    line = list(input())
    for j in range(w):
        if line[j] == '#':
            black.append([j, i])
        else:
            white += 1
    maiz.append(line)

def paint(black, white, maiz):
    new_black = []
    for bx, by in black:
        hjkl = [[bx-1, by], [bx, by-1], [bx+1, by], [bx, by+1]]
        for dx, dy in hjkl:
            if (dx<0) or (dx>w-1) or (dy<0) or (dy>h-1):
                continue
            if maiz[dy][dx] == '.':
                maiz[dy][dx] = '#'
                new_black.append([dx, dy])
                white -=1
    return new_black, white, maiz

ans = 0
while white > 0:
    black, white, maiz = paint(black, white, maiz)
    ans += 1
    #print("i:{} ans:{}".format(i, ans))
    #print('black', black)
    #print('white', white)
    #for i in maiz:
    #    print(i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
H,W=map(int,input().split())


def dfs(h,w):
    A[h][w]="#"
    que=[]
    if h>0:
        if A[h-1][w]!="#":
            que.append([h-1,w])
            A[h-1][w]="#"
    if w>0:
        if A[h][w-1]!="#":
            que.append([h,w-1])
            A[h][w-1]="#"
    if h<H-1:
        if A[h+1][w]!="#":
            que.append([h+1,w])
            A[h+1][w]="#"
    if w<W-1:
        if A[h][w+1]!="#":
            que.append([h,w+1])
            A[h][w+1]="#"
    
    return que


A=[]
for _ in range(H):
    A.append(list(input()))

#print(A)

ans=0
lis=[]
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            lis.append([h,w])
while True:
    if lis:
        N=len(lis)
        for i in range(N):
            item=lis.pop(0)
            lis+=dfs(item[0],item[1])
    if len(lis)==0:
        break
    ans+=1
    #print(lis)
    #print(A)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
H,W=map(int,input().split())


def dfs(h,w,num):
    
    l[h][w]=min(l[h][w],num)
    
    if h>0:
        if A[h-1][w]!="#" and l[h-1][w]>=num:
            dfs(h-1,w,num+1)
    if w>0:
        if A[h][w-1]!="#" and l[h][w-1]>=num:
            dfs(h,w-1,num+1)
    if h<H-1:
        if A[h+1][w]!="#" and l[h+1][w]>=num:
            dfs(h+1,w,num+1)
    if w<W-1:
        if A[h][w+1]!="#" and l[h][w+1]>=num:
            dfs(h,w+1,num+1)
    
    return 0


A=[]
for _ in range(H):
    A.append(list(input()))

#print(A)

l=[[300]*W for i in range(H)]

for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            dfs(h,w,0)
ans=0
for item in l:
    ans=max(ans,max(item))

#print(l)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
H,W=map(int,input().split())


def dfs(h,w):
    que=[]
    if h>0:
        if A[h-1][w]!="#":
            que.append([h-1,w])
    if w>0:
        if A[h][w-1]!="#":
            que.append([h,w-1])
    if h<H-1:
        if A[h+1][w]!="#":
            que.append([h+1,w])
    if w<W-1:
        if A[h][w+1]!="#":
            que.append([h,w+1])
    
    return que


A=[]
for _ in range(H):
    A.append(list(input()))

#print(A)

ans=0
while True:
    lis=[]
    for h in range(H):
        for w in range(W):
            if A[h][w]=="#":
                lis+=dfs(h,w)
    if lis:
        for item in lis:
            A[item[0]][item[1]]="#"
    else:
        break
    ans+=1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs():
    global ans
    d = [[float("inf")] * w for _ in range(h)]
    que = deque([])
    for i in range(h):
        for j in range(w):
           if A[i][j] == "#":
               que.append([i, j])
               d[i][j] = 0
            
    while que:
        p = que.popleft()
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4): 
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < h and 0 <= ny < w and A[nx][ny] != "#" and d[nx][ny] == float("inf"):
                d[nx][ny] = d[p[0]][p[1]] + 1
                A[nx][ny] = "#"
                que.append([nx, ny])
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, d[i][j])


h, w = map(int, input().split())
A = [list(input()) for _ in range(h)]
ans = 0
bfs()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
  h,w=map(int,input().split())
  mp=[input() for _ in range(h)]
  dist=[-1]*(h*w)
  q=deque()
  
  for i in range(h):
    for j in range(w):
      if mp[i][j]=="#":
        q.append(i*w+j)
        dist[i*w+j]=0
      else:
        dist[i*w+j]=-1
  #print(q)
 
  while q:
    c=q.popleft()
    #print(c,q)
    x=c//w
    y=c%w
    for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
      xx,yy=x+i,y+j
      if (0<=xx<h and 0<=yy<w and dist[xx*w+yy]==-1):
        dist[xx*w+yy]=dist[x*w+y]+1
        q.append(xx*w+yy)
      
  print(max(dist))
  return

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
  h,w=map(int,input().split())
  mp=[input() for _ in range(h)]
  dist=[-1]*(h*w)
  q=deque()
  
  for i in range(h):
    for j in range(w):
      if mp[i][j]=="#":
        q.append(i*w+j)
        dist[i*w+j]=0
      else:
        dist[i*w+j]=-1
 
  while q:
    c=q.popleft()
    x=c//w
    y=c%w
    for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
      xx,yy=x+i,y+j
      if (0<=xx<h and 0<=yy<w and dist[xx*w+yy]==-1):
        dist[xx*w+yy]=dist[x*w+y]+1
        q.append(xx*w+yy)

  ret=0
  for i in range(h):
    for j in range(w):
      ret=max(ret,dist[i*w+j])
      
  print(ret)
  return

main()

Submission status: Time Limit Exceeded

Solution code:
#ループ回数をansにインクリメントして保管

def main():
  h,w=map(int,input().split()) 
  mp=[list(input()) for _ in range(h)]
  global dist
  dist=[[-1]*w for i in range(h)]
  
  q=[]
  for i in range(h):
    for j in range(w):
      if mp[i][j]=="#":
        dist[i][j]=0
        q.append((i,j))
      else:
        dist[i][j]=-1
  
  ans=0     
  while q:
    qq=[] #new_list qq
    for (x,y) in q:
      for i,j in ((0,1),(0,-1),(1,0),(-1,0)):
        xx,yy=x+i,y+j
        if 0<=xx<h and 0<=yy<w and dist[xx][yy]==-1:
          dist[xx][yy]="done"
          qq.append((xx,yy))
    q=qq #qと置き換え
    ans+=1        
  print(ans-1) #ラスト無駄に一回足してる分｡
  return

main()

Submission status: Time Limit Exceeded

Solution code:
#qに入れるlistをtupleにしてみる

from collections import deque 
def main():
  h,w=map(int,input().split()) 
  mp=[list(input()) for _ in range(h)]
  dist=[[-1]*w for i in range(h)]
  q=deque([])
  
  for i in range(h):
    for j in range(w):
      if mp[i][j]=="#":
        dist[i][j]=0
        q.append((i,j))
      else:
        dist[i][j]=-1
        
  while q:
    x,y=q.popleft()
    for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
      xx,yy=x+i,y+j
      if (0<=xx<h and 0<=yy<w and dist[xx][yy]==-1):
        dist[xx][yy]=dist[x][y]+1
        q.append((xx,yy))
        
  ret=0
  for i in range(h):
    for j in range(w):
      ret=max(ret,dist[i][j])
      
  print(ret)
  return

main()

Submission status: Time Limit Exceeded

Solution code:
#writer:yutaka1999さんの見ながらPythonで写経 通るかな？一応O(HW)=O(10**6)らしいけど...？
from collections import deque

def main():
  h,w=map(int,input().split())
  #global mp
  mp=[list(input()) for _ in range(h)]
  #global dist
  dist=[[-1]*w for i in range(h)]
  q=deque([])
  
  for i in range(h):
    for j in range(w):
      if mp[i][j]=="#":
        dist[i][j]=0
        q.append([i,j])
      else:
        dist[i][j]=-1
  
  while q:
    x,y=q.popleft()
    for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
      xx,yy=x+i,y+j
      if (0<=xx<h and 0<=yy<w and dist[xx][yy]==-1):
        dist[xx][yy]=dist[x][y]+1
        q.append([xx,yy])
  
  ret=0
  for i in range(h):
    for j in range(w):
      ret=max(ret,dist[i][j])
      
  print(ret)
  return

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

field = [list(input()) for _ in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs():
    distance = [[-1]*w for _ in range(h)]
    que = deque([])
    for i in range(h):
        for j in range(w):
            if field[i][j] == '#':
                que.append((i, j))
                distance[i][j] = 0
    while que:
        y, x = que.popleft()
        for i, j in zip(dx, dy):
            nx = x + i
            ny = y + j
            if 0 <= nx < w and 0 <= ny < h  and distance[ny][nx] == -1:
                distance[ny][nx] = distance[y][x] + 1
                que.append((ny, nx))
    return distance

d = bfs()
ans = 0
for row in d:
    ans = max(ans, max(row))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

field = [list(input()) for _ in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs():
    distance = [[-1]*w for _ in range(h)]
    que = deque([])
    for i in range(h):
        for j in range(w):
            if field[i][j] == '#':
                que.append((i, j))
                distance[i][j] = 0
    while que:
        y, x = que.popleft()
        for i, j in zip(dx, dy):
            nx = x + i
            ny = y + j
            if 0 <= nx < w and 0 <= ny < h and field[ny][nx] == "." and distance[ny][nx] == -1:
                distance[ny][nx] = distance[y][x] + 1
                que.append((ny, nx))
    return distance

d = bfs()
ans = 0
for row in d:
    ans = max(ans, max(row))
print(ans)

Submission status: Time Limit Exceeded

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

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

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))

q = []
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

ans = -1
while q:
  qq = []
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  ans += 1
  
print(ans)

Submission status: Time Limit Exceeded

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

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

# 番兵法 (#を外周に設置する)
visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))

# #の位置をqに格納
q = []
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

# dx,dyを使用せずにBFS 
# 定数倍改善
ans = -1
while q:
  qq = []
  # 新たに#となった地点をqqに格納
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  ans += 1
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
import sys
input = sys.stdin.readline
def main():
    q = queue.Queue()
    h,w=map(int,input().split())
    a=[list(input()) for i in range(h)]
    x=[[-1,0],[1,0],[0,-1],[0,1]]
    for i in range(h):
        for j in range(w):
            if a[i][j]=="#":
                for k in x:
                    if 0<=i+k[0]<h and 0<=j+k[1]<w and a[i+k[0]][j+k[1]]==".":
                        q.put([i+k[0],j+k[1],1])
    ans=0
    while not q.empty():
        v=q.get()
        for k in x:
            if 0<=v[0]+k[0]<h and 0<=v[1]+k[1]<w and a[v[0]+k[0]][v[1]+k[1]]==".":
                q.put([v[0]+k[0],v[1]+k[1],v[2]+1])
                ans=v[2]+1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
import sys
input = sys.stdin.readline
def main():
    q = queue.Queue()
    h,w=map(int,input().split())
    a=[list(input()) for i in range(h)]
    x=[[-1,0],[1,0],[0,-1],[0,1]]
    for i in range(h):
        for j in range(w):
            if a[i][j]=="#":
                a[i][j]=0
                for k in x:
                    if 0<=i+k[0]<h and 0<=j+k[1]<w and a[i+k[0]][j+k[1]]==".":
                        a[i+k[0]][j+k[1]]=1
                        q.put([i+k[0],j+k[1],1])
    ans=0
    while not q.empty():
        v=q.get()
        for k in x:
            if 0<=v[0]+k[0]<h and 0<=v[1]+k[1]<w and a[v[0]+k[0]][v[1]+k[1]]==".":
                a[v[0]+k[0]][v[1]+k[1]]=v[2]+1
                q.put([v[0]+k[0],v[1]+k[1],v[2]+1])
                ans=v[2]+1
    print(ans)
if __name__ == '__main__':
    main()