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:
# coding: utf-8
#!/usr/bin/env python3

import queue

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

# direction vector
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]

# 訪れたかどうかの情報を持つ bool 値
is_visited = [ [False] * w for _ in range(h) ]

q = queue.Queue()

for x in range(w):
    for y in range(h):
        if a[y][x] == "#":
            q.put( (x, y, 0) )
            is_visited[y][x] = True

ans = 0

while not q.empty():
    # queue の先頭を取り出す
    x, y, dist = q.get()
    ans = max(ans, dist)
    # 4方向にループ
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0 or w <= nx or ny < 0 or h <= ny:
            continue

        if is_visited[ny][nx]:
            continue

        q.put( (nx, ny, dist+1) )
        is_visited[ny][nx] = True

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
#!/usr/bin/env python3

import queue

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

# direction vector
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]

# 訪れたかどうかの情報を持つ bool 値
is_visited = [ [False] * w for _ in range(h) ]

q = queue.Queue()

for x in range(w):
    for y in range(h):
        if a[y][x] == "#":
            q.put( (x, y, 0) )
            is_visited[y][x] = True

ans = 0

while not q.empty():
    # queue の先頭を取り出す
    x, y, dist = q.get()
    ans = max(ans, dist)
    # 4方向にループ
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0 or w <= nx or ny < 0 or h <= ny:
            continue

        if is_visited[ny][nx]:
            continue

        q.put( (nx, ny, dist+1) )
        is_visited[ny][nx] = True

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
#!/usr/bin/env python3

"""
Python の queue モジュールは遅いので使わない
deque を使おう!
"""

from collections import deque

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

# direction vector
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]

# 訪れたかどうかの情報を持つ bool 値
is_visited = [ [False] * w for _ in range(h) ]

q = deque()

for x in range(w):
    for y in range(h):
        if a[y][x] == "#":
            q.append( (x, y, 0) )
            is_visited[y][x] = True

ans = 0

while q:
    # queue の先頭を取り出す
    x, y, dist = q.popleft()
    is_visited[y][x] = True

    ans = max(ans, dist)
    # 4方向にループ
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0 or w <= nx or ny < 0 or h <= ny:
            continue
        # is_visited == True <=> そこは黒マス
        if is_visited[ny][nx]:
            continue

        q.append( (nx, ny, dist+1) )

print(ans)

Submission status: Time Limit Exceeded

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

F = [[False for w in range(W)] for h in range(H)]
blackList = []
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            F[h][w] = True
            blackList.append((h, w))

ans = -1
while blackList:
    #print('blackList: ', blackList)
    ans += 1
    nextBlack = []
    for (h, w) in blackList:
        if h-1 >= 0 and F[h-1][w] == False:
            F[h-1][w] = True
            nextBlack.append((h-1, w))
        if h+1 < H and F[h+1][w] == False:
            F[h+1][w] = True
            nextBlack.append((h+1, w))
        if w-1 >= 0 and F[h][w-1] == False:
            F[h][w-1] = True
            nextBlack.append((h, w-1))
        if w+1 < W and F[h][w+1] == False:
            F[h][w+1] = True
            nextBlack.append((h, w+1))
    #print('nextBlack: ', nextBlack)
    blackList = nextBlack

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = list(map(int,input().split()))
A = [list(str(input())) for i in range(H)]
 
black = []
 
cnt = 0
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
 
length = len(black)
            
while (length < H*W):
    gray = []
    for l in black:
        if l[1] != 0:
            c1 = [l[0],l[1]-1]
            if A[c1[0]][c1[1]] == ".":
                gray.append(c1)
                A[c1[0]][c1[1]] = "#"
        if l[1] != W-1:
            c2 = [l[0],l[1]+1]
            if  A[c2[0]][c2[1]] == ".":
                gray.append(c2)
                A[c2[0]][c2[1]] = "#"
        if l[0] != 0:
            c3 = [l[0]-1,l[1]]
            if  A[c3[0]][c3[1]] == ".":
                gray.append(c3)
                A[c3[0]][c3[1]] = "#"
        if l[0] != H-1:
            c4 = [l[0]+1,l[1]]
            if  A[c4[0]][c4[1]] == ".":
                gray.append(c4)
                A[c4[0]][c4[1]] = "#"
    
    black = [l for l in gray]
    
    cnt += 1
    length += len(black)
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


