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:
#darker　and darker
from collections import deque
d=deque()
e=deque()
h,w=map(int,input().split())
field=[0 for i in range(h+2)]
field[0]=[True for i in range(w+2)]
distance=0
for i in range(h):
    s=input()
    a=[False for i in range(w+2)]
    a[0]=True
    for j in range(w):
        if s[j]=="#":
            a[j+1]=True
            d.append((i+1,j+1))
    a[w+1]=True
    field[i+1]=a
field[h+1]=[True for i in range(w+2)]
while d:
    while d:
        some=d.popleft()
        index1,index2=some[0],some[1]
        if field[index1-1][index2]==False:
                field[index1-1][index2]=True
                e.append((index1-1,index2))
        if field[index1+1][index2]==False:
                field[index1+1][index2]=True
                e.append((index1+1,index2))
        if field[index1][index2+1]==False:
                field[index1][index2+1]=True
                e.append((index1,index2+1))
        if  field[index1][index2-1]==False:
                field[index1][index2-1]=True
                e.append((index1,index2-1))
    distance+=1
    d=e
    e=deque()
print(distance-1)

Submission status: Time Limit Exceeded

Solution code:
#darker　and darker
from collections import deque
d=deque()
e=deque()
h,w=map(int,input().split())
field=[0 for i in range(h+2)]
field[0]=[True for i in range(w+2)]
#visited_node=0
distance=0
for i in range(h):
    s=input()
    a=[]
    a.append(True)
    for j in range(w):
        if s[j]=="#":
            a.append(True)
            d.append((i+1,j+1))
        else:
            a.append(False)
    a.append(True)
    field[i+1]=a
field[h+1]=[True for i in range(w+2)]
while d:
    while d:
        some=d.popleft()
        index1,index2=some[0],some[1]
        if field[index1-1][index2]==False:
                field[index1-1][index2]=True
                e.append((index1-1,index2))
        if field[index1+1][index2]==False:
                field[index1+1][index2]=True
                e.append((index1+1,index2))
        if field[index1][index2+1]==False:
                field[index1][index2+1]=True
                e.append((index1,index2+1))
        if  field[index1][index2-1]==False:
                field[index1][index2-1]=True
                e.append((index1,index2-1))
    distance+=1
    d=e
    e=deque()
print(distance-1)

Submission status: Time Limit Exceeded

Solution code:
#darker　and darker
from collections import deque
d=deque()
e=deque()
h,w=map(int,input().split())
field=[]
field.append([True for i in range(w+2)])
#visited_node=0
distance=0
for i in range(h):
    s=input()
    a=[]
    a.append(True)
    for j in range(w):
        if s[j]=="#":
            a.append(True)
            d.append((i+1,j+1))
        else:
            a.append(False)
    a.append(True)
    field.append(a)
field.append([True for i in range(w+2)])
while d:
    for some in d:
        index1,index2=some[0],some[1]
        if field[index1-1][index2]==False:
            field[index1-1][index2]=True
            e.append((index1-1,index2))
        if field[index1+1][index2]==False:
            field[index1+1][index2]=True
            e.append((index1+1,index2))
        if field[index1][index2+1]==False:
            field[index1][index2+1]=True
            e.append((index1,index2+1))
        if  field[index1][index2-1]==False:
            field[index1][index2-1]=True
            e.append((index1,index2-1))
    distance+=1
    d=e
    e=deque()
print(distance-1)

Submission status: Time Limit Exceeded

Solution code:
def main():

    h, w = map(int, input().split())
    area = []
    blacks = []
    blacks
    b_append = blacks.append

    for i in range(h):
        array = input()
        for j in range(len(array)):
            if array[j] == '#':
                b_append((i, j))
        area.append(array)


    def check(i, j):
        min_dist = 10000
        for l, m in blacks:
            dist = abs(i - l) + abs(j - m)
            if dist < min_dist:
                min_dist = dist
        return min_dist


    max_dist = 0

    for i in range(h):
        for j in range(w):
            dist = 0
            if area[i][j] != '#':
                dist = check(i, j)
            if dist > max_dist:
                max_dist = dist

    print(max_dist)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

