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=[[None]*(W+2)]+\
  [[None] + [i=="." for i in input()] + [None] for _ in range(H)] + \
  [[None]*(W+2)]
 
cnt=0
q,r=[],[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j]==False:
            q.append((i,j))
if len(q)==H*W:
    print(0)
    import sys
    sys.exit()
for k in range(2000):
    for i,j in q:
        if A[i-1][j]:
            A[i-1][j]=False
            r.append((i-1,j))
        if A[i+1][j]:
            A[i+1][j]=False
            r.append((i+1,j))
        if A[i][j-1]:
            A[i][j-1]=False
            r.append((i,j-1))
        if A[i][j+1]:
            A[i][j+1]=False
            r.append((i,j+1))
    q=[i for i in r]
    r=[]
    if q==[]:
        break
    cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
A=[[True]*(W+2)]+\
  [[True] + [i=="#" for i in input()] + [True] for _ in range(H)] + \
  [[True]*(W+2)]
 
cnt=0
q,r=[],[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j]==True:
            q.append((i,j))
if len(q)==H*W:
    import sys
    print(0)
    sys.exit()
while(q):
    for i,j in q:
        if A[i-1][j]==False:
            A[i-1][j]=True
            r.append((i-1,j))
        if A[i+1][j]==False:
            A[i+1][j]=True
            r.append((i+1,j))
        if A[i][j-1]==False:
            A[i][j-1]=True
            r.append((i,j-1))
        if A[i][j+1]==False:
            A[i][j+1]=True
            r.append((i,j+1))
    q=[i for i in r]
    r=[]
    cnt+=1
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

def input():
  return sys.stdin.readline()

def pixel_input(H,W,border="."):
    pixel = [[border]*(W+2)] + \
    [[border] + list(input()) + [border] for _ in range(H)] + \
    [[border]*(W+2)]
    return pixel
  
H,W=map(int,input().split())
A=pixel_input(H,W)
 
cnt=0
q,r=[],[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j]=="#":
            q.append((i,j))
if len(q)==H*W:
    print(0)
    sys.exit()
while(q):
    while(q):
        i,j=q.pop()
        if A[i-1][j]==".":
            if i-1!=0:
                A[i-1][j]="#"
                r.append((i-1,j))
        if A[i+1][j]==".":
            if i+1!=H+1:
                A[i+1][j]="#"
                r.append((i+1,j))
        if A[i][j-1]==".":
            if j-1!=0:
                A[i][j-1]="#"
                r.append((i,j-1))
        if A[i][j+1]==".":
            if j+1!=W+1:
                A[i][j+1]="#"
                r.append((i,j+1))
    q=[i for i in r]
    r=[]
    cnt+=1
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
def pixel_input(H,W,border="."):
    pixel = [[border]*(W+2)] + \
    [[border] + list(input()) + [border] for _ in range(H)] + \
    [[border]*(W+2)]
    return pixel
  
H,W=map(int,input().split())
A=pixel_input(H,W)
 
cnt=0
q,r=[],[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j]=="#":
            q.append((i,j))
if len(q)==H*W:
    print(0)
    sys.exit()
while(q):
    while(q):
        i,j=q.pop()
        if A[i-1][j]==".":
            if i-1!=0:
                A[i-1][j]="#"
                r.append((i-1,j))
        if A[i+1][j]==".":
            if i+1!=H+1:
                A[i+1][j]="#"
                r.append((i+1,j))
        if A[i][j-1]==".":
            if j-1!=0:
                A[i][j-1]="#"
                r.append((i,j-1))
        if A[i][j+1]==".":
            if j+1!=W+1:
                A[i][j+1]="#"
                r.append((i,j+1))
    q=[i for i in r]
    r=[]
    cnt+=1
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
import copy

H,W = (int(i) for i in input().split())
A = []
for i in range(H):
    A.append(input())

changingA = copy.deepcopy(A)
numchange = 0


while A.count("#"*W) < H:
    numchange += 1
    for column in range(W):
        for row in range(H):
            if A[row][column] == "#":
                if row-1 >= 0:
                    changingA[row-1] = changingA[row-1][:column] + "#" + changingA[row-1][column+1:]
                if row+1 < H:
                    changingA[row+1] = changingA[row+1][:column] + "#" + changingA[row+1][column+1:]
                if column-1 >= 0:
                    changingA[row] = changingA[row][:column-1] + "#" + changingA[row][column+1-1:]
                if column+1 < W:
                    changingA[row] = changingA[row][:column+1] + "#" + changingA[row][column+1+1:]
    A = copy.deepcopy(changingA)