H,W=map(int, raw_input().split())
A=[ list( sys.stdin.readline().strip())  for i in range(H) ]


D=[ (-1,0),(1,0),(0,1),(0,-1) ]
K=[ [ float("inf") for j in range(W) ] for i in range(H)  ]  #Kyori

def bfs(h,w):
	q=deque()
	K[h][w]=0
	q.append( (h,w) )
	while q:
		h, w=q.popleft()	# newh , neww
		for dx,dy in D:
			if 0<=h+dx<H and 0<=w+dy<W:
				if A[h+dx][w+dy]=="." and K[h+dx][w+dy]>K[h][w]:
					K[h+dx][w+dy]=min( K[h+dx][w+dy], K[h][w]+1 )
					q.append( (h+dx,w+dy) )	


for i in range(H):
	for j in range(W):
		if A[i][j]=="#":
			bfs(i,j)

ans=0
for i in range(H):
	ans=max(ans , max(K[i]))

print ans

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W = map(int, input().split())
env = [list(map(int, list(input().replace('#', '0').replace('.', '1')))) for i in range(H)]
env = np.array(env)


cnt = 0
memo = [np.array(np.where(env==0)).T]
while True:

    if np.sum(env==0) == H*W:
        break
        
    memo_ = []
    for h, w in memo[cnt]:
        
        h_m = max(h-1, 0)
        h_p = min(h+1, H-1)
        w_m = max(w-1, 0)
        w_p = min(w+1, W-1)
        
        if env[h_m][w] == 1:
            env[h_m][w] = 0
            memo_.append([h_m, w])
            
        if env[h_p][w] == 1:
            env[h_p][w] = 0
            memo_.append([h_p, w])

        if env[h][w_m] == 1:
            env[h][w_m] = 0
            memo_.append([h, w_m])

        if env[h][w_p] == 1:
            env[h][w_p] = 0
            memo_.append([h, w_p])

        
    memo.append(memo_)
    cnt += 1
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    rem = H * W
    for i in range(H):
        l = A[i]
        for j in range(W):
            if l[j] == '#':
                queue.append((i+1, j+1, 0))

    ret = 0
    visited = [True] * ((W+2) * (H+2))
    for i in range(W+2):
        visited[i] = False
        visited[(W + 2) * (H + 1) + i] = False
    for i in range(H+2):
        visited[(W + 2) * i] = False
        visited[(W + 2) * i + (W + 1)] = False
    while queue:
        i, j, n = queue.popleft()
        k = i * (W + 2) + j
        if not visited[k]:
            continue
        visited[k] = False
        ret = n
        rem -= 1

        if rem == 0:
            break

        l0 = A[i-1]
        if visited[k - 1] and l0[j-2] == '.':
            queue.append((i, j - 1, n + 1))
        if visited[k + 1] and l0[j] == '.':
            queue.append((i, j + 1, n + 1))

        if visited[k - (W + 2)] and A[i-2][j-1] == '.':
            queue.append((i - 1, j, n + 1))
        if visited[k + (W + 2)] and A[i][j-1] == '.':
            queue.append((i + 1, j, n + 1))
    return ret


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]"
    result = solve(H, W, A)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    rem = H * W
    for i in range(H):
        l = A[i]
        for j in range(W):
            if l[j] == '#':
                queue.append((i+1, j+1, 0))

    ret = 0
    visited = [False] * ((W+2) * (H+2))
    for i in range(W+2):
        visited[i] = True
        visited[(W + 2) * (H + 1) + i] = True
    for i in range(H+2):
        visited[(W + 2) * i] = True
        visited[(W + 2) * i + (W + 1)] = True
    while queue:
        i, j, n = queue.popleft()
        k = i * (W + 2) + j
        if visited[k]:
            continue
        visited[k] = True
        ret = n
        rem -= 1

        if rem == 0:
            break
        if not visited[k - 1] and A[i-1][j-2] == '.':
            queue.append((i, j - 1, n + 1))
        if not visited[k + 1] and A[i-1][j] == '.':
            queue.append((i, j + 1, n + 1))
        if not visited[k - (W + 2)] and A[i-2][j-1] == '.':
            queue.append((i - 1, j, n + 1))
        if not visited[k + (W + 2)] and A[i][j-1] == '.':
            queue.append((i + 1, j, n + 1))
    return ret


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]"
    result = solve(H, W, A)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W = map(int, input().split())
