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:
H, W = map(int,input().split())
A = list(list(str(input())) for _ in range(H))
X = []

def count(A, value):
    return [i for i, x in enumerate(A) if x == value]

def black(X):
  for i in range(H):
    if len(count(A[i], '#')) != 0:
      for k in count(A[i], '#'):
        X.append([i, k])
  return X

def dist(i,j,X):
  Z = []
  for k in range(len(X)):
    Z.append(abs(i-X[k][0]) + abs(j-X[k][1]))
  z = min(Z)
  return z

Y = []
for i in range(H):
  for j in range(W):
    Y.append(dist(i,j,black(X)))
Y = [y for y in Y if y != 0]

if len(Y) == 0:
  print(0)
else:
  print(max(Y))

Submission status: Time Limit Exceeded

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

def main():
    H, W = map(int, input().split())
    a = [input().strip() for i in range(H)]

    INF = int(1e8)
    min_cost = [[INF] * W for i in range(H)]

    # q = []
    q = deque()
    for y in range(H):
        for x in range(W):
            if a[y][x] == "#":
                # heapq.heappush(q, (0, x, y))
                q.append((0, x, y))
    
    ans = 0
    while len(q) > 0:
        # cost, x, y = heapq.heappop(q)
        cost, x, y = q.popleft()
        # 最小コストでテーブルを更新
        if cost < min_cost[y][x]:
            ans = max(ans, cost)
            min_cost[y][x] = cost
            for nx, ny in [(x, y-1), (x+1, y), (x, y+1), (x-1, y)]:
                if 0 <= nx and nx < W and 0 <= ny and ny < H:
                    if cost + 1 < min_cost[ny][nx]:
                        # heapq.heappush(q, (cost+1, nx, ny))
                        q.append((cost+1, nx, ny))
    
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    H, W = map(int, input().split())
    a = [input().strip() for i in range(H)]

    INF = int(1e8)
    min_cost = [[INF] * W for i in range(H)]

    q = []
    for y in range(H):
        for x in range(W):
            if a[y][x] == "#":
                heapq.heappush(q, (0, x, y))
    
    ans = 0
    while len(q) > 0:
        cost, x, y = heapq.heappop(q)
        # 最小コストでテーブルを更新
        if cost < min_cost[y][x]:
            ans = max(ans, cost)
            min_cost[y][x] = cost
            for nx, ny in [(x, y-1), (x+1, y), (x, y+1), (x-1, y)]:
                if 0 <= nx and nx < W and 0 <= ny and ny < H:
                    if cost + 1 < min_cost[ny][nx]:
                        heapq.heappush(q, (cost+1, nx, ny))
    
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


#input
lines = [x.strip() for x in sys.stdin.readlines()]
h,w=[int(x) for x in lines[0].split()]
map=[[x for x in y] for y in lines[1:]]
memo=[[-1 for x in y] for y in lines[1:]]

def slv(lines):
    q=[]
    for x in range(w):
        for y in range(h):
            if map[y][x]=="#":
                memo[y][x]=0
                q.append([x,y])
    ans=0
    while q!=[]:
        x,y=q.pop(0)
        for d in [1,-1]:
            if w>x+d>=0 and map[y][x+d]=="." and memo[y][x+d]<0:
                q.append([x+d,y])
                memo[y][x+d]=memo[y][x]+1
            if h>y+d>=0 and map[y+d][x]=="." and memo[y+d][x]<0:
                q.append([x,y+d])
                memo[y+d][x]=memo[y][x]+1
            else:
                continue
            ans=max([ans,memo[y][x]+1])

    return ans

if __name__ == "__main__":
    print(slv(lines))

Submission status: Time Limit Exceeded

Solution code:
import sys


#input
lines = [x.strip() for x in sys.stdin.readlines()]
h,w=[int(x) for x in lines[0].split()]
map=[[x for x in y] for y in lines[1:]]
memo=[[-1 for x in y] for y in lines[1:]]

def slv(lines):
    q=[]
    for x in range(w):
        for y in range(h):
            if map[y][x]=="#":
                memo[y][x]=0
                q.append([x,y])

    while q!=[]:
        x,y=q.pop(0)
        for d in [1,-1]:
            if w>x+d>=0 and map[y][x+d]=="." and memo[y][x+d]<0:
                q.append([x+d,y])
                memo[y][x+d]=memo[y][x]+1
            if h>y+d>=0 and map[y+d][x]=="." and memo[y+d][x]<0:
                q.append([x,y+d])
                memo[y+d][x]=memo[y][x]+1

    return max([max(x) for x in memo])

