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()
blacks = list()
for i in range(H):
    s = input()
    for j, c in enumerate(s):
        if c == '#':
            blacks.append((i, j))
    A.append(s)

ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == '.':
            dist = float('inf')
            for bi, bj in blacks:
                dist = min(dist, abs(bi - i) + abs(bj - j))
            ans = max(ans, dist)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
s = set()
for i in range(H):
    for j, c in enumerate(input()):
        if c == '#':
            s.add((i, j))

cnt = 0
while len(s) < H * W:
    ns = set()
    for i, j in s:
        ns.add((i, j))
        if i > 0:
            ns.add((i - 1, j))
        if j > 0:
            ns.add((i, j - 1))
        if i < H - 1:
            ns.add((i + 1, j))
        if j < W - 1:
            ns.add((i, j + 1))
    s = ns
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

h, w = map(int, input().split())
field = []
todo = deque([])

for y in range(h):
    text = input()
    field.append(text)
    for x in range(w):
        if text[x] == '#':
            todo.append([y, x])

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

seen = [[None] * w for _ in range(h)]

for y, x in todo:
    seen[y][x] = 0

while todo:
    y, x = todo.popleft()

    for i in range(4):
        ny, nx = y + dy[i], x + dx[i]

        if ny < 0 or h <= ny or nx < 0 or w <= nx:
            continue
        elif seen[ny][nx] is not None:
            continue
        else:
            seen[ny][nx] = seen[y][x] + 1
            todo.append([ny, nx])

    if not todo:
        print(seen[y][x])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy
H,W = list(map(int,input().split()))
A = [input().split() for i in range(H)]
place_h = [0,-1,0,1]
place_w = [1,0,-1,0]
black = 0
q = []
dist = [[-1 for i in range(W)] for j in range(H)]
for i in range(H):
    A[i] = list(A[i][0])
    for j in range(W):
        if A[i][j] == "#":
            black += 1
            q.append(deque([[i,j]]))
            dist[i][j] = 0

while len(q)>0:
    i = 0
    while i < black:
        if len(q[i]) == 0:
            q.pop(i)
            black -= 1
            continue
        vh,vw = q[i].popleft()
        for m in range(4):
            nvh = vh+place_h[m]
            nvw = vw+place_w[m]
            if 0<=nvh<H and 0<=nvw<W and dist[nvh][nvw] == -1:
                q[i].append([nvh,nvw])
                dist[nvh][nvw] = dist[vh][vw]+1
        i+=1
print(numpy.amax(dist))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W = map(int, input().split())
A = [[] for _ in range(H)]
inf = 1000000007
for i in range(H):
    A[i] = list(input())
    for j in range(W):
        if A[i][j] == '.':
            A[i][j] = inf
        elif A[i][j] == '#':
            A[i][j] = 0

#print(A)

for i in range(H):
    for j in range(1, W):
        A[i][j] = min(A[i][j-1]+1, A[i][j])

#print(A)


for i in range(H):
    for j in range(W-2, -1, -1):
        A[i][j] = min(A[i][j+1]+1, A[i][j])

#print(A)

for i in range(1, H):
    for j in range(0, W):
        A[i][j] = min(A[i-1][j]+1, A[i][j])

#print(A)

for i in range(H-2, -1, -1):
    for j in range(W):
        A[i][j] = min(A[i+1][j]+1, A[i][j])

#print(A)

ans_list = []

for i in range(H):
    ans_list.append(max(A[i]))

print(max(ans_list))

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy

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

#print(*b, sep='\n')

cnt=0

while 1:
    for y in range(h):
        for x in range(w):
            if a[y][x]=="#":
                a[y][x] = cnt
                
            if a[y][x] == cnt:
                flag = 1
                #print(x,y)
                if x!=0:
                    if a[y][x-1] == ".":
                        a[y][x-1]=cnt+1
                if x!=w-1:
                    if a[y][x+1] == ".":
                        a[y][x+1]=cnt+1
                if y!=0:
                    if a[y-1][x] == ".":
                        a[y-1][x]=cnt+1
                if y!=h-1:
                    if a[y+1][x] == ".":
                        a[y+1][x]=cnt+1

    if flag==0:
        print(cnt-1)
        sys.exit()

    cnt+=1
    flag = 0

Submission status: Time Limit Exceeded

