Problem:


Score : 300 points

Problem Statement

You are given a grid of squares with H horizontal rows and W vertical columns, where each square is painted white or black.
HW characters from A_{11} to A_{HW} represent the colors of the squares.
A_{ij} is # if the square at the i-th row from the top and the j-th column from the left is black, and A_{ij} is . if that square is white.

We will repeatedly perform the following operation until all the squares are black:

Every white square that shares a side with a black square, becomes black.

Find the number of operations that will be performed.
The initial grid has at least one black square.

Constraints

1 \leq H,W \leq 1000

A_{ij} is # or ..

The given grid has at least one black square.

Input

Input is given from Standard Input in the following format:

H W
A_{11}A_{12}...A_{1W}
:
A_{H1}A_{H2}...A_{HW}

Output

Print the number of operations that will be performed.

Sample Input 1

3 3
...
.#.
...

Sample Output 1

2

After one operation, all but the corners of the grid will be black. After one more operation, all the squares will be black.

Sample Input 2

6 6
..#..#
......
#..#..
......
.#....
....#.

Sample Output 2

3



Sample input:
3 3
...
.#.
...


Sample output:
2

Submission status: Time Limit Exceeded

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

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

maze = []
for _ in range(H):
    maze.append(input())
    
q = deque()
saitan = [1000000]*H*W
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            q.append(i*W+k)
            saitan[i*W+k] = 0
len_q = len(q)

#print(start)
def bfs(h,w,q,Saitan,len_Q):
    
    while q and len_Q < h * w:
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for i,k in ([1,0],[-1,0],[0,1],[0,-1]):
            my = y + i
            mx = x + k
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
            len_Q += 1
            #Sumi.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,saitan,len_q))
#print(saitan)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
q = deque()
saitan = [1000000]*H*W
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            q.append(i*W+k)
            saitan[i*W+k] = 0
len_q = len(q)

#print(start)
def bfs(h,w,q,Saitan,len_Q):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0 and len_Q < h * w:
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
            len_Q += 1
            #Sumi.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,saitan,len_q))
#print(saitan)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
q = deque()
saitan = [1000000]*H*W
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            q.append(i*W+k)
            saitan[i*W+k] = 0

#print(start)
def bfs(h,w,q,Saitan):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0:
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
            #Sumi.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,saitan))
#print(saitan)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
q = deque()
saitan = [1000000]*H*W
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            q.append(i*W+k)
            saitan[i*W+k] = 0

#print(start)
def bfs(h,w,q,Saitan):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0 and (1000000 in saitan):
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
            #Sumi.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,saitan))
#print(saitan)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
q = deque()
saitan = [1000000]*H*W
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            q.append(i*W+k)
            saitan[i*W+k] = 0

#print(start)
def bfs(h,w,q,Saitan):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0 and (1000000 in saitan):
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if saitan[(my*w + mx)] != 1000000:
                #print('b')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
            #Sumi.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,saitan))
#print(saitan)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
q = deque()
saitan = [1000000]*H*W
start = []
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            start.append(i*W+k)

for i in start:
    q.append(i)
    saitan[i] = 0
#print(start)
def bfs(h,w,q,Saitan):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0 and 1000000 in saitan:
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if saitan[(my*w + mx)] != 1000000:
                #print('b')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
            #Sumi.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,saitan))
#print(saitan)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
q = deque()
saitan = [1000000]*H*W
start = []
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            start.append(i*W+k)

for i in start:
    q.append(i)
    saitan[i] = 0
#print(start)
def bfs(h,w,q,Saitan):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0:
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if saitan[(my*w + mx)] != 1000000:
                #print('b')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
            #Sumi.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,saitan))
#print(saitan)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
q = deque()
saitan = [1000000]*H*W
start = []
sumi= []
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            start.append(i*W+k)

for i in start:
    q.append(i)
    sumi.append(i)
    saitan[i] = 0
#print(start)
def bfs(h,w,q,Sumi,Saitan):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0:
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if (my*w + mx) in Sumi:
                #print('b')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
            Sumi.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,sumi,saitan))
#print(saitan)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
q = deque()
saitan = [1000000]*H*W
start = []
sumi= []
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            start.append(i*W+k)

for i in start:
    q.append(i)
    saitan[i] = 0
#print(start)
def bfs(h,w,q,Sumi,Saitan):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0:
        j = q.popleft()
        sumi.append(j)
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if (my*w + mx) in Sumi:
                #print('b')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,sumi,saitan))