todo = deque([])
draw = ((1, 0), (-1, 0), (0, 1), (0, -1))
done = [[0] * (w + 2)]
for i in range(h):
    done.append([0] + [1000 for _ in range(w)] + [0])
done.append([0] * (w + 2))

grid = [list("#" * (w + 2))]
for i in range(h):
    s = input()
    for j, k in enumerate(s):
        if k == "#":
            todo.append((i + 1, j + 1))
            done[i + 1][j + 1] = 0
    grid.append(list("#" + s + "#"))
grid.append(list("#" * (w + 2)))

while todo:
    n, m = todo.popleft()
    d = done[n][m]
    for dn, dm in draw:
        if done[n + dn][m + dm] != 1000:
            pass
        elif done[n + dn][m + dm] > d + 1:
            todo.append((n + dn, m + dm))
            done[n + dn][m + dm] = d + 1

print(max(max(i) for i in done))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

move = (-w, -1, 1, w)
todo = deque([])
done = [1000 for _ in range(w * h)]
for i, j in enumerate(grid):
    for k, l in enumerate(j):
        if l == "#":
            todo.append(k + i * w)
            done[k + i * w] = 0

while todo:
    n = todo.popleft()
    d = done[n]
    for dn in move:
        if n % w == 0 and dn == -1:
            pass
        elif n % w == w - 1 and dn == 1:
            pass
        elif n < w and dn == -w:
            pass
        elif n >= w * h - w and dn == w:
            pass
        elif done[n + dn] <= d + 1:
            pass
        else:
            todo.append(n + dn)
            done[n + dn] = d + 1

print(max(done))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

move = (-w, -1, 1, w)
todo = deque([])
done = [1000 for _ in range(w * h)]
for i in range(h):
    s = input()
    for j, k in enumerate(s):
        if k == "#":
            todo.append(j + i * w)
            done[j + i * w] = 0

while todo:
    n = todo.popleft()
    d = done[n]
    for dn in move:
        if n % w == 0 and dn == -1:
            pass
        elif n % w == w - 1 and dn == 1:
            pass
        elif n < w and dn == -w:
            pass
        elif n >= w * h - w and dn == w:
            pass
        elif done[n + dn] <= d + 1:
            pass
        else:
            todo.append(n + dn)
            done[n + dn] = d + 1

print(max(done))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

move = (-w, -1, 1, w)
todo = deque([])
done = [False for _ in range(w * h)]
grid = ""
for i in range(h):
    s = input()
    for j, k in enumerate(s):
        if k == "#":
            todo.append(j + i * w)
            done[j + i * w] = True
    grid += s
grid = list(grid)

cnt = -1
while todo:
    for i in range(len(todo)):
        n = todo.popleft()
        for dn in move:
            if n % w == 0 and dn == -1:
                pass
            elif n % w == w - 1 and dn == 1:
                pass
            elif n < w and dn == -w:
                pass
            elif n >= w * h - w and dn == w:
                pass
            elif done[n + dn]:
                pass
            elif grid[n + dn] == "#":
                pass
            elif grid[n + dn] == ".":
                todo.append(n + dn)
                done[n + dn] = True
                grid[n + dn] = "#"
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

todo = deque([])
draw = ((1, 0), (-1, 0), (0, 1), (0, -1))
done = [[1] * (w + 2)]
for i in range(h):
    done.append([1] + [0 for _ in range(w)] + [1])
done.append([1] * (w + 2))

grid = [list("#" * (w + 2))]
for i in range(h):
    s = input()
    for j, k in enumerate(s):
        if k == "#":
            todo.append((i + 1, j + 1))
            done[i + 1][j + 1] = 1
    grid.append(list("#" + s + "#"))
grid.append(list("#" * (w + 2)))

cnt = 0
while todo:
    tmp = deque([])
    while todo:
        n, m = todo.popleft()
        for dn, dm in draw:
            if done[n + dn][m + dm] != 0:
                pass
            elif grid[n + dn][m + dm] == "#":
                pass
            elif grid[n + dn][m + dm] == ".":
                tmp.append((n + dn, m + dm))
                done[n + dn][m + dm] = 1
                grid[n + dn][m + dm] = "#"
    todo = tmp
    cnt += 1