env = [list(map(int, list(input().replace('#', '0').replace('.', '1')))) for i in range(H)]
env = np.array(env)


cnt = 0
memo = [np.array(np.where(env==0)).T]
while True:

    if np.sum(env==0) == H*W:
        break
        
    memo_ = []
    for h, w in memo[cnt]:
        
        if h-1 >= 0:
            if env[h-1][w] == 1:
                memo_.append([h-1, w])
                env[h-1][w] = 0
                
        if h+1 <= H-1:
            if env[h+1][w] == 1:
                memo_.append([h+1, w])
                env[h+1][w] = 0
            
        if w-1 >= 0:
            if env[h][w-1] == 1:
                memo_.append([h, w-1])
                env[h][w-1] = 0
            
        if w+1 <= W-1:
            if env[h][w+1] == 1:
                memo_.append([h, w+1])
                env[h][w+1] = 0
            
        
    memo.append(memo_)
    cnt += 1
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


H,W=map(int, raw_input().split())
A=[ list( sys.stdin.readline().strip())  for i in range(H) ]


D=[ (-1,0),(1,0),(0,1),(0,-1) ]
K=[ [ float("inf") for j in range(W) ] for i in range(H)  ]  #Kyori

def bfs(h,w):
	V=[ [ 0 for j in range(W) ] for i in range(H)  ]
	q=deque()
	V[h][w]=1
	K[h][w]=0
	q.append( (h,w) )
	while q:
		h, w=q.popleft()	# newh , neww
		for dx,dy in D:
			if 0<=h+dx<H and 0<=w+dy<W:
				if A[h+dx][w+dy]=="." and K[h+dx][w+dy]>K[h][w]:
					V[h+dx][w+dy]=1
					K[h+dx][w+dy]=min( K[h+dx][w+dy], K[h][w]+1 )
					q.append( (h+dx,w+dy) )	


for i in range(H):
	for j in range(W):
		if A[i][j]=="#":
			bfs(i,j)

ans=0
for i in range(H):
	ans=max(ans , max(K[i]))

print ans

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

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

    ret = 0
    visited = [False] * (W * H)
    while queue:
        i, j, n = queue.popleft()
        k = i * W + j
        if visited[k]:
            continue
        visited[k] = True
        ret = n
        rem -= 1

        if rem == 0:
            break
        if 0 < j and not visited[k - 1] and A[i][j-1] == '.':
            queue.append((i, j - 1, n + 1))
        if j < (W - 1) and not visited[k + 1] and A[i][j+1] == '.':
            queue.append((i, j + 1, n + 1))
        if 0 < i and not visited[k - W] and A[i-1][j] == '.':
            queue.append((i - 1, j, n + 1))
        if i < (H - 1) and not visited[k + W] and A[i+1][j] == '.':
            queue.append((i + 1, j, n + 1))
    return ret


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]"
    result = solve(H, W, A)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import time
import numpy as np

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

#print('mae:{}'.format(time.time() - start))

A = np.array([list(input()) for i in range(H)])

#print('imput:{}'.format(time.time() - start))

b_pos = []
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            b_pos.append(list((h,w)))
b_pos = np.array(b_pos)