#print(saitan)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
B = deque()
check = [[H*W for _ in range(W)] for _ in range(H)]
for h in range(H):
    a = input()
    if a.count("#") > 0:
        b = [(h, w) for w, e in enumerate(a) if e == "#"]
        B += b
        for bx, bw in b:
            check[bx][bw] = 0

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

while B:
    x, y = B.pop()
    for dx, dy in move:
        nx, ny = x + dx, y + dy
        if -1 < nx < H and -1 < ny < W:
            if check[nx][ny] > check[x][y] + 1:
                check[nx][ny] = check[x][y] + 1
                B.appendleft((nx, ny))
print(max(max(c) for c in check))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
A = [[2000 for _ in range(W)] for _ in range(H)]
B = []
for h in range(H):
    a = input()
    if a.count("#") > 0:
        for w, e in enumerate(a):
            if e == "#":
                B.append((h, w))
                A[h][w] = 0

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

for b in B:
    stack = deque()
    stack.append(b)
    while stack:
        x, y = stack.pop()
        for dx, dy in move:
            nx, ny = x + dx, y + dy
            if -1 < nx < H and -1 < ny < W:
                if A[x][y] + 1 < A[nx][ny]:
                    A[nx][ny] = A[x][y] + 1
                    stack.append((nx, ny))
print(max(max(a) for a in A))

Submission status: Time Limit Exceeded

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

black, white = [], 0
for y, line in enumerate(STAGE):
	for x, cell in enumerate(line):
		if "#" == cell:
			black += [(y, x)]
		else:
			white += 1

stage = STAGE
ds = ((0, 1), (1, 0), (0, -1), (-1, 0))

def get_next(p, d):
	n = (p[0] + d[0], p[1] + d[1])
	if 0 <= n[0] < H and 0 <= n[1] < W:
		return n
	return None

def set_val(p, v):
	global stage
	stage[p[0]][p[1]] = v

def get_val(p):
	return stage[p[0]][p[1]]

count = 0
while white:
	count += 1
	next_black = []
	for b in black:
		for d in ds:
			n = get_next(b, d)
			if n:
				v = get_val(n)
				if "." == v:
					white -= 1
					set_val(n, "#")
					next_black += [n]
	black = next_black

print(count)

Submission status: Time Limit Exceeded

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

from collections import deque

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

field = [[0] * W for _ in range(H)]
field_dist = [[2000] * W for _ in range(H)]
move_history = [[[False] * 4 for _ in range(W)] for _ in range(H)]
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            field[i][j] = 1
            init_h = i
            init_w = j
'''
import random
H, W = 1000, 1000
field = [[0] * W for _ in range(H)]
field_dist = [[2000] * W for _ in range(H)]
move_history = [[[False] * 4 for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if random.randint(0, 2) % 2 == 0:
            field[i][j] = 1
            init_h = i
            init_w = j
'''
            
d = deque([[init_h, init_w]])
reverse_d = []
while len(d) > 0:
    cur_h, cur_w = d.popleft()
    cur_d = abs(init_h - cur_h) + abs(init_w - cur_w)
    
    if field[cur_h][cur_w] == 1:
        field_dist[cur_h][cur_w] = 0
    
    for i, (dh, dw) in enumerate([[0, 1], [0, -1], [1, 0], [-1, 0]]):
        if move_history[cur_h][cur_w][i] == False:
            move_history[cur_h][cur_w][i] = True
            if (cur_h + dh) >= 0 and (cur_h + dh) < H and (cur_w + dw) >= 0 and (cur_w + dw) < W:
                next_d = abs(init_h - (cur_h + dh)) + abs(init_w - (cur_w + dw))
                if next_d > cur_d:
                    field_dist[cur_h+dh][cur_w+dw] = min(field_dist[cur_h+dh][cur_w+dw], field_dist[cur_h][cur_w]+1)
                    d.append([cur_h+dh, cur_w+dw])
                    reverse_d.append([cur_h+dh, cur_w+dw, cur_h, cur_w])
         
max_dist = 0
while len(reverse_d) > 0:
    s_h, s_w, d_h, d_w = reverse_d.pop()
    if field_dist[s_h][s_w] + 1 < field_dist[d_h][d_w]:
        field_dist[d_h][d_w] = field_dist[s_h][s_w] + 1
    max_dist = max(max_dist, field_dist[s_h][s_w])

print(max_dist)
'''
for i in range(H):
    for j in range(W):
        print(field_dist[i][j], end=' ')
    print()
'''

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
from collections import defaultdict
import math
import re