Solution code:
import queue
h,w = map(int,input().split())
q = queue.Queue()
l = []
for i in range(h):
    a = list(input())
    for j in range(w):
        if a[j] == "#":
            q.put([i,j])
    l.append(a)    
c = [1,0,-1,0]
d = [0,1,0,-1]
count = 0
while not q.empty():
    q2 = queue.Queue()
    while not q.empty() > 0:
        b = q.get()
        for i in range(4):
            if b[0]+c[i] >= 0 and b[1]+d[i] >= 0 and b[0]+c[i] < h and b[1]+d[i] < w:
                if l[b[0]+c[i]][b[1]+d[i]] == ".":
                    q2.put([b[0]+c[i],b[1]+d[i]])
                    l[b[0]+c[i]][b[1]+d[i]] = "#"
    q = q2
    count = count + 1
    """for i in range(h):
        for x in l[i]:
            print(x,end="")
        print()
    print()"""
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
h,w = map(int,input().split())
q = deque()
l = []
for i in range(h):
    a = list(input())
    for j in range(w):
        if a[j] == "#":
            q.append([i,j])
    l.append(a)    
c = [1,0,-1,0]
d = [0,1,0,-1]
count = 0
while len(q) > 0:
    q2 = deque()
    while len(q) > 0:
        b = q.popleft()
        for i in range(4):
            if b[0]+c[i] >= 0 and b[1]+d[i] >= 0 and b[0]+c[i] < h and b[1]+d[i] < w:
                if l[b[0]+c[i]][b[1]+d[i]] == ".":
                    q2.append([b[0]+c[i],b[1]+d[i]])
                    l[b[0]+c[i]][b[1]+d[i]] = "#"
    q = q2
    count = count + 1
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = tuple(tuple(input()) for _ in range(H))
next_q = [(i, j) for i in range(H) for j in range(W) if A[i][j] == '#']
L = [[0] * W for _ in range(H)]

res = 0
while len(next_q) != 0:
    q, next_q = next_q[:], []
    while len(q) != 0:
        y, x = q.pop(0)
        if y > 0 and L[y - 1][x] == 0:
            L[y - 1][x] = 1
            next_q.append((y - 1, x))
        if y < H - 1 and L[y + 1][x] == 0:
            L[y + 1][x] = 1
            next_q.append((y + 1, x))
        if x > 0 and L[y][x - 1] == 0:
            L[y][x - 1] = 1
            next_q.append((y, x - 1))
        if x < W - 1 and L[y][x + 1] == 0:
            L[y][x + 1] = 1
            next_q.append((y, x + 1))
    if len(next_q) == 0: break
    res += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
def check(before_masu, after_masu, count):
  hata=0
  for i in range(h):
    for n in range(w):
      if before_masu[i][n] == '#':
        after_masu[i][n] = '#'
        if i-1 >-1:
          after_masu[i-1][n] = '#'
        if i+1 < h:
          after_masu[i+1][n] = '#'
        if n-1 > -1:
          after_masu[i][n-1] = '#'
        if n+1 < w:
          after_masu[i][n+1] = '#'
  for i in before_masu:
    for n in i:
      if n != '#':
        hata=1
  if hata==0:
    print(count)
  else:
    check(after_masu, before_masu, count+1)
h, w = map(int, input().split())
before_masu = [[0 for i in range(w)] for n in range(h)]
after_masu = [[0 for i in range(w)] for n in range(h)]
for i in range(h):
  line = list(input())
  for n in range(w):
    before_masu[i][n] = line[n]
check(before_masu, after_masu, 0)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
H,W=map(int,input().split())
A=[list(input()) for _ in range(H)]
B=[[0]*W for _ in range(H)]
L=[]
ans=0
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            B[i][j]==1
            L.append([i,j])
while True:
    LL=[]
    for l in L:
        h,w=l[0],l[1]
        if h!=0:
            if B[h-1][w]==0:
                LL.append([h-1,w])
                B[h-1][w]=1
        if h!=H-1:
            if B[h+1][w]==0:
                LL.append([h+1,w])
                B[h+1][w]=1
        if w!=0:
            if B[h][w-1]==0:
                LL.append([h,w-1])
                B[h][w-1]=1
        if w!=W-1:
            if B[h][w+1]==0:
                LL.append([h,w+1])
                B[h][w+1]=1
    if LL==[]:
        break
    else:
        ans+=1
        L=LL
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