#print(time.time() - start)
max_dist = 0
for h in range(H):
    for w in range(W):
        dist = np.amin(np.sum(np.abs(b_pos - (h,w)),axis=1))
        if dist > max_dist:
            max_dist = dist
print(max_dist)

#print('end:{}'.format(time.time() - start))

Submission status: Time Limit Exceeded

Solution code:
import queue as qu
import numpy as np
import functools as ft

words = lambda t : np.array(list(map(t, input().split())))

h,w = words(int)
mat = []
for _ in range(h):
    a = np.array(list(input()))
    mat.append(a)

mat = np.array(mat)
#print(mat)

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

def putL(x, y, next):
    if x != 0 and mat[x-1][y] != "#":
        next.append((x-1,y))
        mat[x-1][y] = "#"
    if y != 0 and mat[x][y-1] != "#":
        next.append((x,y-1))
        mat[x][y-1] = "#"
    if x != h-1 and mat[x+1][y] != "#":
        next.append((x+1,y))
        mat[x+1][y] = "#"
    if y != w-1 and mat[x][y+1] != "#":
        next.append((x,y+1))
        mat[x][y+1] = "#"

round = -1
while not len(prev) == 0:
    #print(prev)
    #print(mat)
    round += 1
    next = []
    for (x,y) in prev:
        putL(x, y, next)

    prev = next

print(round)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math

h, w = map(int, input().split())
A=[]

for i in range(0,h):
    A.append(list(str(x) for x in input()))

A = np.array(A)

B1 = np.where(A == "#")
B1 = np.array([B1[0], B1[1]]).T

B2 = np.where(A == ".")
B2 = np.array([B2[0], B2[1]]).T

B3=B2[B2[:,0]==0]
B3=np.append(B3,B2[B2[:,0]==h-1],axis=0)
B3=np.append(B3,B2[B2[:,1]==0],axis=0)
B3=np.append(B3,B2[B2[:,1]==w-1],axis=0)

B3 = list(map(list, set(map(tuple, B3))))

C1=np.zeros(len(B1))
C2=np.zeros(len(B3))

for i in range(0,len(B1)):
    temp=[]
    for j in range(0,i):
        temp.append(math.ceil(sum(np.abs(B1[i]-B1[j]))/2))
        C1[i]=min(temp)
        
for i in range(0, len(B3)):
    temp=[]
    for j in range(0,len(B1)):
        temp.append(sum(np.abs(B3[i]-B1[j])))
        C2[i]=min(temp)
        
C3= np.insert(C1,0,C2)

print(int(max(C3)))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

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

    ret = 0
    visited = [False] * (W * H)
    while queue:
        i, j, n = queue.popleft()
        k = i * W + j
        if visited[k]:
            continue
        visited[k] = True
        ret = n
        rem -= 1

        if rem == 0:
            break
        if 0 < j and not visited[k - 1] and A[i][j-1] == '.':
            queue.append((i, j - 1, n + 1))
        if j < (W - 1) and not visited[k + 1] and A[i][j+1] == '.':
            queue.append((i, j + 1, n + 1))
        if 0 < i and not visited[k - W] and A[i-1][j] == '.':
            queue.append((i - 1, j, n + 1))
        if i < (H - 1) and not visited[k + W] and A[i+1][j] == '.':
            queue.append((i + 1, j, n + 1))
    return ret


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]"
    result = solve(H, W, A)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    rem = H * W
    visited = [False] * (W * H)
    for i in range(H):
        l = A[i]
        for j in range(W):
            if l[j] == '#':
                queue.append((i, j, 0))
                k = i * W + j
                visited[k] = True
    ret = 0
    while queue:
        i, j, n = queue.popleft()
        k = i * W + j
        if visited[k] and 0 < n:
            continue
        visited[k] = True
        ret = n
        rem -= 1

        if rem == 0:
            break
        if 0 < j and not visited[k - 1]:
            queue.append((i, j - 1, n + 1))
        if j < (W - 1) and not visited[k + 1]:
            queue.append((i, j + 1, n + 1))
        if 0 < i and not visited[k - W]:
            queue.append((i - 1, j, n + 1))
        if i < (H - 1) and not visited[k + W]:
            queue.append((i + 1, j, n + 1))
    return ret


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]"
    result = solve(H, W, A)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