print(cnt - 1)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())

todo = []
draw = ((1, 0), (-1, 0), (0, 1), (0, -1))
done = [[1] * (w + 2)]
for i in range(h):
    done.append([1] + [0 for _ in range(w)] + [1])
done.append([1] * (w + 2))

grid = [list("#" * (w + 2))]
for i in range(h):
    s = input()
    for j, k in enumerate(s):
        if k == "#":
            todo.append((i + 1, j + 1))
            done[i + 1][j + 1] = 1
    grid.append(list("#" + s + "#"))
grid.append(list("#" * (w + 2)))

cnt = 0
while todo:
    tmp = []
    while todo:
        n, m = todo.pop(0)
        for dn, dm in draw:
            if done[n + dn][m + dm] != 0:
                pass
            elif grid[n + dn][m + dm] == "#":
                pass
            elif grid[n + dn][m + dm] == ".":
                tmp.append((n + dn, m + dm))
                done[n + dn][m + dm] = 1
                grid[n + dn][m + dm] = "#"
    todo = tmp
    cnt += 1

print(cnt - 1)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
a = list(list(input())for i in range(h))
stack = []
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            stack.append((i,j))
        
vec = ((1,0),(0,1),(-1,0),(0,-1))
move = 0
while stack:
    next = []
    move +=1
    for y,x in stack:
        for ny,nx in vec:
            ty,tx = y+ny,x+nx
            if ty>h-1 or tx>w-1 or ty<0 or tx <0:continue
            if a[ty][tx] == ".":
                a[ty][tx] = move
                next.append((ty,tx))
    stack = next

print(move-1)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
a = list(list(input())for i in range(h))
stack = []
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            stack.append((i,j))
            a[i][j] == -1
vec = ((1,0),(0,1),(-1,0),(0,-1))
move = 0
while stack:
    next = []
    move +=1
    for y,x in stack:
        for ny,nx in vec:
            ty,tx = y+ny,x+nx
            if ty>h-1 or tx>w-1 or ty<0 or tx <0:continue
            if a[ty][tx] == ".":
                a[ty][tx] = move
                next.append((ty,tx))
    stack = next

print(move-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import copy

r, c = map(int, input().split())
map_ = [[c == "#" for c in input().strip()] for _ in range(r)]

queue = deque([(i, j) for j in range(c) for i in range(r) if map_[i][j]])

def bfs(maze, queue):
    depth = 0
    while True:
        depth += 1
        nextqueue = deque()
        while queue:
            posr, posc = queue.popleft()
            for dr, dc in zip([1, -1, 0, 0], [0, 0, 1, -1]):
                nextr = posr + dr
                nextc = posc + dc
                if 0 <= nextr < r and 0 <= nextc < c and not maze[nextr][nextc]:
                    maze[nextr][nextc] = True
                    nextqueue.append((nextr, nextc))
        if nextqueue:
            queue = copy(nextqueue)
        else:
            return depth - 1


print(bfs(map_, queue))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    
    h, w = map(int, input().split())
    a = [list(input()) for i in range(h)]
    queue = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                queue.append([i, j])

    visited = [[-1 for i in range(w)] for j in range(h)]
    ans = 0
    nqueue = []
    while queue:
        x, y = queue.pop(0)
        visited[x][y] = 1
        for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            nx = x + i
            ny = y + j
            if nx >= 0 and ny >= 0 and nx < h and ny < w:
                if visited[nx][ny] == -1 and a[nx][ny] != "#":
                    nqueue.append([nx, ny])
                    visited[nx][ny] = 1
                    a[nx][ny] = "#"
        
        if len(queue) == 0:
            queue = nqueue
            nqueue = []
            ans += 1
        
    print(ans-1)


        
                





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import product
h, w = [int(i) for i in sys.stdin.readline().split()]
A = {i : [] for i in range(h)}
que = []
already = set()
for y in range(h):
    inp = [i for i in sys.stdin.readline()]
    A[y] = inp
    for x, _i in enumerate(inp):
        if _i == "#":
            que.append((0, x, y))
            already.add((x, y))

worst = 0
while len(que) > 0:
    cur_cost, x, y = que.pop(0)
    worst = max(cur_cost, worst)
    for _x, _y in [(0,1),(0,-1), (1,0), (-1,0)]:
        next_x = x + _x
        next_y = y + _y
        if (next_x, next_y) in already:
            continue
        if 0 <= next_x < w and 0 <= next_y < h:
            que.append((cur_cost + 1, next_x, next_y))
            already.add((next_x, next_y))
print(worst)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


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

INF = 10 ** 5
d = [[10 ** 5] * W for _ in range(H)]

q = deque()

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

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

ans = 0
while q:
    y, x = q.popleft()

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

        if (0 <= ny < H and 0 <= nx < W and
            A[ny][nx] != '#' and d[ny][nx] == INF):

            d[ny][nx] = d[y][x] + 1
            q.append((ny, nx))
            ans = max(ans, d[ny][nx])

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)]