c = [[10**9 for _ in range(W)] for _ in range(H)]
que = deque()

for i in range(H):
  for j in range(W):
    if maze[i][j] == "#":
      c[i][j] = 0
      que.append([i, j])

dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]      
      
while len(que) != 0:
  p = que.popleft()
  for i in dxy:
    nx = p[0] + i[0]
    ny = p[1] + i[1]
    if 0 <= nx < H and 0 <= ny < W and c[nx][ny] == 10**9 and maze[nx][ny] ==".":
      maze[nx][ny] = "#"
      c[nx][ny] = c[p[0]][p[1]] + 1
      que.append([nx, ny])
max = 0
for i in range(H):
  for j in range(W):
    if max < c[i][j]:
      max = c[i][j]
print(max)

Submission status: Time Limit Exceeded

Solution code:
def bfs(start, count):
    global visited, color
    temp = []
    for hh, ww in start:
        if (hh in range(h)) & (ww in range(w)):
            color[hh][ww] = min(count, color[hh][ww])
            visited.add(str(hh) + "_" + str(ww))
            h_w_list = [[hh + 1, ww], [hh, ww + 1], [hh - 1, ww], [hh, ww - 1]]
            for h_, w_ in h_w_list:
                if (str(h_) + "_" + str(w_)) not in visited:
                    if (h_ in range(h)) & (w_ in range(w)):
                        temp.append([h_, w_])
    if len(temp) > 0:
        bfs(temp, count + 1)

inf = 10 ** 9
h, w = map(int, input().split())
a = []
for _ in range(h):
    a.append(list(input()))
color = [[inf for _ in range(w)] for _ in range(h)]
start = []
visited = set([])
for hh in range(h):
    for ww in range(w):
        if a[hh][ww] == "#":
            start.append([hh, ww])
            color[hh][ww] = 0
bfs(start, 0)
colored = []
for c in color:
    colored.extend(c)
print(max(colored))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque
H, W = [int(x) for x in stdin.readline().rstrip().split()]

data = []

for _ in range(H):
    data.append(list(input()))

searched = [[0]*(W+2)]

for _ in range(H):
    searched.append([0] + [1000000]*W + [0])
searched.append([0]*(W+2))

visit_p = deque()
for h,i in enumerate(data):
    for w, j in enumerate(i):
        if j == "#":
            searched[h+1][w+1] = 0
            visit_p.append((h+1, w+1, 0))
while visit_p:
    nh,nw,num = visit_p.popleft()
    if searched[nh][nw] < num:
        continue
    for dh,dw in [(0,1),(1,0),(0,-1),(-1,0)]:
        if searched[nh+dh][nw+dw] > num:
            searched[nh+dh][nw+dw] = num + 1
            visit_p.append((nh+dh,nw+dw,num+1))
print(max(map(max, searched)))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque
H, W = [int(x) for x in stdin.readline().rstrip().split()]

data = []

for _ in range(H):
    data.append(list(input()))

searched = [[0]*(W+2)]

for _ in range(H):
    searched.append([0] + [1000000]*W + [0])
searched.append([0]*(W+2))

visit_p = deque()
for h,i in enumerate(data):
    for w, j in enumerate(i):
        if j == "#":
            searched[h+1][w+1] = 0
            visit_p.append((h+1, w+1, 0))
while visit_p:
    nh,nw,num = visit_p.popleft()
    for dh,dw in [(0,1),(1,0),(0,-1),(-1,0)]:
        if searched[nh+dh][nw+dw] > num:
            searched[nh+dh][nw+dw] = num + 1
            visit_p.append((nh+dh,nw+dw,num+1))
