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

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

dxdy = [(-1,0), (1,0), (0,-1), (0,1)]
INF = 999999
que = deque()

dist = [[INF] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if grid[i][j] == "#":
            dist[i][j] = 0
            que.append(i*W + j)

ans = 0
while len(que) > 0:
    num = que.popleft()
    h = num // W
    w = num % W
    for dx, dy in dxdy:
        nx = w + dx
        ny = h + dy
        if ny<0 or ny>=H or nx<0 or nx>=W or dist[ny][nx] <= dist[h][w] + 1:
            continue
        dist[ny][nx] = dist[h][w] + 1
        ans = max(ans, dist[ny][nx])
        que.append(ny * W + nx)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

dxdy = [(-1,0), (1,0), (0,-1), (0,1)]
INF = 999999
que = deque()

dist = [[INF] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if grid[i][j] == "#":
            dist[i][j] = 0
            que.append(i*W + j)

ans = 0
while len(que) > 0:
    num = que.popleft()
    h = num // W
    w = num % W
    for dx, dy in dxdy:
        nx = w + dx
        ny = h + dy
        if ny<0 or ny>=H or nx<0 or nx>=W or dist[ny][nx] < INF:
            continue
        dist[ny][nx] = min(dist[ny][nx], dist[h][w]+1)
        ans = max(ans, dist[ny][nx])
        que.append(ny * W + nx)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
L = ['.' * (W + 2)] + [('.' + input() + '.') for _ in range(H)] + ['.' * (W + 2)]
v = [[0 for _ in range(W + 2)]] + [([0] + [-1 for _ in range(W)] + [0]) for _ in range(H)] + [[0 for i in range(W + 2)]]
# print(v)
# v = [[-1 for _ in range(W)] for _ in range(H)]
Q = deque()
for i in range(H + 2):
    for j in range(W + 2):
        if L[i][j] == "#":
            v[i][j] = 0
            Q.append((i, j))
#print(L,v)
# reached = [[-1 for _ in range(W)] for _ in range(H)]
# Q.append((sy, sx))
# step[sy][sx] = 0
L = [[-1, 0], [1, 0], [0, -1], [0, 1]]
a = 0
while Q:
    y, x = Q.popleft()
    # if v[y][x] == -1:
    #     print(step[y][x])
    #     exit()
    # else:
    for i, j in L:
        #print(y,x,y+i,x+j)
        if v[y + i][x + j] == -1:
            Q.append((y + i, x + j))
            v[y + i][x + j] = v[y][x] + 1
            a = max(a, v[y + i][x + j])
print(a)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

dxdy = [(-1,0), (1,0), (0,-1), (0,1)]
INF = 999999
que = deque()

dist = [[INF] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if grid[i][j] == "#":
            dist[i][j] = 0
            que.append((i,j))

ans = 0
while len(que) > 0:
    h, w = que.popleft()
    for dx, dy in dxdy:
        nx = w + dx
        ny = h + dy
        if ny<0 or ny>=H or nx<0 or nx>=W or dist[ny][nx] < INF:
            continue
        dist[ny][nx] = min(dist[ny][nx], dist[h][w]+1)
        ans = max(ans, dist[ny][nx])
        que.append((ny,nx))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = deque()
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat.append((h, w, 0))
            s[w] = 1
        else:
            s[w] = 0
    dp[h] = s

while len(mat):
    h, w, cnt = mat.popleft()

    for t, h, w, cnt in ((h > 0, h - 1, w, cnt),(h < H-1, h + 1, w, cnt),(w > 0, h , w - 1, cnt),(w < W-1, h , w + 1, cnt)):
        if t and dp[h][w] == 0:
            mat.append((h, w, cnt+1))
            dp[h][w] = 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = deque()
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat.append((h, w, 0))
    dp[h] = s

while len(mat):
    h, w, cnt = mat.popleft()

    for t, h, w, cnt in ((h > 0, h - 1, w, cnt),(h < H-1, h + 1, w, cnt),(w > 0, h , w - 1, cnt),(w < W-1, h , w + 1, cnt)):
        if t and dp[h][w] == ".":
            mat.append((h, w, cnt+1))
            dp[h][w] = "#"

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = deque()
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat.append((h, w, 0))
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    if dp[nH][nW] == ".":
        mat.append((nH, nW, cnt+1))
        dp[nH][nW] = "#"

while len(mat):
    h, w, cnt = mat.popleft()

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = [None] * (H*W)
matS = matE = 0
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat[matE] = (h, w, 0)
            matE+=1
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    global matE
    if dp[nH][nW] == ".":
        mat[matE] = (nH, nW, cnt+1)
        matE+=1
        dp[nH][nW] = "#"

while matS < matE:
    h, w, cnt = mat[matS]
    matS += 1

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:

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


#grid=[[int(A[j][i]=="#") for i in range(W)] for j in range(H)]
grid=[[0 for i in range(W)] for j in range(H)]


new_black=[]
#find black
for j in range(H):
	for i in range(W):
		if(A[j][i]=="#"):
		#if(grid[j][i]):
			new_black.append([i,j])
def check(x,y):
	return (0<=x<W and 0<=y<H and grid[y][x]==0 )

i=0
next_black=new_black.copy()
while(len(next_black)!=0):
	next_black=[]
	for black in new_black:
		"""	
		if(check(black[0]-1,black[1])):
			next_black.append([black[0]-1,black[1]])
			grid[black[1]][black[0]-1]=1
		if(check(black[0]+1,black[1])):
			next_black.append([black[0]+1,black[1]])
			grid[black[1]][black[0]+1]=1
		if(check(black[0],black[1]-1)):
			next_black.append([black[0],black[1]-1])
			grid[black[1]-1][black[0]]=1
		if(check(black[0],black[1]+1)):
			next_black.append([black[0],black[1]+1])
			grid[black[1]+1][black[0]]=1
		"""
		if(check(black[0],black[1])):
			grid[black[1]][black[0]]=1
			next_black.append([black[0]+1,black[1]])
			next_black.append([black[0]-1,black[1]])
			next_black.append([black[0],black[1]+1])
			next_black.append([black[0],black[1]-1])

	new_black=next_black.copy()
	i+=1
print(i-2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = [None] * (W*H)
matS = matE = 0
for h in range(H):
    dpr = [-1] * W
    for w, x in zip(range(W), input()):
        if x == "#":
            dpr[w] = 0
            mat[matE] = (h, w, 0)
            matE+=1
    dp[h] = dpr

def search(dp, mat, nH, nW, cnt):
    global matE
    if dp[nH][nW] < 0:
        mat[matE] = (nH, nW, cnt+1)
        matE+=1
        dp[nH][nW] = cnt+1

while matS < matE:
    h, w, cnt = mat[matS]
    matS += 1

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:


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


grid=[[int(A[j][i]=="#") for i in range(W)] for j in range(H)]


new_black=[]
#find black
for j in range(H):
	for i in range(W):
		if(grid[j][i]):
			new_black.append([i,j])

def check(x,y):
	return (0<=x<W and 0<=y<H and grid[y][x]==0 )

i=0
next_black=new_black
while(len(next_black)!=0):
	next_black=[]
	for black in new_black:
		if(check(black[0]-1,black[1])):
			next_black.append([black[0]-1,black[1]])
			grid[black[1]][black[0]-1]=1
		if(check(black[0]+1,black[1])):
			next_black.append([black[0]+1,black[1]])
			grid[black[1]][black[0]+1]=1
		if(check(black[0],black[1]-1)):
			next_black.append([black[0],black[1]-1])
			grid[black[1]-1][black[0]]=1
		if(check(black[0],black[1]+1)):
			next_black.append([black[0],black[1]+1])
			grid[black[1]+1][black[0]]=1
	new_black=next_black
	i+=1
print(i-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = deque()
for h in range(H):
    dpr = [-1] * W
    for w, x in zip(range(W), input()):
        if x == "#":
            dpr[w] = 0
            mat.append((h, w, 0))
    dp[h] = dpr

def search(dp, mat, nH, nW, cnt):
    if dp[nH][nW] < 0:
        mat.append((nH, nW, cnt+1))
        dp[nH][nW] = cnt+1

while len(mat) > 0:
    h, w, cnt = mat.popleft()

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
cnt = [[-1] * w for _ in range(h)]

def bfs():
    queue = deque()
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                queue.append([i, j])
                cnt[i][j] = 0
    while queue:
        i, j = queue.popleft()
        for di, dj in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            if 0 <= i + di < h and 0 <= j + dj < w and cnt[i + di][j + dj] == -1:
                queue.append([i + di, j + dj])
                cnt[i + di][j + dj] = cnt[i][j] + 1

bfs()
print(max([max(l) for l in cnt]))

Submission status: Time Limit Exceeded

Solution code:
def d(i, j, x, y):
    return abs(x - j) + abs(y - i)

s_i = []
s_j = []

a = list(map(int, input().split()))
for i in range(a[0]):
    b = input()
    for j in range(a[1]):
        if b[j] == '#':
            s_i.append(i)
            s_j.append(j)

d_max = 0
diag = d(0, 0, a[1], a[0])

for i in range(a[0]):
    for j in range(a[1]):
        if i not in s_i or j not in s_j:
            d_min = diag
            for p_i, p_j in zip(s_i, s_j):
                dist = d(i, j, p_j, p_i)
                if dist <= d_max:
                    d_min = dist
                    break
                else:
                    d_min = min(d_min, dist)
            d_max = max(d_max, d_min)

print(d_max)

Submission status: Time Limit Exceeded

Solution code:
class Queue():
    def __init__(self):
        self.data = []
        self.idx = 0
        self.size = 0

    def get(self):
        self.idx += 1
        self.size -= 1
        return self.data[self.idx-1]

    def put(self, item):
        self.size += 1
        self.data.append(item)

    def qsize(self):
        return self.size

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

# bfs
bfs = [[-1 for j in range(W)] for i in range(H)]
que = Queue()
for i in range(H):
    for j in range(W):
        if(A[i][j] == '#'):
            que.put((i, j))
            bfs[i][j] = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
while(que.qsize()):
    p = que.get()
    for i in range(4):
        if(0 <= p[0]+dx[i] < H and 0 <= p[1]+dy[i] < W):
            if(bfs[p[0]+dx[i]][p[1]+dy[i]] == -1):
                que.put((p[0]+dx[i], p[1]+dy[i]))
                bfs[p[0]+dx[i]][p[1]+dy[i]] = bfs[p[0]][p[1]] + 1

# print ans
print(max([max(l) for l in bfs]))

Submission status: Time Limit Exceeded

Solution code:
import queue

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

# bfs
bfs = [[-1 for j in range(W)] for i in range(H)]
que = queue.Queue()
for i in range(H):
    for j in range(W):
        if(A[i][j] == '#'):
            que.put_nowait((i, j))
            bfs[i][j] = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
while(que.qsize()):
    p = que.get_nowait()
    for i in range(4):
        if(0 <= p[0]+dx[i] < H and 0 <= p[1]+dy[i] < W):
            if(bfs[p[0]+dx[i]][p[1]+dy[i]] == -1):
                que.put_nowait((p[0]+dx[i], p[1]+dy[i]))
                bfs[p[0]+dx[i]][p[1]+dy[i]] = bfs[p[0]][p[1]] + 1

# print ans
print(max([max(l) for l in bfs]))

Submission status: Time Limit Exceeded

Solution code:
import queue

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

# bfs
bfs = [[-1 for j in range(W)] for i in range(H)]
que = queue.Queue()
for i in range(H):
    for j in range(W):
        if(A[i][j] == '#'):
            que.put((i, j))
            bfs[i][j] = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
while(que.qsize()):
    p = que.get_nowait()
    for i in range(4):
        if(0 <= p[0]+dx[i] < H and 0 <= p[1]+dy[i] < W):
            if(bfs[p[0]+dx[i]][p[1]+dy[i]] == -1):
                que.put((p[0]+dx[i], p[1]+dy[i]))
                bfs[p[0]+dx[i]][p[1]+dy[i]] = bfs[p[0]][p[1]] + 1

# print ans
print(max([max(l) for l in bfs]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

# bfs
bfs = [[-1 for j in range(W)] for i in range(H)]
que = deque()
for i in range(H):
    for j in range(W):
        if(A[i][j] == '#'):
            que.append((i, j))
            bfs[i][j] = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
while(len(que)):
    p = que.popleft()
    for i in range(4):
        if(0 <= p[0]+dx[i] < H and 0 <= p[1]+dy[i] < W):
            if(bfs[p[0]+dx[i]][p[1]+dy[i]] == -1):
                que.append((p[0]+dx[i], p[1]+dy[i]))
                bfs[p[0]+dx[i]][p[1]+dy[i]] = bfs[p[0]][p[1]] + 1

# print ans
print(max([max(l) for l in bfs]))

Submission status: Time Limit Exceeded

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

queue = []
dis = [[-1]*W for _ in range(H)]

A = [[0]*W for _ in range(H)]

for y in range(H):
    a = input()
    for x in range(W):
        A[y][x] = a[x]
        if a[x] == '#':
            queue.append((y, x))
            dis[y][x] = 0

ans = 0
while queue:
    y, x = queue.pop(0)
    for i in range(4):
        yy = y + [1, 0, -1, 0][i]
        xx = x + [0, 1, 0, -1][i]
        if 0 <= yy < H and 0 <= xx < W and dis[yy][xx] == -1:
            dis[yy][xx] = dis[y][x] + 1
            queue.append((yy, xx))
            ans = max(ans, dis[yy][xx])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

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

# bfs
bfs = [[-1 for j in range(W)] for i in range(H)]
que = queue.Queue()
for i in range(H):
    for j in range(W):
        if(A[i][j] == '#'):
            que.put((i, j))
            bfs[i][j] = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
while(que.qsize()):
    p = que.get()
    for i in range(4):
        if(0 <= p[0]+dx[i] < H and 0 <= p[1]+dy[i] < W):
            if(bfs[p[0]+dx[i]][p[1]+dy[i]] == -1):
                que.put((p[0]+dx[i], p[1]+dy[i]))
                bfs[p[0]+dx[i]][p[1]+dy[i]] = bfs[p[0]][p[1]] + 1

# print ans
print(max([max(l) for l in bfs]))

Submission status: Time Limit Exceeded

Solution code:

from collections import deque

def read_input():
    h, w = map(int, input().split())
    board = []

    for i in range(h):
        board.append([c for c in input()])

    return h, w, board

def submit():
    def check_index(t):
        if 0 <= t[0] < h and 0 <= t[1] < w:
            return True
        return False

    h, w, board = read_input()

    count = {}
    q = deque()
    for i in range(h):
        for j in range(w):
            if board[i][j] == '#':
                count[(i, j)] = 0
                q.appendleft((i, j))
            else:
                count[(i, j)] = -1

    while len(q) > 0:
        focus = q.pop()

        r = (focus[0], focus[1] + 1)
        l = (focus[0], focus[1] - 1)
        u = (focus[0] - 1, focus[1])
        d = (focus[0] + 1, focus[1])


        if check_index(r) and count[r] == -1:
            count[r] = count[focus] + 1
            q.appendleft(r)

        if check_index(l) and count[l] == -1:
            count[l] = count[focus] + 1
            q.appendleft(l)

        if check_index(u) and count[u] == -1:
            count[u] = count[focus] + 1
            q.appendleft(u)

        if check_index(d) and count[d] == -1:
            count[d] = count[focus] + 1
            q.appendleft(d)


    print(max(count.values()))


if __name__ == '__main__':
    submit()

Submission status: Time Limit Exceeded

Solution code:

from collections import deque

def read_input():
    h, w = map(int, input().split())
    board = []

    for i in range(h):
        board.append([c for c in input()])

    return h, w, board

def submit():
    def check_index(t):
        if 0 <= t[0] < h and 0 <= t[1] < w:
            return True
        return False

    h, w, board = read_input()

    count = {}
    q = deque()
    for i in range(h):
        for j in range(w):
            if board[i][j] == '#':
                count[(i, j)] = 0
                q.appendleft((i, j))
            else:
                count[(i, j)] = -1

    while len(q) > 0:
        focus = q.pop()

        r = (focus[0], focus[1] + 1)
        l = (focus[0], focus[1] - 1)
        u = (focus[0] - 1, focus[1])
        d = (focus[0] + 1, focus[1])

        for t in [r, l, u, d]:
            if check_index(t) and count[t] == -1:
                count[t] = count[focus] + 1
                q.appendleft(t)

    print(max(count.values()))


if __name__ == '__main__':
    submit()

Submission status: Time Limit Exceeded

Solution code:
import queue

q = queue.Queue()
H, W = list(map(int, input().split()))
A = [input() for i in range(H)]
board = [[10**20 for i in range(W)] for j in range(H)]
ans = 0

for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            q.put((i, j, 0))
            
while not q.empty():
    i, j, n = q.get()
    ans = max(ans, n)
    if n < board[i][j]:
        board[i][j] = n
        for i_, j_ in [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]:
            if -1 < i_ and -1 < j_ and i_ < H and j_ < W and board[i_][j_] == 10**20:
                q.put((i_, j_, n+1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit
import queue
import numpy as np
Q = queue.Queue()
H,W = [int(n) for n in input().split()]
INF = (1 << 21)
dxy = [[1,0],[-1,0],[0,1],[0,-1]]
A = [0 for _ in range(H)]
black = []
dis = np.array([[0 for _ in range(W)] for _ in range(H)])
for i in range(H):
    A[i] = list(str(input()))
    for j in range(len(A[i])):
        if(A[i][j] == "#"):
            Q.put((i,j))
A = np.array(A)
while(not Q.empty()):
    now = Q.get()
    A[now[0]][now[1]] = "#"
    for d in dxy:
        i,j = now[0]+d[0], now[1]+d[1]
        if(0 <= i <= H-1 and 0 <= j <= W-1 and A[i][j] == "."):
            A[i][j] = "#"
            Q.put((i,j))
            dis[i][j] = dis[now[0]][now[1]] + 1
ans = 0
for i in range(H):
    tmp = np.max(dis[i])
    ans = max(ans,tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
que = deque(maxlen=h * w)
next = deque(maxlen=h * w)

data = []

for ln in range(h):
    line = list(input().rstrip())
    data.append(line)
    for r, letter in enumerate(line):
        if letter == '#':
            que.append((ln, r))

count = 0

while len(que) > 0:
    count += 1
    while len(que) > 0:
        row, col = que.popleft()
        for r, c in ((row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)):
            if 0 <= r < h and 0 <= c < w and data[r][c] == '.':
                next.append((r, c))
                data[r][c] = '#'
    que, next = next, que
    next.clear()

print(count - 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
A = []
for _ in range(H):
    row = input()
    assert len(row) == W
    A.append(row)

worklist = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            worklist.append((0, i, j))  # 距離, y, x

vs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
table = {}
m = 0
while len(worklist) > 0:
    d, i, j = worklist.popleft()
    if (i, j) not in table:
        table[(i, j)] = d
        m = max(m, d)
        for vi, vj in vs:
            if 0 <= i + vi < H and 0 <= j + vj < W:
                worklist.append((d + 1, i + vi, j + vj))

print(m)

Submission status: Time Limit Exceeded

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

queue = []
dis = [[0]*W for _ in range(H)]

A = [[0]*W for _ in range(H)]

for y in range(H):
    a = input()
    for x in range(W):
        A[y][x] = a[x]
        if a[x] == '#':
            queue.append((y, x))
            dis[y][x] = 0

ans = 0
while queue:
    y, x = queue.pop(0)
    for i in range(4):
        yy = y + [1, 0, -1, 0][i]
        xx = x + [0, 1, 0, -1][i]
        if 0 <= yy < H and 0 <= xx < W and dis[yy][xx] == 0:
            dis[yy][xx] = dis[y][x] + 1
            queue.append((yy, xx))
            ans = max(ans, dis[yy][xx])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = []
for _ in range(H):
    row = input()
    assert len(row) == W
    A.append(row)

worklist = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            worklist.append((0, i, j))  # 距離, y, x

vs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
table = {}
while len(worklist) > 0:
    d, i, j = worklist.pop()
    if (i, j) not in table or d < table[(i, j)]:
        table[(i, j)] = d
        for vi, vj in vs:
            if 0 <= i + vi < H and 0 <= j + vj < W:
                worklist.append((d + 1, i + vi, j + vj))

print(max(table.values()))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = []
for _ in range(H):
    row = input()
    assert len(row) == W
    A.append(row)

worklist = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            worklist.append((0, i, j))  # 距離, y, x

vs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
table = {}
while len(worklist) > 0:
    d, i, j = worklist.pop(0)
    if (i, j) not in table or d < table[(i, j)]:
        table[(i, j)] = d
        for vi, vj in vs:
            if 0 <= i + vi < H and 0 <= j + vj < W:
                worklist.append((d + 1, i + vi, j + vj))

print(max(table.values()))

Submission status: Time Limit Exceeded

Solution code:
import collections
H,W=map(int,input().split())
went=[[False]*W for i in range(H)]
queue=collections.deque()
for hoge in range(H):
    for huga,t in enumerate(input()):
        if t=="#":
            went[hoge][huga]=True
            queue.append([hoge,huga,0])
while queue:
    curx,cury,ct=queue.popleft()
    for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
        newx,newy=curx+dx,cury+dy
        newct=ct+1
        if 0<=newx<H and 0<=newy<W and (not went[newx][newy]):
            went[newx][newy]=True
            queue.append([newx,newy,newct])
print(ct)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import collections
H,W=map(int,input().split())
went=[[False]*W for i in range(H)]
queue=collections.deque()
for hoge in range(H):
    for huga,t in enumerate(input()):
        if t=="#":
            went[hoge][huga]=True
            queue.append([hoge,huga,0])
while queue:
    curx,cury,ct=queue.popleft()
    for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
        newx,newy=curx+dx,cury+dy
        newct=ct+1
        if 0<=newx<H and 0<=newy<W and (not went[newx][newy]):
            went[newx][newy]=True
            queue.append([newx,newy,newct])
print(ct)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
maze = [input() for i in range(H)]
reached = [[0] * W for i in range(H)]
L = []

que = deque([])

for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            L.append(0)
            continue
        que.append([i, j])
        while que:
            py, px = que.popleft()
            dy = (0, 1, 0, -1)
            dx = (1, 0, -1, 0)
            for k, t in zip(dy, dx):
                ny = py + k
                nx = px + t
                if ny < 0 or ny >= H or nx < 0 or nx >= W:
                    continue
                if reached[ny][nx]:
                    continue

                que.append([ny, nx])
                reached[ny][nx] += reached[py][px] + 1

                if maze[ny][nx] == '#':
                    L.append(reached[ny][nx])
                    reached = [[0] * W for i in range(H)]
                    que = deque([])
                    break
                    
print(max(L))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import collections
H,W=map(int,input().split())
A=[input() for j in range(H)]
went=[[False]*W for i in range(H)]
queue=collections.deque()
for x,i in enumerate(A):
    for y,j in enumerate(i):
        if j=="#":
            went[x][y]=True
            queue.append([x,y,0])
while queue:
    curx,cury,ct=queue.popleft()
    for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
        newx,newy=curx+dx,cury+dy
        newct=ct+1
        if 0<=newx<H and 0<=newy<W and (not went[newx][newy]):
            went[newx][newy]=True
            queue.append([newx,newy,newct])
print(ct)

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys

#入力
H, W = map(int, input().split())

lst = []
for i in range(H):
    lst += [list(input())]

count = 0
INF = 10 ** 9
q =collections.deque() #動作用のqueue
dp = [[INF] * W for _ in range(H)] #そのマスを確認したかのフラグ
#print (dp)

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

def check(): #確認の起点になっていない黒マスを全てqueueに入れる
    for i in range(H):
        for j in range(W):
#            print ('i, j, count =', i, j, count)
            if lst[i][j] == '#': #黒マスであることの確認
               if  dp[i][j] == INF:#dp[i][j]がINF= 初回黒のところ
                   q.append([i, j])
#                   print ('INF')
                   dp[i][j] = 0 #フラグを0-->0回で変えることができる
               elif dp[i][j] == count: #dp[i][j] == count-->count回目で黒に変わったもの
#                   print ('dp[i][j]= ', dp[i][j])
                   q.append([i, j])
#                   print (q)
#                   print ('A')
    return

def change(px, py): #現在座標(px,py)から上下左右のマスを白に変え、手数を記録する
    for dx, dy in move:
        nx = px + dx
        ny = py + dy
        if 0 <= nx and nx < H and 0 <= ny and ny < W: #移動先が範囲内であることの確認
            dp[nx][ny] = min(dp[px][py] +1, dp[nx][ny]) #すでに入っている値と新しい値の小さい方を記録し直す
            lst[nx][ny] = '#' #移動先を黒色に変える


while True:
    check() #未確認の黒マスをdequeに入れる
#    print (q)
    if not q: #dequが空の時
        print (count-1) #現在までに変えた回数 = count を入れて終わる
        sys.exit()
    else: #dequeが空でない= 未確認の黒マスがある
       while q: #dequeが空になるまで回す
           px, py = q.popleft()
           change(px, py)
       count += 1
#       print (count, '回変えた後',dp)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import collections
H,W=map(int,input().split())
A=[input() for j in range(H)]
went=[[False]*W for i in range(H)]
queue=collections.deque()
for x,i in enumerate(A):
    for y,j in enumerate(i):
        if j=="#":
            went[x][y]=True
            queue.append((x,y,0))
while queue:
    curx,cury,ct=queue.popleft()
    for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
        newx,newy=curx+dx,cury+dy
        newct=ct+1
        if 0<=newx<H and 0<=newy<W and (not went[newx][newy]):
            went[newx][newy]=True
            queue.append((newx,newy,newct))
print(ct)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import collections
deque=collections.deque
H,W=map(int,input().split())
A=[list(input()) for j in range(H)]
went=[[False]*W for i in range(H)]
queue=deque()
for x,i in enumerate(A):
    for y,j in enumerate(i):
        if j=="#":
            went[x][y]=True
            queue.append((x,y,0))
while queue:
    curx,cury,ct=queue.popleft()
    for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
        newx,newy=curx+dx,cury+dy
        newct=ct+1
        if 0<=newx<H and 0<=newy<W and (not went[newx][newy]):
            went[newx][newy]=True
            queue.append((newx,newy,newct))
print(ct)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from pprint import pprint

def solve(H: int, W: int, A: "List[str]"):
    used = [[False] * W for _ in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, -1, 0, 1]
    s = set()
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                s.add((i, j))
                used[i][j] = True

    ret = 0
    while True:
        nex = set()
        for x, y in s:
            for j in range(4):
                tx = x + dx[j]
                ty = y + dy[j]
                if 0 <= tx < H and 0 <= ty < W and not used[tx][ty]:
                    nex.add((tx, ty))
                    used[tx][ty] = True
        if len(nex) < 1:
            break
        s = nex
        ret += 1

    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, A)

if __name__ == '__main__':
    main()