def abs(x):
    return x if x > 0 else -x

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

    A = []
    D = defaultdict(lambda: BIG_NUM)
    updated = set()
    for h in range(H):
        A_list = list(input())
        A_list = [a == "#" for a in A_list]
        w_list = [(h, w) for w, a in enumerate(A_list) if a]
        for h, w in w_list:
            D[(h, w)] = 0
            updated.add((h, w))

    while updated:
        new_updated = set()
        for h, w in updated:
            for delta_h, delta_w in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                if h+delta_h > 0 and h+delta_h < H\
                    and w+delta_w > 0 and w+delta_w < W:

                    if D[(h+delta_h, w+delta_w)] > D[(h, w)] + 1:
                        D[(h+delta_h, w+delta_w)] = D[(h, w)] + 1
                        new_updated.add((h+delta_h, w+delta_w))
        updated = new_updated

    max_d = max(D.values())
    print(max_d)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
from collections import defaultdict
import math
import re

def abs(x):
    return x if x > 0 else -x

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

    blacks = set()
    A = []
    for h in range(H):
        A_list = list(input())
        A_list = [a == "#" for a in A_list]
        w_list = [(h, w) for w, a in enumerate(A_list) if a]
        blacks.update(w_list)
        A.append(A_list)

    max_d = 0
    for h in range(H):
        for w in range(W):
            min_d = H * W
            for bh, bw in blacks:
                d = abs(bh - h) + abs(bw - w)
                if d < min_d:
                    min_d = d

            if min_d > max_d:
                max_d = min_d

    print(max_d)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

visited = [[float('inf')] * W for i in range(H)]

def bfs():
    queue = deque()
    for i in range(H):
      for j in range(W):
        if A[i][j] == '#':
            queue.append([i,j])
            visited[i][j] = 0

    while queue:
        y,x = queue.popleft()
    
        for i in range(4):
            nx = x + dy[i]
            ny = y + dx[i]
    
            if 0 <= ny < H and 0 <= nx < W and visited[ny][nx] == float('inf'):
                queue.append([ny,nx])
                visited[ny][nx] = visited[y][x] + 1
    
    tmp = 0
    for k in range(H):
        if tmp < max(visited[k]):
            tmp = max(visited[k])
    
    return tmp

print(bfs())

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
a = [input() for i in range(H)]