print(max(map(max, searched)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from copy import *

H, W = map(int, input().split())
A = [input() for i in range(H)]
q = deque()
c = [[-1] * W for i in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            q.append((i, j))
            c[i][j] = 0
D = [[0, 1], [1, 0], [0, -1], [-1, 0]]
while q:
    y, x = q.popleft()
    for dy, dx in D:
        ny, nx = y+dy, x+dx
        if 0 <= ny < H and 0 <= nx < W and c[ny][nx] == -1:
            q.append((ny, nx))
            c[ny][nx] = c[y][x]+1
print(max([max(l) for l in c]))

Submission status: Time Limit Exceeded

Solution code:
# AGC033A - Darker and Darker
# https://docs.scipy.org/doc/scipy/reference/generated/scipy.ndimage.distance_transform_bf.html
from scipy.ndimage import distance_transform_bf as dist


def main():
    """
    distance_transform_bf:
        orig     taxicab / chessboard / euclidean
        1 1 1     2 1 2      1 1 1      1.4 1 1.4
        1 0 1 ->  1 0 1      1 0 1       1  0  1
        1 1 1     2 1 2      1 1 1      1.4 1 1.4
    """
    h, w = tuple(map(int, input().rstrip().split()))
    A = tuple(tuple(input()) for _ in range(h))
    B = tuple(tuple(1 if i == "." else 0 for i in a) for a in A)
    D = dist(B, metric="taxicab")
    print(D.max())


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
a=[]
for i in range(h):
  a.append([it == '#' for it in input()])
q=[]
for i in range(h):
  for j in range(w):
    if a[i][j]: q.append((i, j))
cnt = -1
while q:
  cnt += 1
  r = []
  for i, j in q:
    if i > 0 and not a[i-1][j]:
      a[i-1][j]=True
      r += [(i-1, j)]
    if i < h-1 and not a[i+1][j]:
      a[i+1][j]=True
      r += [(i+1, j)]
    ai = a[i]
    if j > 0 and not ai[j-1]:
      ai[j-1]=True
      r += [(i, j-1)]
    if j < w-1 and not ai[j+1]:
      ai[j+1]=True
      r += [(i, j+1)]
  q=r
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from sys import stdin

dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)

N, M = [int(_) for _ in stdin.readline().rstrip().split()]
graph = []

def bfs(graph, N, M):
    for _ in range(N):
        n = list(stdin.readline().rstrip())
        graph.append(n)

    ans = 0
    que = deque()
    dist = [[-1 for i in range(M)] for j in range(N)]
    for i in range(N):
        for j in range(M):
            if graph[i][j] == '#':
                que.append((i, j)) 
                dist[i][j] = 0

    while len(que):
        v = que.popleft()
        for d in range(4):
            nx = v[0] + dx[d]
            ny = v[1] + dy[d]
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[v[0]][v[1]] + 1
                que.append((nx, ny))

    for i in range(N):
        for j in range(M):
            ans = max(ans, dist[i][j])

    return ans

ans = bfs(graph, N, M)
print(ans)

Submission status: Time Limit Exceeded

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

table = ["" for i in range(H)]


for i in range(H):
    table[i] = input()

black = []
for row in range(H):
    for col in range(W):
        if table[row][col] == "#":
            black.append((row, col))

# print(black)

distanse = 0
for row in range(H):
    for col in range(W):
        if table[row][col] == "#":
            continue
        distanselist = [abs(i - row) + abs(j - col) for i, j in black]
        temp = min(distanselist)
        # print(distanselist)
        # print(temp)
        if distanse < temp:
            distanse = temp

print(distanse)

Submission status: Time Limit Exceeded

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

pre_list = []
# set start point
for iidx, i in enumerate(C):
    for tidx, t in enumerate(i):
        if t == '#':
            pre_list.append((iidx, tidx))
            C[iidx][tidx] = 0

# bfs 
count = 0
 
while len(pre_list) > 0:
    count += 1
    next_list = []
    for y,x in pre_list:
        for i,j in ((1,0),(0,-1),(0,1),(-1,0)):
            if y+i < 0 or x+j < 0 or y+i >= H or x+j >= W:
                continue
            if C[y+i][x+j] == '.':
                C[y+i][x+j] = count
                next_list.append((y+i,x+j))
    pre_list = next_list
print(count-1)

Submission status: Time Limit Exceeded

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

pre_list = []
# set start point
for iidx, i in enumerate(C):
    for tidx, t in enumerate(i):
        if t == '#':
            pre_list.append((iidx, tidx))
            C[iidx][tidx] = 0

# bfs 
count = 0
 
while len(pre_list) > 0:
    count += 1
    next_list = []
    for y,x in pre_list:
        for i,j in ((1,0),(0,-1),(0,1),(-1,0)):
            if y+i < 0 or x+j < 0 or y+i >= H or x+j >= W:
                continue
            if C[y+i][x+j] == '.':
                C[y+i][x+j] = "count"
                next_list.append((y+i,x+j))
    pre_list = next_list
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
C = [list(input()) for i in range(H)]
X = [1,0,-1,0]
Y = [0,-1,0,1]
Q = deque()
dist = [[99999]*W for i in range(H)]
for i in range(H):
  for j in range(W):
    if C[i][j] == "#":
      dist[i][j] = 0
      Q.append((i,j))
      while Q:
        y,x = Q.popleft()
        for k in range(4):
          ny = y + Y[k]
          nx = x + X[k]
          if not (0 <= nx < W):
            continue
          if not (0 <= ny < H):
            continue
          if not (C[ny][nx] == "."):
            continue
          if not (dist[ny][nx] > dist[y][x]+1):
            continue
          Q.append((ny,nx))
          dist[ny][nx] = dist[y][x] + 1
ans = 0
for i in range(H):
  ans = max(ans,max(dist[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
H, W = map(int, input().split())
C = [list(input()) for i in range(H)]
X = [1,0,-1,0]
Y = [0,-1,0,1]
Q = deque()
dist = [[99999]*W for i in range(H)]
for i in range(H):
  for j in range(W):
    if C[i][j] == "#":
      dist[i][j] = 0
      Q.append((i,j))
      while Q:
        y,x = Q.popleft()
        for k in range(4):
          ny = y + Y[k]
          nx = x + X[k]
          if not (0 <= nx < W):
            continue
          if not (0 <= ny < H):
            continue
          if not (C[ny][nx] == "."):
            continue
          if not (dist[ny][nx] > dist[y][x]+1):
            continue
          Q.append((ny,nx))
          dist[ny][nx] = dist[y][x] + 1
ans = 0
for i in range(H):
  ans = max(ans,max(dist[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
H, W = map(int, input().split())
C = [list(input()) for i in range(H)]
X = [1,0,-1,0]
Y = [0,-1,0,1]
Q = deque()
dist = [[0]*W for i in range(H)]
for i in range(H):
  for j in range(W):
    if C[i][j] == "#":
      Q.append((i,j))
      while Q:
        y,x = Q.popleft()
        for k in range(4):
          ny = y + Y[k]
          nx = x + X[k]
          if not (0 <= nx < W):
            continue
          if not (0 <= ny < H):
            continue
          if not (C[ny][nx] == "."):
            continue
          if not (dist[ny][nx] == 0 or dist[ny][nx] > dist[y][x]+1):
            continue
          Q.append((ny,nx))
          dist[ny][nx] = dist[y][x] + 1
ans = 0
for i in range(H):
  ans = max(ans,max(dist[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
H, W = map(int, input().split())
C = [list(input()) for i in range(H)]
X = [1,0,-1,0]
Y = [0,-1,0,1]
Q = deque()
dist = [[0]*W for i in range(H)]
for i in range(H):
  for j in range(W):
    if C[i][j] == "#":
      Q.append((i,j))
      while Q:
        y,x = Q.popleft()
        for k in range(4):
          ny = y + Y[k]
          nx = x + X[k]
          if (0 <= nx < W) and (0 <= ny < H) and (C[ny][nx] == ".") and (dist[ny][nx] == 0 or dist[ny][nx] > dist[y][x]+1):
            Q.append((ny,nx))
            dist[ny][nx] = dist[y][x] + 1
ans = 0
for i in range(H):
  ans = max(ans,max(dist[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
q = deque()
grid = [[10**6] * W for _ in range(H)]
dire = ((1,0),(0,1),(-1,0),(0,-1))
d = 0
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            q.append((i,j))
            grid[i][j] = 0
 
while q:
    i, j = q.popleft()
    d = grid[i][j]
    for dy, dx in dire:
        ny,nx = i+dy, j+dx
        if ny>=0 and ny<H and nx>=0 and nx<W and grid[ny][nx] > grid[i][j]:
            q.append((ny, nx))
            grid[ny][nx] = grid[i][j] + 1
 
print(d)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
a = [list(input()) for _ in range(H)]
q = deque()
inf_ = float("inf")
grid = [[inf_] * W for _ in range(H)]
dire = ((1,0),(0,1),(-1,0),(0,-1))
d = 0
 
for i in range(H):
    for j in range(W):
        if a[i][j] == "#":
            q.append([i,j])
            grid[i][j] = 0
 
while q:
    i, j = q.popleft()
    d = max(d,grid[i][j]) 
    for dy, dx in dire:
        ny,nx = i+dy, j+dx
        if ny>=0 and ny<H and nx>=0 and nx<W and grid[ny][nx] > grid[i][j]:
            q.append([ny, nx])
            grid[ny][nx] = grid[i][j] + 1
 
print(d)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
inf_ = float("inf")
grid = [[inf_] * W for _ in range(H)]
stack = []
dire = [(1,0),(0,1),(-1,0),(0,-1)]
ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            stack.append([i,j,0])
while stack:
    i, j, now = stack.pop()
    grid[i][j] = now
    for dy, dx in dire:
        ny,nx = i+dy, j+dx
        if ny>=0 and ny<H and nx>=0 and nx<W and grid[ny][nx] > now+1:
            stack.append([ny,nx,now+1])
for g in grid:
    ans = max(ans,max(g))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
A=[list(input()) for _ in range(H)]   # (i,j) = A[i][j]
seen = [[False] * W for _ in range(H)] 
queue=[]

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

while queue:
    i,j,k=queue.pop(0)
    if i!=0   and seen[i-1][j] == False: 
        queue.append((i-1,j,k+1))
        seen[i-1][j]=True
    if i!=H-1 and seen[i+1][j] == False:
        queue.append((i+1,j,k+1))
        seen[i+1][j]=True
    if j!=0   and seen[i][j-1] == False:
        queue.append((i,j-1,k+1))
        seen[i][j-1]=True
    if j!=W-1 and seen[i][j+1] == False:
        queue.append((i,j+1,k+1))
        seen[i][j+1]=True

print(k)

Submission status: Time Limit Exceeded

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

import copy

ans=0
while 1:
    if all('.' not in A[i] for i in range(H)):
        break
    else:
        ans+=1

    B=copy.deepcopy(A)
    for i in range(H):
        for j in range(W):
            if A[i][j]=='#':
                if i!=0   and A[i-1][j]=='.': B[i-1][j]='#'
                if i!=H-1 and A[i+1][j]=='.': B[i+1][j]='#'
                if j!=0   and A[i][j-1]=='.': B[i][j-1]='#'
                if j!=W-1 and A[i][j+1]=='.': B[i][j+1]='#'
                B[i][j]='X'

    A=copy.deepcopy(B)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs(maze, visited, l,n_w):
    queue = deque(l)
    for i in queue:
        visited[i[0]][i[1]] = 0
    while queue:
        y, x = queue.popleft()
        if n_w==0:
            s=set()
            tmp=0
            for i in visited:
                if max(i)>tmp:tmp=max(i)
            return(tmp)
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
                n_w-=1

R, C = map(int, input().split())


maze = ["$"*(C+2)]+["$"+input()+"$" for i in range(R)]+["$"*(C+2)]
visited = [[-2]*(C+2)]+[[-2]+[-1]*(C)+[-2] for j in range(R)]+[[-2]*(C+2)]
l_b=[]
for i in range(R+2):
    for j in range(C+2):
        if maze[i][j]=="#":
            l_b.append([i,j])
n_w=R*C-len(l_b)

print(bfs(maze, visited,l_b,n_w))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs(maze, visited, l,n_w):
    queue = deque(l)
    for i in queue:
        visited[i[0]][i[1]] = 0
    while queue:
        y, x = queue.popleft()
        if n_w==0:
            s=set()
            for i in visited:
                s=s|set(i)
            return(max(s))
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
                n_w-=1

R, C = map(int, input().split())


maze = ["$"*(C+2)]+["$"+input()+"$" for i in range(R)]+["$"*(C+2)]
visited = [[-2]*(C+2)]+[[-2]+[-1]*(C)+[-2] for j in range(R)]+[[-2]*(C+2)]
l_b=[]
for i in range(R+2):
    for j in range(C+2):
        if maze[i][j]=="#":
            l_b.append([i,j])
n_w=R*C-len(l_b)

print(bfs(maze, visited,l_b,n_w))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs(maze, visited, l):
    queue = deque(l)
    for i in queue:
        visited[i[0]][i[1]] = 0
    while queue:
        y, x = queue.popleft()
        if all ([-1 not in i for i in visited]):
            s=set()
            for i in visited:
                s=s|set(i)
            return(max(s))
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])

R, C = map(int, input().split())


maze = ["$"*(C+2)]+["$"+input()+"$" for i in range(R)]+["$"*(C+2)]
visited = [[-2]*(C+2)]+[[-2]+[-1]*(C)+[-2] for j in range(R)]+[[-2]*(C+2)]
l_b=[]
for i in range(R+2):
    for j in range(C+2):
        if maze[i][j]=="#":
            l_b.append([i,j])

print(bfs(maze, visited,l_b))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs(maze, visited, l):
    queue = deque(l)
    for i in queue:
        visited[i[0]][i[1]] = 0
    while queue:
        y, x = queue.popleft()
        if all ([-1 not in i for i in visited]):
            s=set()
            for i in visited:
                s.add(max(i))
            return(max(s))
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])

R, C = map(int, input().split())


maze = ["$"*(C+2)]+["$"+input()+"$" for i in range(R)]+["$"*(C+2)]
visited = [[-2]*(C+2)]+[[-2]+[-1]*(C)+[-2] for j in range(R)]+[[-2]*(C+2)]
l_b=[]
for i in range(R+2):
    for j in range(C+2):
        if maze[i][j]=="#":
            l_b.append([i,j])

print(bfs(maze, visited,l_b))

Submission status: Time Limit Exceeded

Solution code:
#  --*-coding:utf-8-*--

def main():
    H, W = map(int, input().split())
    X = [[0]*W for _ in range(H)]
    Q = [None]*(H*W)
    lenOfQ = 0
    Q2 = [None]*(H*W)
    lenOfQ2 = 0
    
    for i in range(H):
        line = input()

        for j, c in enumerate(line):
            if c == '#':
                X[i][j] = 1
                Q[lenOfQ] = i*W+j
                lenOfQ += 1

    t = 1

    while(lenOfQ > 0):
        lenOfQ2 = 0

        for i in range(lenOfQ):
            r, c  = Q[i]//W, Q[i]%W

            if r > 0 and X[r-1][c] == 0:
                X[r-1][c] = t+1
                Q2[lenOfQ2] = (r-1)*W + c
                lenOfQ2 += 1

            if r < H-1 and X[r+1][c] == 0:
                X[r+1][c] = t+1
                Q2[lenOfQ2] = (r+1)*W + c
                lenOfQ2 += 1

            if c > 0 and X[r][c-1] == 0:
                X[r][c-1] = t+1
                Q2[lenOfQ2] = r*W + c-1
                lenOfQ2 += 1

            if c < W-1 and X[r][c+1] == 0:
                X[r][c+1] = t+1
                Q2[lenOfQ2] = r*W + c+1
                lenOfQ2 += 1

        if lenOfQ2 == 0:
            break

        Q, Q2 = Q2, Q
        lenOfQ = lenOfQ2

        t += 1
                
    print(t-1)


 


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#  --*-coding:utf-8-*--

def main():
    H, W = map(int, input().split())
    X = [[0]*W for _ in range(H)]
    Q = [None]*(H*W)
    lenOfQ = 0
    Q2 = [None]*(H*W)
    lenOfQ2 = 0
    
    for i in range(H):
        line = input()

        for j, c in enumerate(line):
            if c == '#':
                X[i][j] = 1
                Q[lenOfQ] = (i, j)
                lenOfQ += 1

    t = 1

    while(lenOfQ > 0):
        lenOfQ2 = 0

        for i in range(lenOfQ):
            r, c  = Q[i]

            if r > 0 and X[r-1][c] == 0:
                X[r-1][c] = t+1
                Q2[lenOfQ2] = (r-1, c)
                lenOfQ2 += 1

            if r < H-1 and X[r+1][c] == 0:
                X[r+1][c] = t+1
                Q2[lenOfQ2] = (r+1, c)
                lenOfQ2 += 1

            if c > 0 and X[r][c-1] == 0:
                X[r][c-1] = t+1
                Q2[lenOfQ2] = (r, c-1)
                lenOfQ2 += 1

            if c < W-1 and X[r][c+1] == 0:
                X[r][c+1] = t+1
                Q2[lenOfQ2] = (r, c+1)
                lenOfQ2 += 1

        if lenOfQ2 == 0:
            break

        Q, Q2 = Q2, Q
        lenOfQ = lenOfQ2

        t += 1
                
    print(t-1)


 


if __name__ == '__main__':
    main()