if __name__ == "__main__":
    print(slv(lines))

Submission status: Time Limit Exceeded

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

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

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

q = collections.deque()
for i in range(1,H+1):
    for j in range(1,W+1):
        if b[i][j]:
            q.appendleft((i,j))
t = 0
while q:
    tmp = collections.deque()
    while q:
        i,j = q.pop()
        if not b[i-1][j]:
            b[i-1][j] = True
            tmp.appendleft((i-1,j))
        if not b[i][j-1]:
            b[i][j-1] = True
            tmp.appendleft((i,j-1))
        if not b[i][j+1]:
            b[i][j+1] = True
            tmp.appendleft((i,j+1))
        if not b[i+1][j]:
            b[i+1][j] = True
            tmp.appendleft((i+1,j))
    q = tmp
    t += 1

print(t-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    h, w = [int(i) for i in input().split()]
    f = []
    for i in range(h):
        f.append(list(input()))
    #カウンター用のフィールド
    d = [[-1 for j in range(w)] for i in range(h)]
    q = deque()
    for i in range(h):
        for j in range(w):
            if f[i][j] == '#':
                # スタート地点のメモ
                d[i][j] = 0
                q.appendleft((i, j))

    while q:
        y, x = q.pop()
        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 and d[ny][nx] == -1:
                d[ny][nx] = d[y][x] + 1
                q.appendleft((ny, nx))

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from heapq import heappush, heappop
    input = sys.stdin.readline
    H, W = map(int, input().split())
    D = [None]*H
    Q = []
    for h in range(H):
        D[h] = [10e10]*W
        l = input().strip()
        for w in range(W):
            if l[w] == "#":
                D[h][w] = 0
                Q.append((0, h, w))

    m = 0
    while Q:
        d, h, w = heappop(Q)
        alt = d+1
        m = max(m, d)
        for dx, dy in [(-1,0), (1,0), (0,-1), (0, +1)]:
            h1, w1 = h+dx, w+dy
            if 0 <= h1 < H and 0 <= w1 < W:
                if D[h1][w1] > alt:
                    D[h1][w1] = alt
                    heappush(Q, (alt, h1, w1))

    #for h in range(H): print(D[h])
    print(m)

main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

H, W = map(int, input().split())
grid = [0] * H
D = [None]*H
Q = []
for h in range(H):
    D[h] = [10**9]*W
    l = input().strip()
    for w in range(W):
        if l[w] == "#":
            D[h][w] = 0
            Q.append((0, h, w))
    grid[h] = l

m = 0
while Q:
    d, h, w = heappop(Q)
    m = max(m, d)
    for dx, dy in [(-1,0), (1,0), (0,-1), (0, +1)]:
        h1, w1 = h+dx, w+dy
        if 0 <= h1 < H and 0 <= w1 < W:
            if D[h1][w1] > d + 1:
                D[h1][w1] = d + 1
                heappush(Q, (d + 1, h1, w1))

#for h in range(H): print(D[h])
print(m)

Submission status: Time Limit Exceeded

Solution code:
import queue

Data = []
Path = []
H = 0
W = 0

def bfs():
    q = queue.Queue()

    left = H * W
    newtarget = 0
    for h in range(H):
        for w in range(W):
            if Data[h][w] == '#':
                q.put([h,w])
                left -= 1
                newtarget +=1

    diff = [[1,0],[-1,0],[0,1],[0,-1]]

    count = 0
    while left > 0:
        count += 1
       
        target = newtarget
        newtarget = 0
        for _ in range(target):
            h,w = q.get()

            for di in diff:
                hh = h + di[0]
                ww = w + di[1]

                if hh >= 0 and ww >= 0 and hh < H and ww < W:
                    if Data[hh][ww] == '.':
                        Data[hh][ww] = '#'
                        left -= 1
                        newtarget += 1
                        q.put([hh,ww])
    return count


H,W = map(int,input().split())
for _ in range(H):
    Data.append(list(input()))
for r in range(H):
    Path.append([-1]*W)
ans = bfs()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    h, w = [int(i) for i in input().split()]
    f = []
    black = deque()
    for i in range(h):
        line = list(input())
        for j, c in enumerate(line):
            if c == '#':
                black.appendleft((i, j))
        f.append(line)
    ans = 0
    d = [[False for i in range(w)] for j in range(h)]
    black.appendleft((-1, -1))
    sw = False
    while black:
        y, x = black.pop()
        if (y, x) == (-1, -1) and sw:
            break
        else:
            sw = False
        if (y, x) == (-1, -1):
            sw = True
            ans += 1
            black.appendleft((-1, -1))
        for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            if 0 <= y+dy < h and 0 <= x+dx < w and f[y+dy][x+dx] == '.' and \
                d[y+dy][x+dx] == False:
                f[y+dy][x+dx] = '#'
                d[y+dy][x+dx] = True
                black.appendleft((y+dy, x+dx))
    print(ans-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    h, w = [int(i) for i in input().split()]
    f = []
    black = deque()
    for i in range(h):
        line = list(input())
        for j, c in enumerate(line):
            if c == '#':
                black.appendleft((i, j))
        f.append(line)
    ans = 0
    black.appendleft((-1, -1))
    sw = False
    while black:
        y, x = black.pop()
        if (y, x) == (-1, -1) and sw:
            break
        else:
            sw = False
        if (y, x) == (-1, -1):
            sw = True
            ans += 1
            black.appendleft((-1, -1))
        for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            if 0 <= y+dy < h and 0 <= x+dx < w and f[y+dy][x+dx] == '.':
                f[y+dy][x+dx] = '#'
                black.appendleft((y+dy, x+dx))
    print(ans-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    h, w = [int(i) for i in input().split()]
    f = []
    black = deque()
    for i in range(h):
        line = list(input())
        for j, c in enumerate(line):
            if c == '#':
                black.append((i, j))
        f.append(line)
    ans = 0
    while True:
        q = deque()
        while black:
            y, x = black.pop()
            for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                if 0 <= y+dy < h and 0 <= x+dx < w and f[y+dy][x+dx] == '.':
                    q.appendleft((y+dy, x+dx))
        if not q:
            break
        ans += 1
        while q:
            y, x = q.pop()
            f[y][x] = '#'
            black.appendleft((y,x))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
def solve():
  h,w = (int(i) for i in input().split())
  maze = ["0"*(w+2)]
  for i in range(h):
    maze.append("0"+input()+"0")
  maze.append("0"*(w+2))
  black = deque([])
  count = 0
  visit = [[False]*(w+2) for _ in range(h+2)]
  
  for i in range(h+2):
    for j in range(w+2):
      if maze[i][j] == "#":
        black.append((0,i,j)) #move,h,w

  d = [(0,1),(1,0),(-1,0),(0,-1)]
  ans = 0
  
  while count != h*w:
    move,y,x = black.popleft()
    #print(move,y,x)
    if visit[y][x]:
      continue
    else:
      visit[y][x] = True
      count += 1
      for dy,dx in d:
        ny,nx = y+dy,x+dx
        if visit[ny][nx]:
          continue
        elif maze[ny][nx] ==".":
          black.append((move+1,ny,nx))
  print(move)
          

    
solve()

Submission status: Time Limit Exceeded

Solution code:
import heapq

def solve():
  h,w = (int(i) for i in input().split())
  maze = ["0"*(w+2)]
  for i in range(h):
    maze.append("0"+input()+"0")
  maze.append("0"*(w+2))
  black = []
  count = 0
  visit = [[False]*(w+2) for _ in range(h+2)]
  
  for i in range(h+2):
    for j in range(w+2):
      if maze[i][j] == "#":
        heapq.heappush(black,(0,i,j)) #move,h,w

  d = [(0,1),(1,0),(-1,0),(0,-1)]
  ans = 0
  
  while count != h*w:
    move,y,x = heapq.heappop(black)
    #print(move,y,x)
    if visit[y][x]:
      continue
    else:
      visit[y][x] = True
      count += 1
      for dy,dx in d:
        ny,nx = y+dy,x+dx
        if visit[ny][nx]:
          continue
        elif maze[ny][nx] ==".":
          heapq.heappush(black,(move+1,ny,nx))
  print(move)
          

    
solve()

Submission status: Time Limit Exceeded

Solution code:
import heapq

def solve():
  h,w = (int(i) for i in input().split())
  maze = ["0"*(w+2)]
  for i in range(h):
    maze.append("0"+input()+"0")
  maze.append("0"*(w+2))
  black = []
  count = 0
  visit = [[False]*(w+2) for _ in range(h+2)]
  for i in range(h+2):
    for j in range(w+2):
      if maze[i][j] == "#":
        heapq.heappush(black,(0,i,j)) #move,h,w

  d = [(1,0),(0,1),(-1,0),(0,-1)]
  ans = 0
  
  while count != h*w:
    move,y,x = heapq.heappop(black)
    #print(move,y,x)
    if visit[y][x]:
      continue
    else:
      visit[y][x] = True
      count += 1
      for dy,dx in d:
        ny,nx = y+dy,x+dx
        if visit[ny][nx]:
          continue
        elif maze[ny][nx] =="0" or maze[ny][nx] == "#":
          continue
        else:
          heapq.heappush(black,(move+1,ny,nx))
  print(move)
          

    
solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
# from bisect import *
# from collections import *
# from copy import deepcopy
# from heapq import *
# from itertools import *
# from math import *
# from operator import *
# from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    H,W = map(int, input().split())
    grid = [list(input().rstrip()) for _ in range(H)]
    q = []
    visited = [[False]*W for _ in range(H)]
    for y in range(H):
        for x in range(W):
            if grid[y][x] == '#':
                q.append((y,x))
                visited[y][x] = True
    ans = -1
    while q:
        ans += 1
        new_q = []
        for y,x in q:
            for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
                ny = y+dy
                nx = x+dx
                if 0<=ny<H and 0<=nx<W and not visited[ny][nx]:
                    new_q.append((ny,nx))
                    visited[ny][nx] = True
        if new_q:
            q = new_q
        else:
            break
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    H,W = map(int, input().split())
    grid = [list(input().rstrip()) for _ in range(H)]
    q = []
    visited = [[False]*W for _ in range(H)]
    for y in range(H):
        for x in range(W):
            if grid[y][x] == '#':
                q.append((y,x))
                visited[y][x] = True
    ans = -1
    while q:
        ans += 1
        new_q = []
        for y,x in q:
            for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
                ny = y+dy
                nx = x+dx
                if 0<=ny<H and 0<=nx<W and not visited[ny][nx]:
                    new_q.append((ny,nx))
                    visited[ny][nx] = True
        if new_q:
            q = new_q
        else:
            break
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *
import numpy as np

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    H, W = map(int,input().split())
    visited = [[False]*W for _ in range(H)]
    q = []
    for y in range(H):
        S = input().rstrip()
        for x, s in enumerate(S):
            if s == "#":
                q.append((y, x))
                visited[y][x] = True

    ans = -1
    while q:
        ans += 1
        nq = []
        for y, x in q:
            if 0 < x and not visited[y][x-1]:
                visited[y][x-1] = True
                nq.append((y,x-1))
            if x < W-1 and not visited[y][x+1]:
                visited[y][x+1] = True
                nq.append((y,x+1))
            if 0 < y and not visited[y-1][x]:
                visited[y-1][x] = True
                nq.append((y-1, x))
            if y < H-1 and not visited[y+1][x]:
                visited[y+1][x] = True
                nq.append((y+1,x))
        if nq:
            q = nq
        else:
            break

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *
import numpy as np

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    H,W = map(int, input().split())
    visited = [[False]*W for _ in range(H)]
    q = []
    for y in range(H):
        for x, val in enumerate(list(input().rstrip())):
            if val == '#':
                q.append((y,x))
                visited[y][x] = True
    ans = -1
    while q:
        ans += 1
        new_q = []
        for y,x in q:
            if 0 < y and not visited[y-1][x]:
                new_q.append((y-1,x))
                visited[y-1][x] = True
            if y < H-1 and not visited[y+1][x]:
                new_q.append((y+1,x))
                visited[y+1][x] = True
            if 0 < x and not visited[y][x-1]:
                new_q.append((y,x-1))
                visited[y][x-1] = True
            if x < W-1 and not visited[y][x+1]:
                new_q.append((y,x+1))
                visited[y][x+1] = True
        if new_q:
            q = new_q[:]
        else:
            break
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *
import numpy as np

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    H,W = map(int, input().split())
    visited = [[False]*W for _ in range(H)]
    q = []
    for y in range(H):
        for x, val in enumerate(list(input().rstrip())):
            if val == '#':
                q.append((y,x))
                visited[y][x] = True
    ans = -1
    while q:
        ans += 1
        new_q = []
        for y,x in q:
            for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
                ny = y+dy
                nx = x+dx
                if 0<=ny<H and 0<=nx<W and not visited[ny][nx]:
                    new_q.append((ny,nx))
                    visited[ny][nx] = True
        if new_q:
            q = new_q[:]
        else:
            break
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *
import numpy as np

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    H,W = map(int, input().split())
    grid = [list(input().rstrip()) for _ in range(H)]
    q = []
    visited = [[False]*W for _ in range(H)]
    for y in range(H):
        for x in range(W):
            if grid[y][x] == '#':
                q.append((y,x))
                visited[y][x] = True
    ans = -1
    while q:
        ans += 1
        new_q = []
        for y,x in q:
            for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
                ny = y+dy
                nx = x+dx
                if 0<=ny<H and 0<=nx<W and not visited[ny][nx] and grid[ny][nx] == '.':
                    new_q.append((ny,nx))
                    visited[ny][nx] = True
        if new_q:
            q = new_q
        else:
            break
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *
import numpy as np

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    H,W = map(int, input().split())
    grid = [list(input().rstrip()) for _ in range(H)]
    q = []
    visited = [[False]*W for _ in range(H)]
    for y in range(H):
        for x in range(W):
            if grid[y][x] == '#':
                q.append((y,x))
                visited[y][x] = True
    ans = -1
    while q:
        ans += 1
        new_q = []
        for y,x in q:
            for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
                ny = y+dy
                nx = x+dx
                if 0<=ny<H and 0<=nx<W and not visited[ny][nx] and grid[ny][nx] == '.':
                    new_q.append((ny,nx))
                    visited[ny][nx] = True
        if new_q:
            q = new_q[:]
        else:
            break
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *
import numpy as np

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    H,W = map(int, input().split())
    grid = [list(input().rstrip()) for _ in range(H)]
    q = deque()
    visited = [[False]*W for _ in range(H)]
    black_cnt = 0
    ans = 0
    for y in range(H):
        for x in range(W):
            if grid[y][x] == '#':
                q.append((y,x,0))
                visited[y][x] = True
                black_cnt += 1
    while q:
        y,x,step = q.popleft()
        ans = step
        for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
            ny = y+dy
            nx = x+dx
            if 0<=ny<H and 0<=nx<W and not visited[ny][nx]:
                q.append((ny,nx,step+1))
                visited[ny][nx] = True
                black_cnt += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *
import numpy as np

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    H,W = map(int, input().split())
    grid = [list(input().rstrip()) for _ in range(H)]
    ans = 0
    while True:
        new_grid = [['.']*W for _ in range(H)]
        black_cnt = 0
        for y in range(H):
            for x in range(W):
                if grid[y][x] == '#':
                    black_cnt += 1
                    new_grid[y][x] = '#'
                    for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
                        ny = y+dy
                        nx = x+dx
                        if 0<=ny<H and 0<=nx<W:
                            new_grid[ny][nx] = '#'
        if black_cnt == W*H: break

        ans += 1
        grid = deepcopy(new_grid)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

H, W = map(int, input().split())
a = [list(input()) for _ in range(H)]
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
que = deque([(i, j) for i in range(H) for j in range(W) if a[i][j] == '#'])
count = 0

flag_all = False

while True:
	count += 1

	que_next = deque()
	while que:
		i, j = que.popleft()
		for k in range(4):
			dx, dy = d[k][0], d[k][1]
			x = i + dx
			y = j + dy
			if x >= 0 and x < H and y >= 0 and y < W and a[x][y] != '#':
				a[x][y] = '#'
				que_next.append((x, y))

	que = copy.copy(que_next)

	if que:
		que = copy.copy(que_next)
	else:
		break
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

H, W = map(int, input().split())
a = [list(input()) for _ in range(H)]
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
que = deque([(i, j) for i in range(H) for j in range(W) if a[i][j] == '#'])
count = 0

flag_all = False

while True:
	count += 1

	que_next = deque()
	while que:
		i, j = que.popleft()
		for k in range(4):
			dx, dy = d[k][0], d[k][1]
			x = i + dx
			y = j + dy
			if x >= 0 and x < H and y >= 0 and y < W and a[x][y] != '#':
				a[x][y] = '#'
				que_next.append((x, y))

	que = copy.copy(que_next)

	if not que:
		break
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    H,W = map(int, input().split())

    A = [[a for a in input()] for _ in range(H)]
    stack = deque([(i, j) for i in range(H) for j in range(W) if A[i][j]=="#"])
    
    ans = 0
    flag = False
    if stack:
        flag = True
    while flag:
        ans += 1
        flag = False
        new_stack = deque()
        #for a,b in stack:
        while stack:
            a,b = stack.pop() # 取り出す
            # A[a][b]の隣接マスについて調べる
             # 上
            if a != 0 and A[a-1][b] == ".": # 白の場合
                    A[a-1][b] = "#"
                    new_stack.append((a-1,b))
             # 下
            if a != H-1 and A[a+1][b] == ".": # 白の場合
                    A[a+1][b] = "#"
                    new_stack.append((a+1,b))
            # 左
            if b != 0 and A[a][b-1] == ".": # 白の場合
                    A[a][b-1] = "#"
                    new_stack.append((a,b-1))
            # 右
            if b != W-1 and A[a][b+1] == ".": # 白の場合
                    A[a][b+1] = "#"
                    new_stack.append((a,b+1))
        stack = new_stack
        if stack:
            flag = True
        else:
            ans -= 1 

    print(ans)
            


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    H,W = map(int, input().split())

    A = [[a for a in input()] for _ in range(H)]
    stack = deque([(i, j) for i in range(H) for j in range(W) if A[i][j]=="#"])
    """
    stack = deque()
    for i in range(H):
        tmp = list(input())
        for j in range(W):
            A[i][j] = tmp[j]
            if tmp[j] == "#":
                stack.append((i,j))
    """
    ans = 0
    flag = False
    if stack:
        flag = True
    while flag:
        ans += 1
        #print(ans, stack)
        flag = False
        new_stack = deque()
        #for a,b in stack:
        while stack:
            a,b = stack.pop() # 取り出す
            # A[a][b]の隣接マスについて調べる
            if a != 0: # 上
                if A[a-1][b] == ".": # 白の場合
                    A[a-1][b] = "#"
                    new_stack.append((a-1,b))
            if a != H-1: # 下
                if A[a+1][b] == ".": # 白の場合
                    A[a+1][b] = "#"
                    new_stack.append((a+1,b))
            if b != 0: # 左
                if A[a][b-1] == ".": # 白の場合
                    A[a][b-1] = "#"
                    new_stack.append((a,b-1))
            if b != W-1: # 右
                if A[a][b+1] == ".": # 白の場合
                    A[a][b+1] = "#"
                    new_stack.append((a,b+1))
        stack = new_stack
        if stack:
            flag = True
        else:
            ans -= 1 

    print(ans)
            


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    H,W = map(int, input().split())

    A = [[a for a in input()] for _ in range(H)]
    stack = deque([(i, j) for i in range(H) for j in range(W) if A[i][j]=="#"])
    """
    stack = deque()
    for i in range(H):
        tmp = list(input())
        for j in range(W):
            A[i][j] = tmp[j]
            if tmp[j] == "#":
                stack.append((i,j))
    """
    ans = 0
    flag = False
    if stack:
        flag = True
    while flag:
        ans += 1
        #print(ans, stack)
        flag = False
        new_stack = deque()
        for a,b in stack:
            #a,b = stack.pop() # 取り出す
            # A[a][b]の隣接マスについて調べる
            if a != 0: # 上
                if A[a-1][b] == ".": # 白の場合
                    A[a-1][b] = "#"
                    new_stack.append((a-1,b))
            if a != H-1: # 下
                if A[a+1][b] == ".": # 白の場合
                    A[a+1][b] = "#"
                    new_stack.append((a+1,b))
            if b != 0: # 左
                if A[a][b-1] == ".": # 白の場合
                    A[a][b-1] = "#"
                    new_stack.append((a,b-1))
            if b != W-1: # 右
                if A[a][b+1] == ".": # 白の場合
                    A[a][b+1] = "#"
                    new_stack.append((a,b+1))
        stack = new_stack
        if stack:
            flag = True
        else:
            ans -= 1 

    print(ans)
            


if __name__ == "__main__":
    main()