print(numchange)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
aa = []
was = []
for i in range(H):
    line = input()
    for j,c in enumerate(line):
        if c =="#":
            aa.append((i, j))
            was.append((i, j))

cost = 0
while len(was) != H*W:
    cost += 1
    nextaa = []
    for a in aa:
        if a[0] > 0:
            if not (a[0]-1, a[1]) in was:
                nextaa.append((a[0]-1, a[1]))
                was.append((a[0]-1, a[1]))
        if H-1 > a[0]:
            if not (a[0]+1, a[1]) in was:
                nextaa.append((a[0]+1, a[1]))
                was.append((a[0]+1, a[1]))
        if a[1] > 0:
            if not (a[0], a[1]-1) in was:
                nextaa.append((a[0], a[1]-1))
                was.append((a[0], a[1]-1))
        if W-1 > a[1]:
            if not (a[0], a[1]+1) in was:
                nextaa.append((a[0], a[1]+1))
                was.append((a[0], a[1]+1))
    aa = nextaa

print(cost)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect


def main():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]

    checked = [[False] * W for _ in range(H)]
    ans = -1

    while True:
        checked_count = 0
        for h in range(H):
            for w in range(W):
                if checked[h][w]:
                    checked_count += 1
        if checked_count == H * W:
            break

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

        ans += 1
        # print(ans)

        que = []
        for h in range(H):
            for w in range(W):
                if A[h][w] == '#' and not checked[h][w]:
                    que.append((h, w))
                    checked[h][w] = True

        while que:
            h, w = que.pop()
            dx4 = [0, 0, 1, -1]
            dy4 = [1, -1, 0, 0]

            for dx, dy in zip(dx4, dy4):
                next_h = h + dy
                next_w = w + dx
                if 0 <= next_h < H and 0 <= next_w < W and not checked[next_h][next_w]:
                    A[next_h][next_w] = '#'

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split(" "))
map=[]
count=0
countOfDot=0
map.append(["*"]*(w+2))
for i in range(h):
    line=list(input())
    line.insert(0,"*")
    line.append("*")
    countOfDot+=line.count(".")
    map.append(line)
map.append(["*"]*(w+2))
while countOfDot>0:
    setLst=[]
    for i in range(h+2):
        for j in range(w+2):
            if map[i][j] == ".":
                if (map[i-1][j] == "#"
                    or map[i+1][j] == "#"
                    or map[i][j+1] == "#"
                    or map[i][j-1] == "#"):
                    countOfDot-=1
                    setLst.append([i,j])
    for i in setLst:
        map[i[0]][i[1]]="#"
    count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

q = deque([])

for i in range(h):
    for j in range(w):
        if c[i][j] == '#':
            q.append([i, j])
            c[i][j] = 0

p = q.popleft()
max = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
while True:
    xx = p[0]
    yy = p[1]
    for i in range(4):
        x = xx + dx[i]
        y = yy + dy[i]
        if x < 0 or x > h - 1 or y < 0 or w - 1 < y:
            continue
        if c[x][y] == '.':
            q.append([x, y])
            count = c[xx][yy] + 1
            if max < count:
                max = count
            c[x][y] = count
    if len(q) == 0:
        break
    p = q.popleft()
print(max)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

whites = []
blacks = []

check_list = [[True for i in range(C+2)]]
for i in range(R):
    tmp = []
    check_list.append([True] + [s == '#' for s in input()] + [True])
    for n, c in enumerate(check_list[i+1][1:C+1]):
        if c:
            blacks.append((i+1, n+1))
check_list.append([True for i in range(C+2)])


result = -1
while blacks:
    new_blacks = []
    result += 1
    for x, y in blacks:
        if not check_list[x + 1][y]:
            check_list[x + 1][y] = True
            new_blacks.append([x + 1, y])

        if not check_list[x - 1][y]:
            check_list[x - 1][y] = True
            new_blacks.append([x - 1, y])

        if not check_list[x][y + 1]:
            check_list[x][y + 1] = True
            new_blacks.append([x, y + 1])

        if not check_list[x][y - 1]:
            check_list[x][y - 1] = True
            new_blacks.append([x, y - 1])
    blacks = new_blacks

print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

whites = []
blacks = []

check_list = [[True for i in range(C+2)]]
for i in range(R):
    tmp = []
    for n,s in enumerate(input()):
        tmp.append(s == '#')
        if s == '#':
            blacks.append([i+1, n+1])
    check_list.append([True]+tmp+[True])

check_list.append([True for i in range(C+2)])