white = []
black = []

cnt = 0

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

length = len(black)
            
while (length < H*W):
    gray = []
    for l in black:
        if l[1] != 0:
            c1 = [l[0],l[1]-1]
            if A[c1[0]][c1[1]] == ".":
                gray.append(c1)
                A[c1[0]][c1[1]] = "#"
        if l[1] != W-1:
            c2 = [l[0],l[1]+1]
            if  A[c2[0]][c2[1]] == ".":
                gray.append(c2)
                A[c2[0]][c2[1]] = "#"
        if l[0] != 0:
            c3 = [l[0]-1,l[1]]
            if  A[c3[0]][c3[1]] == ".":
                gray.append(c3)
                A[c3[0]][c3[1]] = "#"
        if l[0] != H-1:
            c4 = [l[0]+1,l[1]]
            if  A[c4[0]][c4[1]] == ".":
                gray.append(c4)
                A[c4[0]][c4[1]] = "#"
    
    gray = list(map(list, set(map(tuple, gray))))
    black = [l for l in gray]
    
    cnt += 1
    length += len(black)
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
H, W, *A = sys.stdin.read().split()
H = int(H); W = int(W)

rW = range(W)
rrW = range(W-1, -1, -1)
rH = range(H)

INF = 2000
dist = [[INF]*W for i in rH]
for di, Ai in zip(dist, A):
    for j, a in enumerate(Ai):
        if a == '#':
            di[j] = 0
for di in dist:
    cur = INF
    for j in rW:
        if not di[j]:
            cur = -j
        else:
            di[j] = cur+j
    cur = INF
    for j in rrW:
        if not di[j]:
            cur = j
        elif cur-j < di[j]:
            di[j] = cur-j
for j in rW:
    cur = INF
    for di in dist:
        if cur+1 < di[j]:
            di[j] = cur = cur+1
        else:
            cur = di[j]
    cur = INF
    for di in reversed(dist):
        if cur+1 < di[j]:
            di[j] = cur = cur+1
        else:
            cur = di[j]
sys.stdout.write("%d\n" % max(max(di) for di in dist))

Submission status: Time Limit Exceeded

Solution code:
import queue

H, W = map(int, input().split())
A = []
dist = []
black = []
for i in range(H):
    A.append(list(input()))
    dist.append([])
    for j in range(W):
        dist[i].append([1000000, False])
        if A[i][j] == '#':
            black.append([i, j])

q = queue.Queue(maxsize=-1)
for b in black:
    q.put(b)

max_dist = 0
while not q.empty():
    item = q.get()
    if i < 0 or j < 0 or i > H - 1 or j > W - 1:
        continue
    if A[item[0]][item[1]] == '#':
        dist[item[0]][item[1]][0] = 0
    else:
        a = dist[item[0] - 1][item[1]][0] if item[0] > 0 else 1000000
        b = dist[item[0]][item[1] - 1][0] if item[1] > 0 else 1000000
        c = dist[item[0] + 1][item[1]][0] if item[0] < H - 1 else 1000000
        d = dist[item[0]][item[1] + 1][0] if item[1] < W - 1 else 1000000
        dist[item[0]][item[1]][0] = min(a, b, c, d) + 1
        if dist[item[0]][item[1]][0] > max_dist:
            max_dist = dist[item[0]][item[1]][0]

    if item[0] > 0 and not dist[item[0] - 1][item[1]][1]:
        q.put([item[0] - 1, item[1]])
        dist[item[0] - 1][item[1]][1] = True
    if item[1] > 0 and not dist[item[0]][item[1] - 1][1]:
        q.put([item[0], item[1] - 1])
        dist[item[0]][item[1] - 1][1] = True
    if item[0] < H - 1 and not dist[item[0] + 1][item[1]][1]:
        q.put([item[0] + 1, item[1]])
        dist[item[0] + 1][item[1]][1] = True
    if item[1] < W - 1 and not dist[item[0]][item[1] + 1][1]:
        q.put([item[0], item[1] + 1])
        dist[item[0]][item[1] + 1][1] = True