INF = 10 ** 5
d = [[10 ** 5] * W for _ in range(H)]

q = deque()

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

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

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

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

        if (0 <= ny < H and 0 <= nx < W and
            A[ny][nx] != '#' and d[ny][nx] == INF):

            d[ny][nx] = d[y][x] + 1
            q.append((ny, nx))

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

h, w = map(int, readline().split())
grid = [[0]*(w) for _ in range(h)]

black = []
for i in range(h):
    for j, k in enumerate(readline()):
        if k == "#":
            black.append((i, j))
            grid[i][j] = 1

ans = 0
d = ((0, 1),
     (1, 0),
     (0, -1),
     (-1, 0),)
while True:
    paint = []
    while black:
        x, y = black.pop()
        for nx, ny in d:
            if x+nx == -1 or x+nx == h or y+ny == -1 or y+ny == w:
                continue
            if not grid[nx + x][ny + y]:
                grid[nx + x][ny + y] = 1
                paint.append((nx + x, ny + y))

    if len(paint) == 0:
        break
    black = paint[:]
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
grid = [[0]*(w) for _ in range(h)]

black = []
for i in range(h):
    for j, k in enumerate(input()):
        if k == "#":
            black.append((i, j))
            grid[i][j] = 1

ans = 0
d = ((0, 1),
     (1, 0),
     (0, -1),
     (-1, 0),)
while True:
    paint = []
    while black:
        x, y = black.pop()
        for nx, ny in d:
            if x+nx == -1 or x+nx == h or y+ny == -1 or y+ny == w:
                continue
            if not grid[nx + x][ny + y]:
                grid[nx + x][ny + y] = 1
                paint.append((nx + x, ny + y))

    if len(paint) == 0:
        break
    black = paint[:]
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
grid = [[0]*(w+2) for _ in range(h+2)]

black = []
for i in range(h):
    for j, k in enumerate(input()):
        if k == "#":
            black.append((i + 1, j + 1))
            grid[i+1][j+1] = 1

ans = 0
d = ((0, 1),
     (1, 0),
     (0, -1),
     (-1, 0),)
while True:
    paint = []
    while black:
        x, y = black.pop()
        if x == 0 or x == h + 1 or y == 0 or y == w + 1:
            continue
        else:
            for nx, ny in d:
                if not grid[nx + x][ny + y]:
                    if x+nx == 0 or x+nx == h + 1 or y+ny == 0 or y+ny == w + 1:
                        continue
                    grid[nx + x][ny + y] = 1
                    paint.append((nx + x, ny + y))

    if len(paint) == 0:
        break
    black = paint[:]
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h, w = map(int, input().split())
grid = np.zeros((h + 2, w + 2), dtype=int)

black = []
for i in range(h):
    for j, k in enumerate(input()):
        if k == "#":
            black.append((i + 1, j + 1))
            grid[i+1][j+1] = True

ans = 0
d = ((0, 1),
     (1, 0),
     (0, -1),
     (-1, 0),)