result = -1
while blacks:
    new_blacks = []
    result += 1
    for element in blacks:
        x = element[0]
        y = element[1]
        if not check_list[x + 1][y]:
            check_list[x + 1][y] = True
            new_blacks.append([x + 1, y])

        if not check_list[x - 1][y]:
            check_list[x - 1][y] = True
            new_blacks.append([x - 1, y])

        if not check_list[x][y + 1]:
            check_list[x][y + 1] = True
            new_blacks.append([x, y + 1])

        if not check_list[x][y - 1]:
            check_list[x][y - 1] = True
            new_blacks.append([x, y - 1])
    blacks = new_blacks

print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

whites = []
blacks = []

check_list = [[True for i in range(C+2)]]
for i in range(R):
    tmp = []
    for n,s in enumerate(input()):
        tmp.append(s == '#')
        if s == '#':
            blacks.append([i+1, n+1])
    check_list.append([True]+tmp+[True])

check_list.append([True for i in range(C+2)])


result = -1
while not len(blacks) == 0:
    new_blacks = []
    result += 1
    for element in blacks:
        x = element[0]
        y = element[1]
        if not check_list[x + 1][y]:
            check_list[x + 1][y] = True
            new_blacks.append([x + 1, y])

        if not check_list[x - 1][y]:
            check_list[x - 1][y] = True
            new_blacks.append([x - 1, y])

        if not check_list[x][y + 1]:
            check_list[x][y + 1] = True
            new_blacks.append([x, y + 1])

        if not check_list[x][y - 1]:
            check_list[x][y - 1] = True
            new_blacks.append([x, y - 1])
    blacks = new_blacks

print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

whites = []
blacks = []

for i in range(R):
    st = input()
    for n, c in enumerate(st):
        coordinates = (i, n)
        if c == '.':
            whites.append(coordinates)
        else:
            blacks.append(coordinates)

result = 0
while whites:
    # print(result)
    new_blacks = []
    result += 1
    for element in blacks:
        x = element[0]
        y = element[1]

        if (x-1, y) in whites:
            whites.remove((x-1, y))
            new_blacks.append((x-1, y))
        if (x+1, y) in whites:
            whites.remove((x+1, y))
            new_blacks.append((x+1, y))
        if (x, y-1) in whites:
            whites.remove((x, y-1))
            new_blacks.append((x, y-1))
        if (x, y+1) in whites:
            whites.remove((x, y+1))
            new_blacks.append((x, y+1))
        
    blacks = new_blacks

print(result)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from functools import reduce

h, w = map(int, input().split())
a = []
b = set([])

for i in range(h):
    a.append(list(input()))
    for j in range(w):
        if (a[i][j] == '#'):
            b.add((i, j))


def addBlack(bl, t):
    bl.add(t)
    if t[0] - 1 >= 0:
        bl.add((t[0] - 1, t[1]))
    if t[0] + 1 < w:
        bl.add((t[0] + 1, t[1]))
    if t[1] - 1 >= 0:
        bl.add((t[0], t[1] - 1))
    if t[1] + 1 < h:
        bl.add((t[0], t[1] + 1))
    return bl


count = 0
while(len(b) < h * w):
    count += 1
    b = reduce(addBlack, b, set([]))

print(count)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
 
import copy
 
H, W = map(int, input().split())
rest = H * W
lst = [[0 for i in range(W)] for j in range(H)]
answer = 0
 
black_mass = set()
new_black_mass = set()
 
for h in range(H):
    line=input()
    for w in range(W):
        if line[w] == '#':
            rest -= 1
            lst[h][w] = 1
            black_mass.add((h,w))
 
while(rest > 0):
    for xy in black_mass:
        if xy[0] > 0:
            if lst[xy[0]-1][xy[1]] == 0:
                lst[xy[0]-1][xy[1]] = 1
                new_black_mass.add((xy[0]-1, xy[1]))
                rest -= 1
        if xy[0] < H - 1:
            if lst[xy[0]+1][xy[1]] == 0:
                lst[xy[0]+1][xy[1]] = 1
                new_black_mass.add((xy[0]+1, xy[1]))
                rest -= 1
        if xy[1] > 0:
            if lst[xy[0]][xy[1]-1] == 0:
                lst[xy[0]][xy[1]-1] = 1
                new_black_mass.add((xy[0], xy[1]-1))
                rest -= 1
        if xy[1] < W - 1:
            if lst[xy[0]][xy[1]+1] == 0:
                lst[xy[0]][xy[1]+1] = 1
                new_black_mass.add((xy[0], xy[1]+1))
                rest -= 1
    black_mass.clear()
    black_mass = copy.copy(new_black_mass)
    answer += 1
 
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int,input().split())
A = [list(input()) for _ in range(H)]
p = deque()
for i, Ai in enumerate(A):
    for j, Aij in enumerate(Ai):
        if Aij == "#":
            p.append([i, j, 0])