print(max_dist)

Submission status: Time Limit Exceeded

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

grid = [[True] * (w + 2)]
for _ in range(h):
    grid.append([True] + [x == '#' for x in input()] + [True])
grid.append([True] * (w + 2))

q = []

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if grid[i][j] is True:
            q.append((i, j))

cnt = 0
while q:
    qq = []
    for i, j in q:
        if not grid[i + 1][j]:
            grid[i + 1][j] = True
            qq.append((i + 1, j))
        if not grid[i - 1][j]:
            grid[i - 1][j] = True
            qq.append((i - 1, j))
        if not grid[i][j + 1]:
            grid[i][j + 1] = True
            qq.append((i, j + 1))
        if not grid[i][j - 1]:
            grid[i][j - 1] = True
            qq.append((i, j - 1))

    cnt += 1
    q = qq

print(cnt - 1)

Submission status: Time Limit Exceeded

Solution code:
import copy
H,W = map(int, input().split())
A = [list(map(str,list(input()))) for i in range(H)]
count = 0
while A != [["#" for i in range(W)] for j in range(H)]:
    tmp = copy.deepcopy(A)
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                if j > 0:
                    if A[i][j-1] == ".":
                        tmp[i][j-1] = "#"
                if j < W-1:
                    if A[i][j+1] == ".":
                        tmp[i][j+1] = "#"
                if i > 0:
                    if A[i-1][j] == ".":
                        tmp[i-1][j] = "#"
                if i < H-1:
                    if A[i+1][j] == ".":
                        tmp[i+1][j] = "#"
    A = tmp
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
a = ['#'*(w+2)]+['#'+input()+'#' for _ in range(h)]+['#'*(w+2)]
ans = 0
queue = []
for i in range(1,h+1):
    for j in range(1,w+1):
        if a[i][j]=='#':
            queue.append([i,j])
from collections import deque
queue = deque(queue)
while len(queue):
    l = []
    for _ in range(len(queue)):
        q = queue.pop()
        if q[0]>1 and a[q[0]-1][q[1]]=='.':
            l.append([q[0]-1,q[1]])
        if q[1]>1 and a[q[0]][q[1]-1]=='.':
            l.append([q[0],q[1]-1])
        if q[0]<h and a[q[0]+1][q[1]]=='.':
            l.append([q[0]+1,q[1]])
        if q[1]<w and a[q[0]][q[1]+1]=='.':
            l.append([q[0],q[1]+1])
        a[q[0]-1] = a[q[0]-1][:q[1]]+'#'+a[q[0]-1][q[1]+1:]
        a[q[0]] = a[q[0]][:q[1]-1]+'###'+a[q[0]][q[1]+2:]
        a[q[0]+1] = a[q[0]+1][:q[1]]+'#'+a[q[0]+1][q[1]+1:]
    queue = deque(l)
    ans += 1
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def inside(x, l, r):
    return l <= x < r


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

rest = H * W
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            rest -= 1
            qu.append((i, j))

ans = 0
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
while True:
    if rest == 0:
        break
    ans += 1
    qu2 = deque()
    while qu:
        i0, j0 = qu.popleft()
        for k in range(4):
            ni = i0 + dx[k]
            nj = j0 + dy[k]
            if not (inside(ni, 0, H) and inside(nj, 0, W)):
                continue
            if A[ni][nj] == '.':
                A[ni][nj] = '#'
                rest -= 1
                qu2.append((ni, nj))
    qu = qu2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

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

    ret = 0
    visited = [False] * (W * H)
    while queue:
        i, j, n = queue.popleft()
        k = i * W + j
        if visited[k]:
            continue
        visited[k] = True
        ret = n
        rem -= 1

        if rem == 0:
            break
        if 0 < j and not visited[k - 1]:
            queue.append((i, j - 1, n + 1))
        if j < (W - 1) and not visited[k + 1]:
            queue.append((i, j + 1, n + 1))
        if 0 < i and not visited[k - W]:
            queue.append((i - 1, j, n + 1))
        if i < (H - 1) and not visited[k + W]:
            queue.append((i + 1, j, n + 1))
    return ret


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]"
    result = solve(H, W, A)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# import queue