while not grid[1: h + 1, 1: w + 1].all():
    paint = []
    while black:
        x, y = black.pop()
        if x == 0 or x == h + 1 or y == 0 or y == w + 1:
            continue
        else:
            for nx, ny in d:
                if not grid[nx + x][ny + y]:
                    grid[nx + x][ny + y] = 1
                    paint.append((nx + x, ny + y))

    black = paint[:]
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
dp = [[-1]*W for i in range(H)]

q = collections.deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            dp[i][j] = 0
            q.append([i, j])


while(q):
    x, y = q.popleft()
    if x > 0:
        if dp[x-1][y] == -1:
            dp[x-1][y] = dp[x][y]+1
            q.append([x-1, y])
    if x < H-1:
        if dp[x+1][y] == -1:
            dp[x+1][y] = dp[x][y]+1
            q.append([x+1, y])
    if y > 0:
        if dp[x][y-1] == -1:
            dp[x][y-1] = dp[x][y]+1
            q.append([x, y-1])
    if y < W-1:
        if dp[x][y+1] == -1:
            dp[x][y+1] = dp[x][y]+1
            q.append([x, y+1])
ans = 0
for i in range(H):
    ans = max(ans, max(dp[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
dp = [[H+W]*W for i in range(H)]

q = collections.deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            dp[i][j] = 0
            q.append([i, j])


while(q):
    x, y = q.popleft()
    if x > 0:
        if dp[x-1][y] > dp[x][y]+1:
            if A[x-1][y] == ".":
                dp[x-1][y] = dp[x][y]+1
            else:
                dp[x-1][y] = 0
            q.append([x-1, y])
    if x < H-1:
        if dp[x+1][y] > dp[x][y]+1:
            if A[x+1][y] == ".":
                dp[x+1][y] = dp[x][y]+1
            else:
                dp[x+1][y] = 0
            q.append([x+1, y])
    if y > 0:
        if dp[x][y-1] > dp[x][y]+1:
            if A[x][y-1] == ".":
                dp[x][y-1] = dp[x][y]+1
            else:
                dp[x][y-1] = 0
            q.append([x, y-1])
    if y < W-1:
        if dp[x][y+1] > dp[x][y]+1:
            if A[x][y+1] == ".":
                dp[x][y+1] = dp[x][y]+1
            else:
                dp[x][y+1] = 0
            q.append([x, y+1])
ans = 0
for i in range(H):
    ans = max(ans, max(dp[i]))
print(ans)

Submission status: Time Limit Exceeded

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

stack = []
for i in range(h):
    for j in range(w):
        if A[i][j] == "#":
            stack.append([i,j])

move = [[0,1],[1,0],[-1,0],[0,-1]]
cnt = 0
while stack:
    cur_stack = stack
    stack = []
    for si,sj in cur_stack:
        for mi,mj in move:
            i,j = si+mi,sj+mj
            if 0 > i or 0 > j or i >= h or j >= w:
                continue
            next_mass = A[i][j]
            if next_mass == ".":
                A[i][j] = "#"
                stack.append([i,j])
    cnt += 1
    # [print(c) for c in A]
    # print()
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    h,w=map(int,input().split())
    maze=[list(input()) for i in range(h)]
    d=[[float("inf")]*w for i in range(h)]
    que=deque([])
    dd=((1,0),(0,1),(-1,0),(0,-1))
    for i in range(h):
        for j in range(w):
            if maze[i][j]=="#":
                que.append((i,j))           
                d[i][j]=0
    ans=0
    while que:
        p=que.popleft()
        ans=d[p[0]][p[1]]
        for dx,dy in dd:
            nx=p[0]+dx
            ny=p[1]+dy
            if 0<=nx and nx<h and 0<=ny and ny<w and maze[nx][ny]!="#" and d[nx][ny]==float("inf"):
                d[nx][ny]=ans+1
                que.append((nx,ny))  
    return ans
if __name__=='__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    h,w=map(int,input().split())
    maze=[list(input()) for i in range(h)]
    d=[[float("inf")]*w for i in range(h)]
    que=deque([])
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    for i in range(h):
        for j in range(w):
            if maze[i][j]=="#":
                que.append((i,j))           
                d[i][j]=0
    ans=0
    while que:
        p=que.popleft()
        ans=d[p[0]][p[1]]
        for i in range(4):
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]
            if 0<=nx and nx<h and 0<=ny and ny<w and maze[nx][ny]!="#" and d[nx][ny]==float("inf"):
                d[nx][ny]=ans+1
                que.append((nx,ny))  
    return ans
if __name__=='__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

# メモ配列
INF = 10**7
# memo = [[INF]*w for i in range(h)]

# 探索用ベクトル
vx = (0, -1, 0, 1)
vy = (-1, 0, 1, 0)

# 幅探索用キューの準備
# 白マスをカウント
q = deque()
bcnt = 0
for i, vi in enumerate(p):
    for j, vj in enumerate(vi):
        if vj == '#':
            q.appendleft((j, i))
            bcnt+=1
            
qans = deque()
            
def bfs(q):
    for i in range(INF):
        # キューが空なら終了
        if len(q) == 0:
            return qans

        # キューから一つ取り出す
        x, y = map(int, q.pop())
#         print('xy', x, y)

        # 4方向のいずれかに白があれば、黒にする
        for j in range(4):
            nx, ny = x+vx[j], y+vy[j]

            # エリア外 or 黒色なら探索しない
            if nx < 0 or w <= nx or ny < 0 or h <= ny or p[ny][nx] == '#':
                continue

            p[ny][nx] = '#'
            qans.appendleft((nx, ny))

def printmap(a):
    for i in a:
        print(i)
        
# print(q)
# printmap(p)
for i in range(INF):
    qans = deque()
    q = bfs(q)
#     print(q)
#     printmap(p)
    # キューが空なら終了
    if len(q) == 0:
        ans = i
        break
    
print(ans)
# print(q)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
grid=[None]*h
INF=10**6
from collections import deque
stack=deque()
for i in range(h):
  s=list(input())
  for j in range(len(s)):
    if s[j]=="#":
      stack.append([i,j,0])
    s[j]=INF
  grid[i]=s
      
while stack:
  v=stack.popleft()
  y=v[0]
  x=v[1]
  p=v[2]
  grid[y][x]=p
  if y-1>=0 and p+1<grid[y-1][x]:
    stack.append([y-1,x,p+1])
  if y+1<h and p+1<grid[y+1][x]:
    stack.append([y+1,x,p+1])
  if x-1>=0 and p+1<grid[y][x-1]:
    stack.append([y,x-1,p+1])
  if x+1<w and p+1<grid[y][x+1]:
    stack.append([y,x+1,p+1])
    
ans=0
for i in range(len(grid)):
  ans=max(ans,max(grid[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
grid=[None]*h
INF=10**6
stack=[]
for i in range(h):
  s=list(input())
  for j in range(len(s)):
    if s[j]=="#":
      stack.append([i,j,0])
    s[j]=INF
  grid[i]=s
      
while stack:
  v=stack.pop()
  y=v[0]
  x=v[1]
  p=v[2]
  grid[y][x]=p
  if y-1>=0 and p+1<grid[y-1][x]:
    stack.append([y-1,x,p+1])
  if y+1<h and p+1<grid[y+1][x]:
    stack.append([y+1,x,p+1])
  if x-1>=0 and p+1<grid[y][x-1]:
    stack.append([y,x-1,p+1])
  if x+1<w and p+1<grid[y][x+1]:
    stack.append([y,x+1,p+1])
    
ans=0
for i in range(len(grid)):
  ans=max(ans,max(grid[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
grid=[None]*h
INF=10**6
stack=[]
for i in range(h):
  s=list(input())
  for j in range(len(s)):
    if s[j]=="#":
      stack.append([i,j,0])
    s[j]=INF
  grid[i]=s
      
while stack:
  v=stack.pop()
  y=v[0]
  x=v[1]
  p=v[2]
  if p<grid[y][x]:
    grid[y][x]=p
  else:
    continue
  if y-1>=0:
    stack.append([y-1,x,p+1])
  if y+1<h:
    stack.append([y+1,x,p+1])
  if x-1>=0:
    stack.append([y,x-1,p+1])
  if x+1<w:
    stack.append([y,x+1,p+1])
    
ans=0
for i in range(len(grid)):
  ans=max(ans,max(grid[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
grid = [list(input()) + [False] for _ in range(H)]
grid = grid + [[False for _ in range(W + 1)]]
d = ((1, 0), (-1, 0), (0, 1), (0, -1))


def bfs(q):
    res_q = deque()
    while len(q):
        x, y = q.popleft()
        for dx, dy in d:
            nx = x + dx
            ny = y + dy

            if grid[nx][ny] == '.':
                res_q.append((nx, ny))
                grid[nx][ny] = '#'
    return res_q


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

res = 0
while len(q):
    res += 1
    q = bfs(q)

print(res - 1)

Submission status: Time Limit Exceeded

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

# d = [[2001] * W for _ in range(H)]


def bfs(q):
    res_q = deque()
    while len(q):
        x, y = q.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy

            if (0 <= nx < H) and (0 <= ny < W) and grid[nx][ny] != '#':
                res_q.append((nx, ny))
                grid[nx][ny] = '#'
    return res_q


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

res = 0
while len(q):
    res += 1
    q = bfs(q)

print(res - 1)

Submission status: Time Limit Exceeded

Solution code:
H, W=map(int, input().split())
A=[input() for _ in range(H)]
board=[[10**9 for _ in range(W)] for _ in range(H)]
black_position=[]
for i in range(H):
  for j in range(W):
    if A[i][j]=="#":
      black_position.append([i, j])
      board[i][j]=0
for i in range(H):
  for j in range(W):
    if board[i][j] in (0, 1):
      continue
    for b in black_position:
      board[i][j]=min(board[i][j], abs(i-b[0])+abs(j-b[1]))
maxv=0
for i in range(H):
  maxv=max(maxv, max(board[i]))
print(maxv)

Submission status: Time Limit Exceeded

Solution code:
import queue
# class Queue:
#     def __init__(self, data=[]):
#         self.data = data
#
#     def enqueue(self, x):
#         self.data.append(x)
#
#     def dequeue(self):
#         return self.data.pop(0)
#
#     def is_Empty(self):
#         if len(self.data) == 0:
#             return True
#         else:
#             return False


H, W = map(int, input().split())  # H行W列

gridgraph = [list(input()) for _ in range(H)]  # H行W列のグリッドグラフ
visited = [[False]*W for _ in range(H)]
cnt = [[0]*W for _ in range(H)]

q = queue.Queue()

for i in range(H):
    for j in range(W):
        if gridgraph[i][j] == '#':
            q.put([i, j])  # 初期の時点で黒色のマスをqueueに追加する
            visited[i][j] = True

while not q.empty():
    cy, cx = q.get()

    for dy, dx in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        if cy+dy >= H or cy+dy < 0 or cx+dx >= W or cx+dx < 0:
            continue
        if visited[cy+dy][cx+dx]:  # すでに訪問済みであればcontinue
            continue
        visited[cy+dy][cx+dx] = True  # 訪問済みにする
        cnt[cy+dy][cx+dx] = cnt[cy][cx] + 1
        q.put([cy+dy, cx+dx])


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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
H, W = map(int, input().split())
gridgraph = []
for line in sys.stdin.readlines():
    line = line.rstrip()
    gridgraph.append(list(line))
q = deque()
visited = [[False]*W for _ in range(H)]
ans = [[1e+9]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if gridgraph[i][j] == "#":
            q.append((i, j))
            visited[i][j] = True
            ans[i][j] = 0

while len(q):
    cy, cx = q.popleft()

    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        if not (cy+dy >= 0 and H-1 >= cy+dy and cx+dx >= 0 and W-1 >= cx+dx):
            continue
        if visited[cy+dy][cx+dx]:
            continue
        visited[cy+dy][cx+dx] = True
        ans[cy+dy][cx+dx] = min(ans[cy+dy][cx+dx], ans[cy][cx]+1)
        q.append((cy+dy, cx+dx))

min_value = 0
for a in ans:
    min_value = max(min_value, max(a))
print(min_value)