while p:
    y, x, cnt = p.popleft()
    for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        if 0 <= y + dy < H and 0 <= x + dx < W and A[y + dy][x + dx] == ".":
            p.append([y + dy, x + dx, cnt + 1])
            A[y + dy][x + dx] = "#"
print(cnt)

Submission status: Time Limit Exceeded

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

import copy

H, W = map(int, input().split())
rest = H * W
lst = [[0 for i in range(W)] for j in range(H)]
answer = 0

black_mass = set()
new_black_mass = set()

for h in range(H):
    line=input()
    for w in range(W):
        if line[w] == '#':
            rest -= 1
            lst[h][w] = 1
            black_mass.add((h,w))

while(rest > 0):
    for xy in black_mass:
        if xy[0] > 0:
            if lst[xy[0]-1][xy[1]] == 0:
                lst[xy[0]-1][xy[1]] = 1
                new_black_mass.add((xy[0]-1, xy[1]))
                rest -= 1
        if xy[0] < H - 1:
            if lst[xy[0]+1][xy[1]] == 0:
                lst[xy[0]+1][xy[1]] = 1
                new_black_mass.add((xy[0]+1, xy[1]))
                rest -= 1
        if xy[1] > 0:
            if lst[xy[0]][xy[1]-1] == 0:
                lst[xy[0]][xy[1]-1] = 1
                new_black_mass.add((xy[0], xy[1]-1))
                rest -= 1
        if xy[1] < W - 1:
            if lst[xy[0]][xy[1]+1] == 0:
                lst[xy[0]][xy[1]+1] = 1
                new_black_mass.add((xy[0], xy[1]+1))
                rest -= 1
    black_mass.clear()
    black_mass = copy.deepcopy(new_black_mass)
    answer += 1

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int,input().split())
A = []
X = deque(); Y = deque()
for l in range(H):
    a = list(input())
    addX = [n for n, i in enumerate(a) if i == "#"]
    X.extend(addX); Y.extend([l] * len(addX))
    A.append(a)

cntList = deque()
cntList.extend([0] * len(X))

while X and Y:
    x = X.popleft(); y = Y.popleft(); cnt = cntList.popleft()
    for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        if 0 <= y + dy < H and 0 <= x + dx < W and A[y + dy][x + dx] == ".":
            X.append(x + dx); Y.append(y + dy); cntList.append(cnt + 1)
            A[y + dy][x + dx] = "#"
print(cnt)

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy


def getDistance(indx,blcks):
    minDist = 1001
    for set in blcks:
        tmp = abs(numpy.subtract(indx,set))
        dist = tmp[0]+tmp[1]
        if dist < minDist:
            minDist = dist
    return minDist


R, C = list(map(int,input().split()))
lst = []
for i in range(R):
    st = input()
    tmp = []
    for c in st:
        tmp.append(c)
    lst.append(tmp)

# get dark positions
darks = []
for i in range(len(lst)):
    for j in range(len(lst[0])):
        if lst[i][j] == '#':
            darks.append((i, j))

currentDist = 0

for i in range(len(lst)):
    found = (0, -1)
    for j in range(len(lst[0])):
        if lst[i][j] == '.':
            if found[0] == 0 or j-found[1] > currentDist:
                dist = getDistance((i, j), darks)
                if dist > currentDist:
                    currentDist = dist
        else:
            found = (1, j)

print(currentDist)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy

def getDistance(indx,blcks):
    minDist = 1001
    for set in blcks:
        tmp = abs(numpy.subtract(indx,set))
        dist = tmp[0]+tmp[1]
        if dist < minDist:
            minDist = dist
    return minDist


R,C = list(map(int,input().split()))
lst = []
for i in range(R):
    st = input()
    tmp = []
    for c in st:
        tmp.append(c)
    lst.append(tmp)

# print(lst)
# R = 6
# C = 6
#
# # lst = [['.','.','.'],['.','#','.'],['.','.','.']]
# lst = [['.','.','#','.','.','#'],['.','.','.','.','.','.'],['#','.','.','#','.','.'],['.','.','.','.','.','.'],['.','#','.','.','.','.'],['.','.','.','.','#','.']]



# get dark positions
darks = []
for i in range(len(lst)):
    for j in range(len(lst[0])):
        if lst[i][j] == '#':
            darks.append((i,j))