# from collections import deque

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

grid = [[True] * (w + 2)]
for _ in range(h):
    grid.append([True] + [x == '#' for x in input()] + [True])
grid.append([True] * (w + 2))

# q = deque()
q = []

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if grid[i][j] is True:
            q.append((i, j))

cnt = 0
while q:
    qq = []
    for (i, j) in q:
        # i, j = q.pop()
        if not grid[i + 1][j]:
            grid[i + 1][j] = True
            qq.append((i + 1, j))
        if not grid[i - 1][j]:
            grid[i - 1][j] = True
            qq.append((i - 1, j))
        if not grid[i][j + 1]:
            grid[i][j + 1] = True
            qq.append((i, j + 1))
        if not grid[i][j - 1]:
            grid[i][j - 1] = True
            qq.append((i, j - 1))

    cnt += 1
    q = qq

print(cnt - 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int,input().split())
coords = []
blacks = deque([])
for i in range(H):
    rows = list(input())
    coords.append(rows)
    for j,row in enumerate(rows):
        if row == "#":
            blacks.append((i,j,0))

ans = 0
while len(blacks) > 0: 
    h,w,dist = blacks.popleft()
    ans = max(dist,ans)
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni = h + di
        nj = w + dj
        if 0 <= ni < H and 0 <= nj < W:
            if coords[ni][nj] == ".":
                blacks.append((ni,nj,dist+1))
                coords[ni][nj] = "#"

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
a = ['#'*(w+2)]+['#'+input()+'#' for _ in range(h)]+['#'*(w+2)]
ans = 0
queue = []
for i in range(1,h+1):
    for j in range(1,w+1):
        if a[i][j]=='#':
            queue.append([i,j])
while True:
    if queue == []:
        break
    l = []
    for _ in range(len(queue)):
        q = queue.pop()
        if q[0]>1 and a[q[0]-1][q[1]]=='.':
            l.append([q[0]-1,q[1]])
        if q[1]>1 and a[q[0]][q[1]-1]=='.':
            l.append([q[0],q[1]-1])
        if q[0]<h and a[q[0]+1][q[1]]=='.':
            l.append([q[0]+1,q[1]])
        if q[1]<w and a[q[0]][q[1]+1]=='.':
            l.append([q[0],q[1]+1])
        a[q[0]-1] = a[q[0]-1][:q[1]]+'#'+a[q[0]-1][q[1]+1:]
        a[q[0]] = a[q[0]][:q[1]-1]+'###'+a[q[0]][q[1]+2:]
        a[q[0]+1] = a[q[0]+1][:q[1]]+'#'+a[q[0]+1][q[1]+1:]
    queue = l
    ans += 1
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
from time import time
from collections import deque

# reduce q.append()
# (constant-factor optimization)


def append(d, i, j):
    if not 0 <= i < H or not 0 <= j < W or dists[i][j] != -1:
        return
    dists[i][j] = d
    q.append((d, i, j))


q = deque()
H, W = map(int, input().split())
dists = [[-1] * W for _ in range(H)]
for i in range(H):
    for j, v in enumerate(input()):
        if v == "#":
            append(0, i, j)

while len(q):
    d, i, j = q.popleft()
    append(d+1, i-1, j)
    append(d+1, i+1, j)
    append(d+1, i, j-1)
    append(d+1, i, j+1)

# fast (0.01s)
ans = max(map(max, dists))
# very slow (4.2s)
# ans = max(sum(dists, []))

print(ans)