# 黒マスの位置を記録
stack = []
black_map = [[ a[i][j] == "#" for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if a[i][j] == "#":
            stack.append([i, j])

cnt = 0
while True:
    _stack = []
    for pos in stack:
        for i in [[-1,0], [1, 0], [0, -1], [0, 1]]:
            _x = pos[0] + i[0]
            _y = pos[1] + i[1]
            if 0 <= _x <= H-1 and 0 <= _y <= W-1 and not black_map[_x][_y]:
                _stack.append([_x, _y])
                black_map[_x][_y] = True
    if len(_stack) > 0:
        stack = _stack[::]
    else:
        break
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
a = []
INF = 10 ** 9
for i in range(H):
    a.append(input())

# 黒マスの位置を記録
stack = []
black_map = [[ a[i][j] == "#" for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if a[i][j] == "#":
            stack.append([i, j])

cnt = 0
while True:
    _stack = []
    for pos in stack:
        for i in [[-1,0], [1, 0], [0, -1], [0, 1]]:
            _x = pos[0] + i[0]
            _y = pos[1] + i[1]
            if 0 <= _x <= H-1 and 0 <= _y <= W-1 and not black_map[_x][_y]:
                _stack.append([_x, _y])
                black_map[_x][_y] = True
    if len(_stack) > 0:
        stack = _stack[::]
    else:
        break
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
a = []
INF = 10 ** 9
for i in range(H):
    a.append(input())

# 黒マスの位置を記録
black_stack = []
black_map = {}
for i in range(H):
    for j in range(W):
        if a[i][j] == "#":
            black_stack.append([i, j])
            black_map[str(i) + ":" + str(j)] = True

cnt = 0
while len(black_map.keys()) != H*W:
    next_stack = []
    cnt += 1
    for pos in black_stack:
        for i in [[-1,0], [1, 0], [0, -1], [0, 1]]:
            if 0 <= pos[0] + i[0] <= H-1 and 0 <= pos[1] + i[1] <= W-1:
                    next_stack.append([pos[0] + i[0], pos[1] + i[1]])
                    if str(pos[0] + i[0]) + ":" + str(pos[1] + i[1]) not in black_map:
                        black_map[str(pos[0] + i[0]) + ":" + str(pos[1] + i[1])] = True
    black_stack = next_stack[::]
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
a = []
INF = 10 ** 9
for i in range(H):
    a.append(input())

# 黒マスの位置を記録
black_stack = []
for i in range(H):
    for j in range(W):
        if a[i][j] == "#":
            black_stack.append([i, j])
black_map = black_stack[::]
cnt = 0
while len(black_map) != H*W:
    next_stack = []
    cnt += 1
    for pos in black_stack:
        for i in [[-1,0], [1, 0], [0, -1], [0, 1]]:
            if 0 <= pos[0] + i[0] <= H-1 and 0 <= pos[1] + i[1] <= W-1:
                    next_stack.append([pos[0] + i[0], pos[1] + i[1]])
                    if [pos[0] + i[0], pos[1] + i[1]] not in black_map:
                        black_map.append([pos[0] + i[0], pos[1] + i[1]])
    black_stack = next_stack[::]
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy
H,W = map(int,input().split())
A = [list(input()) for i in range(H)]
#######
p = queue.Queue()
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            p.put([h-1,w])
            p.put([h+1,w])
            p.put([h,w-1])
            p.put([h,w+1])
ans = 0
while True:
    q = copy.copy(p)
    p = queue.Queue()
    while not(q.empty()):
        x = q.get()
        h,w = x[0],x[1]
        if h<0 or h>=H or w<0 or w>=W or A[h][w]=="#":
            continue
        A[h][w] = "#"
        p.put([h-1,w])
        p.put([h+1,w])
        p.put([h,w-1])
        p.put([h,w+1])
    if p.empty():
        break
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
H,W = map(int,input().split())
A = [list(input()) for i in range(H)]
#######
p,q = [],[]
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            p.append([h-1,w])
            p.append([h+1,w])
            p.append([h,w-1])
            p.append([h,w+1])
ans = 0
while True:
    q = copy.copy(p)
    p.clear()
    while len(q)!=0:
        h,w = q[0][0],q[0][1]
        del q[0]
        if h<0 or h>=H or w<0 or w>=W or A[h][w]=="#":
            continue
        A[h][w] = "#"
        p.append([h-1,w])
        p.append([h+1,w])
        p.append([h,w-1])
        p.append([h,w+1])
    if p==[]:
        break
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
[h,w] = [int(i) for i in input().split()]
a =[]
a.append(["#"]*(w+2))
b = ["#"]

for i in range(h):
    s = input()
    for j in range(w):
        b.append(s[j])
    b.append("#")
    a.append(b)
    b = ["#"]
a.append(["#"]*(w+2))

"""
for i in range(h+2):
    for j in range(w+2):
        print(a[i][j],end = "")
    print("")

print([["#"] * (w+2)] * (h+2))
"""

ls = []

cnt = 0
while a != [["#"] * (w+2)] * (h+2):
    for i in range(1,h+1):
        for j in range(1,w+1):
            if a[i][j] == "#":
                ls.append([i-1,j])
                ls.append([i+1,j])
                ls.append([i,j-1])
                ls.append([i,j+1])

    cnt += 1
    for i in ls:
        a[i[0]][i[1]] = "#"
    """
    print("")
    for i in range(1,h+1):
        for j in range(1,w+1):
            print(a[i][j],end = "")
        print("")
    """
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h,w=map(int,input().split())
graph=[[0 if i=='#' else float('inf') for i in list(input())] for _ in range(h)]
graph=np.array(graph)

def bfs():
    for x in range(h):
        for y in range(w):
            for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
                if 0<=x+dx<h and 0<=y+dy<w:
                    graph[x+dx][y+dy]=np.minimum(graph[x][y]+1,graph[x+dx][y+dy])
while np.max(graph)==float('inf'):
    bfs()
print(int(np.max(graph)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
field=[list(input()) for _ in range(h)]
graph=[[float('inf')]*w for _ in range(h)]
queue=deque()
for i in range(h):
    for j in range(w):
        if field[i][j]=='#':
            queue.append([i,j])
            graph[i][j]=0

def bfs():
    while queue:
        x,y=queue.popleft()
        for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
            if 0<=x+dx<h and 0<=y+dy<w:
                if graph[x+dx][y+dy]==float('inf'):
                    graph[x+dx][y+dy]=graph[x][y]+1
                    queue.append([x+dx,y+dy])
bfs()
print(max(max(graph[s]) for s in range(h)))

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
A = [input() for _ in range(H)]

count = [[0]*W for _ in range(H)]
q = deque([])

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

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

while len(q) >= 1:
	i, j = q.popleft()
	# print(i, j)
	for x, y in zip(dx, dy):
		ny = i + y
		nx = j + x
		if 0 <= nx <= W-1 and 0 <= ny <= H-1 and count[ny][nx] == 0 and A[ny][nx] != "#":
			count[ny][nx] = count[i][j] + 1
			q.append((ny, nx))

ans = 0
for i in range(H):
	ans = max(ans, max(count[i]))
# print(count)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = [int(x) for x in input().split()]
A = [[x for x in input()] for _ in range(H)]
#%%
maps = [[-1]*W for _ in range(H)]
mv=[[1,0],[-1,0],[0,1],[0,-1]]
cnt = 0
li=[]
que = []
for h,i in enumerate(A):
    for w,j in enumerate(i):
        if(j=='#'):
            maps[h][w]=0
            que.append([h,w])
while(True):
    next_que=[]
    while(que):
        x = que.pop()
        now = maps[x[0]][x[1]]
        for i in mv:
            if(0<=x[0]+i[0]<H and 0<=x[1]+i[1]<W):
                if(maps[x[0]+i[0]][x[1]+i[1]]==-1):
                    maps[x[0]+i[0]][x[1]+i[1]]=now+1
                    next_que.append([x[0]+i[0],x[1]+i[1]])
    if(len(next_que)==0):
        break
    else:
        cnt += 1
        que=next_que
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
field=[list(input()) for _ in range(h)]
graph=[[float('inf')]*w for _ in range(h)]
queue=deque()
count=0
for i in range(h):
    for j in range(w):
        if field[i][j]=='#':
            queue.append([i,j])
            graph[i][j]=0

def bfs():
    x,y=queue.popleft()
    for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=x+dx<h and 0<=y+dy<w:
            if graph[x+dx][y+dy]==float('inf'):
                graph[x+dx][y+dy]=graph[x][y]+1
                queue.append([x+dx,y+dy])
while queue:
    bfs()
print(max(max(graph[s]) for s in range(h)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w = map(int, input().split(' '))
a = [input() for _ in range(h)]
d = [[float('inf') for _ in range(w)] for _ in range(h)]
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

que = []
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            d[i][j] = 0
            if (i + 1 < h and a[i+1][j] == '.') or (i - 1 >= 0 and a[i-1][j] == '.') or (j + 1 < w and a[i][j+1] == '.') or (j - 1 >= 0 and a[i][j-1] == '.'):
                que.append((i, j))


while len(que) > 0:
    y, x = que.pop(0)

    for dy, dx in move:
        ny = y + dy
        nx = x + dx

        if (ny >= 0 and ny < h) and (nx >= 0 and nx < w) and a[ny][nx] == '.' and d[ny][nx] == float('inf'):
            d[ny][nx] = d[y][x] + 1
            if (ny + 1 < h and a[ny + 1][nx] == '.') or (ny - 1 >= 0 and a[ny - 1][nx] == '.') or (nx + 1 < w and a[ny][nx + 1] == '.') or (nx - 1 >= 0 and a[ny][nx - 1] == '.'):
                que.append((ny, nx))

print(np.max(d))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

a = []
que = []
for i in range(h):
    aa = input()
    a.append(aa)
    for j, aaa in enumerate(aa):
        if aaa == '#':
            d[i][j] = 0
            que.append((i, j))

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

while len(que) > 0:
    y, x = que.pop(0)

    for dy, dx in move:
        ny = y + dy
        nx = x + dx

        if (ny >= 0 and ny < h) and (nx >= 0 and nx < w) and a[ny][nx] == '.' and d[ny][nx] == float('inf'):
            que.append((ny, nx))
            d[ny][nx] = d[y][x] + 1

print(np.max(d))

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
board = []
cnt = 0
 
def show(blacks, h, w):
  for hh in range(h):
    for ww in range(w):
      print('#' if (hh, ww) in blacks else '.', end='')
    print()
 
for hh in range(h):
  board.append(list(input()))
 
blacks = {}
frontier = {}
for hh in range(h):
  for ww in range(w):
    if board[hh][ww] == '#':
      blacks[(hh,ww)] = True
      frontier[(hh,ww)] = True
 
moves = 0
 
while not len(blacks.keys()) == h * w:
  #show(blacks, h, w)
  new_frontier = {}
  for fh, fw in frontier:
    for hh, ww in [(fh+1, fw), (fh-1, fw), (fh, fw+1), (fh, fw-1)]:
      if hh >= h or hh < 0 or ww >= w or ww < 0:
        continue
      if not (hh, ww) in blacks:
        new_frontier[(hh, ww)] = True
        blacks[(hh, ww)] = True
  frontier = new_frontier
  moves += 1
#show(blacks, h, w)
print(moves)