currentDist = 0

for i in range(len(lst)):
    for j in range(len(lst[0])):
        if lst[i][j] == '.':
            dist = getDistance((i,j),darks)
            if dist > currentDist:
                currentDist = dist

print(currentDist)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W = [int(i) for i in input().split()]
l = [list(input()) for _ in range(H)]
ans = [[-1]*W for _ in range(H)]
q = deque()

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

t = 0
while q:
    i,j = q.popleft()
    for next_i, next_j in [[i+1,j], [i-1,j], [i,j+1], [i,j-1]]:
        if 0 <= next_i < H and 0 <= next_j < W:
            if ans[next_i][next_j] == -1 and l[next_i][next_j] == '.':
                ans[next_i][next_j] = ans[i][j] + 1
                t = max(t, ans[next_i][next_j])
                q.append([next_i,next_j])

print(t)

Submission status: Time Limit Exceeded

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

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

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

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

    new_blacks = set()
    for b in blacks:
        top = b[0] - 1
        bottom = b[0] + 1
        left = b[1] - 1
        right = b[1] + 1

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

    blacks = new_blacks

print(c - 1)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

    blacks = new_blacks

print(c - 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

H,W = [int(i) for i in input().split()]
l = [list(input()) for _ in range(H)]
check = [[False]*W for _ in range(H)]
ans = [[0]*W for _ in range(H)]
q = deque()

for i in range(H):
    for j in range(W):
        if l[i][j] == '#':
            q.append([i,j])

while q:
    i,j = q.popleft()
    for next_i, next_j in [[i+1,j], [i-1,j], [i,j+1], [i,j-1]]:
        if 0 <= next_i < H and 0 <= next_j < W:
            if not check[next_i][next_j] and l[next_i][next_j] == '.':
                check[next_i][next_j] = True
                ans[next_i][next_j] = ans[i][j] + 1
                q.append([next_i,next_j])

a = 0
for i in range(H):
    for j in range(W):
        a = max(ans[i][j], a)
print(a)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

    blacks = new_blacks


print(c-1)

Submission status: Time Limit Exceeded

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

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

    for idx, r in enumerate(row):
        if r == ".":
            whites.append([i,idx])

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

    next_whites = []
    delete_whites = []
    while len(whites) > 0:
        w = whites.pop()

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

        flag = False
        if top >= 0:
            if grid[top][w[1]] == "#":
                flag = True
        if bottom < H:
            if grid[bottom][w[1]] == "#":
                flag = True
        if left >= 0:
            if grid[w[0]][left] == "#":
                flag = True
        if right < W:
            if grid[w[0]][right] == "#":
                flag = True

        if not flag:
            next_whites.append(w)
        else:
            delete_whites.append(w)

    for w in delete_whites:
        grid[w[0]][w[1]] = "#"

    whites = next_whites

print(c)

Submission status: Time Limit Exceeded

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

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

    for idx, r in enumerate(row):
        if r == ".":
            whites.append([i,idx])

c = 0
next_state = copy.deepcopy(grid)
while len(whites) > 0:
    c += 1

    next_whites = []
    while len(whites) > 0:
        w = whites.pop()

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

        flag = False
        if top >= 0:
            if grid[top][w[1]] == "#":
                next_state[w[0]][w[1]] = "#"
                flag = True
        if bottom < H:
            if grid[bottom][w[1]] == "#":
                next_state[w[0]][w[1]] = "#"
                flag = True
        if left >= 0:
            if grid[w[0]][left] == "#":
                next_state[w[0]][w[1]] = "#"
                flag = True
        if right < W:
            if grid[w[0]][right] == "#":
                next_state[w[0]][w[1]] = "#"
                flag = True

        if not flag:
            next_whites.append(w)

    whites = next_whites.copy()
    grid = copy.deepcopy(next_state)

print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W = map(int,input().split(" "))
A = [0]*H
E = [[0]*W for x in range(H)]
d = deque()
K = 0
for i in range(H):
    A[i] = list(input())

for x in range(H):
    for y in range(W):
        if A[x][y] == '#':
            A[x][y] = 0
            E[x][y] = 1
            d.append([x,y])
            K += 1

KK = H * W
while K < KK:
    xx,yy = d.popleft()
    for x,y in [[xx + 1,yy],[xx - 1,yy],[xx,yy + 1],[xx,yy - 1]]:
        if 0 <= x < H and 0 <= y < W and not(E[x][y]):
            A[x][y] = A[xx][yy] + 1
            E[x][y] = 1
            d.append([x,y])
            K += 1

print(max(map(max,A)))