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:
import copy

H, W = map(int, input().split())
A = [list('#' * (W + 2))]
for _ in range(H):
    a = input()
    A.append(list('#' + a + '#'))
A.append(list('#' * (W + 2)))
B = copy.deepcopy(A)
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

ans = 0
count = 0
while count < H * W:
    count = 0
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if A[i][j] == '#':
                count += 1
                for k in range(4):
                    B[i + dy[k]][j + dx[k]] = '#'
    ans += 1
    A = copy.deepcopy(B)

print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
import  math
import bisect
from collections import *
from operator import itemgetter
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

def bfs():
    d = [[[float("inf")] * w for _ in range(h)] for _ in range(len(kabe))]
    ans = float("inf")
    for i in range(len(kabe)):
        que = deque([])
        que.append((kabe[i][0], kabe[i][1]))
        d[i][kabe[i][0]][kabe[i][1]] = 0
        while que:
            x, y = que.popleft()
            for dx, dy in ([1, 0], [0, 1], [0, -1], [-1, 0]):
                nx = x + dx
                ny = y + dy
                if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[i][nx][ny] == float("inf"):
                    que.append((nx, ny))
                    d[i][nx][ny] = d[i][x][y] + 1
    li = []
    for i in range(h):
        for j in range(w):
            tmp = [d[k][i][j] for k in range(len(kabe))]
            li.append(min(tmp))
    return max(li)

h, w = na()
maze = [list(input()) for _ in range(h)]
kabe = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            kabe.append((i, j))
print(bfs())

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
import  math
import bisect
from statistics import *
from collections import *
from operator import itemgetter
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

def bfs():
    d = [[[float("inf")] * w for _ in range(h)] for _ in range(len(kabe))]
    ans = float("inf")
    for i in range(len(kabe)):
        que = deque([])
        que.append((kabe[i][0], kabe[i][1]))
        d[i][kabe[i][0]][kabe[i][1]] = 0
        while que:
            x, y = que.popleft()
            for dx, dy in ([1, 0], [0, 1], [0, -1], [-1, 0]):
                nx = x + dx
                ny = y + dy
                if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[i][nx][ny] == float("inf"):
                    que.append((nx, ny))
                    d[i][nx][ny] = d[i][x][y] + 1
    li = []
    for i in range(h):
        for j in range(w):
            tmp = [d[k][i][j] for k in range(len(kabe))]
            li.append(min(tmp))
    return max(li)

h, w = na()
maze = [list(input()) for _ in range(h)]
kabe = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            kabe.append((i, j))
print(bfs())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import itertools
#入力
h,w = map(int, input().split())
w = w + 2
maze = [list('#' * (w))]
for i in range(h):
    maze.append(list('#' + input() + '#')) #迷路の読み込み
maze.append(list('#' * (w)))
h = h + 2
                
distance = [[float('inf')] * w for i in range(h)] #まずは無限大の距離と仮定

start = []

for i in range(1,h-1):
    for j in range(1,w-1):
        if maze[i][j] == '#':
            start.append((i,j,0))

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

for t in range(len(start)):
    que = deque()
    que.append(start[t])
    
    while que:
        i,j,k = que.popleft() #先頭を取得
        for di,dj in move:
            if maze[i+di][j+dj] == '.' and distance[i+di][j+dj] > k+1:
            #迷路の道で，今までの距離が今出した距離より長いなら
                distance[i+di][j+dj] = k+1 #より短い今の距離に更新し
                que.append((i+di,j+dj,k+1)) #queの末尾に追加            

ans = itertools.chain(*distance)
ans = list(ans)
for i in range(len(ans)):
    if ans[i] == float('inf'):
        ans[i] = 0
        
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import itertools
#入力
h,w = map(int, input().split())
w = w + 2
maze = [list('#' * (w))]
for i in range(h):
    maze.append(list('#' + input() + '#')) #迷路の読み込み
maze.append(list('#' * (w)))
h = h + 2
                
distance = [[float('inf')] * w for i in range(h)] #まずは無限大の距離と仮定

start = []

for i in range(1,h-1):
    for j in range(1,w-1):
        if maze[i][j] == '#':
            start.append((i,j,0))

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

for t in range(len(start)):
    que = deque()
    que.append(start[t])
    
    while que:
        i,j,k = que.popleft() #先頭を取得
        for di,dj in move:
            if maze[i+di][j+dj] == '.' and distance[i+di][j+dj] > k+1:
            #迷路の道で，今までの距離が今出した距離より長いなら
                distance[i+di][j+dj] = k+1 #より短い今の距離に更新し
                que.append((i+di,j+dj,k+1)) #queの末尾に追加            

for i in range(h):
    for j in range(w):
        if maze[i][j] == '#':
            distance[i][j] = 0

ans = itertools.chain(*distance)
ans = list(ans)

print(max(ans))

Submission status: Time Limit Exceeded

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

def bfs(dp, q, i):
	if len(q[i]) == 0:
		return i - 1
	else:
		q.append([])

	while len(q[i]) > 0:

		cp = q[i].pop(0)
		np = [[cp[0]+1,cp[1]], [cp[0]-1,cp[1]], [cp[0],cp[1]+1], [cp[0],cp[1]-1]]

		for n in np:
			if 0 <= n[0] <= H-1 and 0 <= n[1] <= W-1:
				if dp[n[0]][n[1]] == inf:
					q[i+1].append(n)
					dp[n[0]][n[1]] = 0

	return bfs(dp,q,i+1)

inf = float("inf")

dp = [[inf if C[i][j] == "." else 0 for j in range(W)] for i in range(H)]

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

cnt = bfs(dp,q,0)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
s=set()
a=[]
from collections import deque
q=deque([])
for i in range(h):
    tmp=list(input())
    a.append(tmp)
    for j in range(w):
        if tmp[j]=="#":
            q.append((i,j,0))

ans=0
ll=[[0,1],[0,-1],[1,0],[-1,0]]
while q:
    x,y,v=q.popleft()
    ans=max(ans,v)
    for i,j in ll:
        if 0<=x+i<h and 0<=y+j<w and a[i+x][j+y]==".":
            a[i+x][j+y]="#"
            q.append((i+x,j+y,v+1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
s=set()
q=[]
for i in range(h):
    tmp=input()
    for j in range(w):
        if tmp[j]=="#":
            q.append((i,j))
            s.add((i,j))

ans=0
ll=[[0,1],[0,-1],[1,0],[-1,0]]
while q:
    l=[]
    for i,j in q:
        for x,y in ll:
            if i+x>=0 and i+x<h and j+y>=0 and j+y<w:
                if (i+x,j+y) not in s:
                    s.add((i+x,j+y))
                    l.append((i+x,j+y))
    q=l
    ans+=1

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
s=set()
from collections import deque
q=deque([])
for i in range(h):
    tmp=input()
    for j in range(w):
        if tmp[j]=="#":
            q.append((i,j))
            s.add((i,j))

ans=0
ll=[[0,1],[0,-1],[1,0],[-1,0]]
while q:
    l=[]
    while q:
        i,j=q.popleft()
        for x,y in ll:
            if i+x>=0 and i+x<h and j+y>=0 and j+y<w:
                if (i+x,j+y) not in s:
                    s.add((i+x,j+y))
                    l.append((i+x,j+y))
    q=deque(l)
    ans+=1

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
cnt = [[float('inf') for _ in range(w)] for _ in range(h)]
ans = 0
start = []
q = deque([])

def bfs():
  searched = [[0 for _ in range(w)] for _ in range(h)]
  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      if 0 <= y+dy < h and 0 <= x+dx < w and searched[y+dy][x+dx] == 0 and a[y+dy][x+dx] == '.' and cnt[y+dy][x+dx] > cnt[y][x]+1:
        searched[y+dy][x+dx] = 1
        q.append([y+dy, x+dx])
        cnt[y+dy][x+dx] = cnt[y][x]+1

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

bfs()
for i in range(h):
  for j in range(w):
    ans = max(ans, cnt[i][j])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
cnt = [[float('inf') for _ in range(w)] for _ in range(h)]
ans = 0
start = []
q = deque([])

def bfs():
  #q = deque([(y, x)])
  searched = [[0 for _ in range(w)] for _ in range(h)]
  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      if 0 <= y+dy < h and 0 <= x+dx < w and searched[y+dy][x+dx] == 0 and a[y+dy][x+dx] == '.' and cnt[y+dy][x+dx] > cnt[y][x]+1:
        searched[y+dy][x+dx] = 1
        q.append([y+dy, x+dx])
        cnt[y+dy][x+dx] = cnt[y][x]+1

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

#for i, j in start:
  #bfs(i, j)
bfs()
for i in range(h):
  for j in range(w):
    ans = max(ans, cnt[i][j])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
cnt = [[float('inf') for _ in range(w)] for _ in range(h)]
ans = 0
start = []

def bfs(y, x):
  q = deque([(y, x)])
  searched = [[0 for _ in range(w)] for _ in range(h)]
  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      if 0 <= y+dy < h and 0 <= x+dx < w and searched[y+dy][x+dx] == 0 and a[y+dy][x+dx] == '.' and cnt[y+dy][x+dx] > cnt[y][x]+1:
        searched[y+dy][x+dx] = 1
        q.append([y+dy, x+dx])
        cnt[y+dy][x+dx] = cnt[y][x]+1

for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      start.append([i, j])
      cnt[i][j] = 0
      
for i, j in start:
  bfs(i, j)

for i in range(h):
  for j in range(w):
    ans = max(ans, cnt[i][j])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
cnt = [[float('inf') for _ in range(w)] for _ in range(h)]
ans = 0
start = []

def bfs(y, x):
  q = deque([(y, x)])
  searched = [[0 for _ in range(w)] for _ in range(h)]
  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      if 0 <= y+dy < h and 0 <= x+dx < w and searched[y+dy][x+dx] == 0 and a[y+dy][x+dx] == '.':
        searched[y+dy][x+dx] = 1
        q.append([y+dy, x+dx])
        cnt[y+dy][x+dx] = min(cnt[y+dy][x+dx], cnt[y][x]+1)

for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      start.append([i, j])
      cnt[i][j] = 0
      
for i, j in start:
  bfs(i, j)

for i in range(h):
  for j in range(w):
    ans = max(ans, cnt[i][j])


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
cnt = [[float('inf') for _ in range(w)] for _ in range(h)]
ans = 0

def bfs(y, x):
  q = deque([(y, x)])
  searched = [[0 for _ in range(w)] for _ in range(h)]
  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      if 0 <= y+dy < h and 0 <= x+dx < w and searched[y+dy][x+dx] == 0 and a[y+dy][x+dx] == '.':
        #a[y+dy][x+dx] = '#'
        searched[y+dy][x+dx] = 1
        q.append([y+dy, x+dx])
        cnt[y+dy][x+dx] = min(cnt[y+dy][x+dx], cnt[y][x]+1)

for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      cnt[i][j] = 0
      
for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      bfs(i, j)

for i in range(h):
  for j in range(w):
    ans = max(ans, cnt[i][j])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(input())
    cur = []
    visited = dict()
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                cur.append([i, j])
                visited[(i, j)] = 1
            else:
                visited[(i, j)] = 0
    mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    count = 0
    while cur:
        temp = []
        for i, j in cur:
            for di, dj in mv:
                i1, j1 = i+di, j+dj
                if 0 <= i1 < H and 0 <= j1 < W and not visited[(i1, j1)]:
                    visited[(i1, j1)] = True
                    temp.append([i1, j1])
        if len(temp) > 0:
            count += 1
        cur = temp
    return count

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
import heapq
def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(input())
    cur = []
    visited = set()
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                heapq.heappush(cur, [0, i, j])
                visited.add((i, j))
    mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    max_c = float('-inf')
    while cur:
        c, i, j= heapq.heappop(cur)
        max_c = max(max_c, c)
        for di, dj in mv:
            i1, j1 = i+di, j+dj
            if (i1, j1) not in visited and 0 <= i1 < H and 0 <= j1 < W:
                visited.add((i1, j1))
                heapq.heappush(cur, [c+1, i1, j1])
    return max_c

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(input())
    cur = []
    visited = set()
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                cur.append([i, j])
                visited.add((i, j))
    mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    count = 0
    while cur:
        temp = []
        for i, j in cur:
            for di, dj in mv:
                i1, j1 = i+di, j+dj
                if (i1, j1) not in visited and 0 <= i1 < H and 0 <= j1 < W:
                    visited.add((i1, j1))
                    temp.append([i1, j1])
        if len(temp) > 0:
            count += 1
        cur = temp
    return count

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from collections import deque
from itertools import product
sys.setrecursionlimit(10**9)



def bfs(H,W,G,pos):
    todo=[pos]
    index=1
    dx,dy=[-1,1,0,0],[0,0,-1,1]
    depth=np.array([[0]*W for _ in range(H)])
    while True:
        x,y=pos

        for i in range(4):
            npos=(x+dx[i],y+dy[i])
            if 0<=npos[0]<W and 0<=npos[1]<H:
                if G[npos[1]][npos[0]]=="#":
                    return depth[y][x]+1

                if G[npos[1]][npos[0]]=="." and not npos in todo:
                    depth[npos[1]][npos[0]]=depth[y][x]+1
                    todo.append(npos)

        if index<len(todo):
            pos=todo[index]
            index+=1

def main():
    H,W=map(int,input().split())
    G=np.array([[""]*W for _ in range(H)])
    spos=[]
    black=0

    for y in range(H):
        A=input()
        for x in range(W):
            G[y][x]=A[x]
            if A[x]==".":
                spos.append((x,y))

    ans=0
    for pos in spos:
        ans=max(ans,bfs(H,W,G,pos))

    print(ans)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque
from itertools import product
sys.setrecursionlimit(10**9)

H,W=map(int,input().split())
G=[[""]*W for _ in range(H)]
spos=[]
black=0

for y in range(H):
    A=input()
    for x in range(W):
        G[y][x]=A[x]
        if A[x]==".":
            spos.append((x,y))


def bfs(pos):
    todo=[pos]
    index=1
    dx,dy=[-1,1,0,0],[0,0,-1,1]
    depth=[[0]*W for _ in range(H)]
    while True:
        x,y=pos

        for i in range(4):
            npos=(x+dx[i],y+dy[i])
            if 0<=npos[0]<W and 0<=npos[1]<H:
                if G[npos[1]][npos[0]]=="#":
                    return depth[y][x]+1

                if G[npos[1]][npos[0]]=="." and not npos in todo:
                    depth[npos[1]][npos[0]]=depth[y][x]+1
                    todo.append(npos)

        if index<len(todo):
            pos=todo[index]
            index+=1

ans=0
for pos in spos:
    ans=max(ans,bfs(pos))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
from itertools import product
sys.setrecursionlimit(10**9)

H,W=map(int,input().split())
G=[[""]*W for _ in range(H)]
sposes=[]
dx,dy=[-1,1,0,0],[0,0,-1,1]

for y in range(H):
    A=input()
    for x in range(W):
        G[y][x]=A[x]
        if A[x]=="#":
            spos=(x,y)
            sposes.append(spos)

def solve(poses,ans):
    todo=[]
    for pos in poses:
        if True:
            x,y=pos
            for i in range(4):
                npos=(x+dx[i],y+dy[i])
                if 0<=npos[0]<W and 0<=npos[1]<H:
                    if G[npos[1]][npos[0]]=="." and not npos in todo:
                        G[npos[1]][npos[0]]="#"
                        todo.append(npos)

    if len(todo)>0:
        ans+=1
    else:
        print(ans)
        exit()

    solve(todo,ans)


# print(sposes)
solve(sposes,0)
# print(G)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
a=[input() for _ in range(h)]
dxy=[(0,1),(1,0),(-1,0),(0,-1)]
inf=float("inf")

dp=[[inf]*w for _ in range(h)]
q=deque()

for y,l in enumerate(a):
    for x,c in enumerate(l):
        if c=="#":
            dp[y][x]=0
            q.append((x,y))
ans=0
while q:
    x,y=q.popleft()
    d=dp[y][x]
    for dx,dy in dxy:
        nx,ny=x+dx,y+dy
        if not 0<=nx<w: continue
        if not 0<=ny<h: continue
        if dp[ny][nx]<=d+1: continue
        dp[ny][nx]=d+1
        q.append((nx,ny))
        ans=max(ans,d+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
g=[list(input()) for _ in range(h)]
q=[]
r=[[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if g[i][j]=="#":
            g[i][j]=0
            r[i][j]=1
            q.append([i,j])
dx=[1,-1,0,0]
dy=[0,0,1,-1]
ans=0
while q:
    i,j=q.pop(0)
    for x,y in zip(dx,dy):
        if i+y<0 or i+y>=h or j+x<0 or j+x>=w:
            continue
        if r[i+y][j+x]:
            continue
        g[i+y][j+x]=g[i][j]+1
        r[i+y][j+x]+=1
        ans=max(ans,g[i+y][j+x])
        q.append([i+y,j+x])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
g=[list(input()) for _ in range(h)]
q=[]
r=[[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if g[i][j]=="#":
            g[i][j]=0
            r[i][j]=1
            q.append([i,j])
dx=[1,-1,0,0]
dy=[0,0,1,-1]
ans=0
while q:

    i,j=q.pop(0)
    for x,y in zip(dx,dy):
        if i+y<0 or i+y>=h or j+x<0 or j+x>=w:
            continue
        if r[i+y][j+x]:
            continue
        g[i+y][j+x]=g[i][j]+1
        r[i+y][j+x]+=1
        ans=max(ans,g[i+y][j+x])
        q.append([i+y,j+x])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
g=[list(input()) for _ in range(h)]
q=[]
r=[[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if g[i][j]=="#":
            g[i][j]=0
            r[i][j]=1
            q.append([i,j])
dx=[1,-1,0,0]
dy=[0,0,1,-1]
ans=0
while q:

    i,j=q.pop(0)
    for x,y in zip(dx,dy):
        if i+y<0 or i+y>=h or j+x<0 or j+x>=w:
            continue
        if r[i+y][j+x]:
            continue
        g[i+y][j+x]=g[i][j]+1
        r[i+y][j+x]+=1
        ans=max(ans,g[i+y][j+x])
        q.append([i+y,j+x])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = []
for i in range(H):
  A.append(list(map(int,input().replace(".", "0").replace("#", "1"))))
V = []
v = []
c = 0
for i in range(H):
  for j in range(W):
    if A[i][j] == 1:
      V.append([i, j])
for i in range(H+W):
  P = []
  if len(V) == H*W:
    break
  c += 1
  for v in V:
    if v not in P:
      P.append(v)
    if v[0]!=0 and [v[0]-1, v[1]] not in P:
      P.append([v[0]-1, v[1]])
    if v[1]!=0 and [v[0], v[1]-1] not in P:
      P.append([v[0], v[1]-1])
    if v[0]!=(H-1) and [v[0]+1, v[1]] not in P:
      P.append([v[0]+1, v[1]])
    if v[1]!=(W-1) and [v[0], v[1]+1] not in P:
      P.append([v[0], v[1]+1])
  V = P
print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    h, w = read_int(2)
    a = []
    for y in range(h):
        a.append(list(read_line(w)))
    return a


def read_int(n):
    return list(map(int, read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    white_tile = '.'
    black_tile = '#'

    w, h = get_area(a)
    invalid = w * h
    memo = [[invalid for x in range(w)] for y in range(h)]

    queue = deque()
    next_steps = [[1, 0], [-1, 0], [0, 1], [0, -1]]

    maximum_count = 0

    for y in range(h):
        for x in range(w):
            if a[y][x] == black_tile:
                queue.append((x, y, 0))

    while queue:
        x, y, d = queue.popleft()

        memo[y][x] = d

        for dx, dy in next_steps:
            nx, ny = x + dx, y + dy
            if not (0 <= nx < w and 0 <= ny < h):
                continue
            if memo[ny][nx] <= d + 1:
                continue
            if a[ny][nx] == black_tile:
                continue
            queue.append((nx, ny, d + 1))

    for y in range(h):
        maximum_count = max(maximum_count, max(memo[y]))
    return maximum_count


def get_area(a):
    w = len(a[0])
    h = len(a)
    return w, h


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    h, w = read_int(2)
    a = []
    for y in range(h):
        a.append(list(read_line(w)))
    return a


def read_int(n):
    return list(map(int, read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    white_tile = '.'
    black_tile = '#'

    w, h = get_area(a)
    invalid = w * h
    memo = [[invalid for x in range(w)] for y in range(h)]

    queue = deque()
    next_steps = [[1, 0], [-1, 0], [0, 1], [0, -1]]

    maximum_count = 0

    for y in range(h):
        for x in range(w):
            if a[y][x] == black_tile:
                queue.append((x, y, 0))

    while queue:
        x, y, d = queue.popleft()

        memo[y][x] = d
        maximum_count = max(maximum_count, d)

        for dx, dy in next_steps:
            nx, ny = x + dx, y + dy
            if not (0 <= nx < w and 0 <= ny < h):
                continue
            if memo[ny][nx] <= d + 1:
                continue
            queue.append((nx, ny, d + 1))

    return maximum_count


def get_area(a):
    w = len(a[0])
    h = len(a)
    return w, h


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    h, w = read_int(2)
    a = []
    for y in range(h):
        a.append(list(read_line(w)))
    return a


def read_int(n):
    return list(map(int, read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    white_tile = '.'
    black_tile = '#'

    w, h = get_area(a)
    invalid = w * h
    memo = [[invalid for x in range(w)] for y in range(h)]

    queue = deque()
    next_steps = [[1, 0], [-1, 0], [0, 1], [0, -1]]

    maximum_count = 0

    for y in range(h):
        for x in range(w):
            if a[y][x] == black_tile:
                queue.append((x, y, 0))

    while queue:
        x, y, d = queue.popleft()
        if memo[y][x] < d:
            continue
        memo[y][x] = d
        maximum_count = max(maximum_count, d)

        for dx, dy in next_steps:
            nx, ny = x + dx, y + dy
            if not (0 <= nx < w and 0 <= ny < h):
                continue
            queue.append((nx, ny, d + 1))

    return maximum_count


def get_area(a):
    w = len(a[0])
    h = len(a)
    return w, h


def collect_tiles(a, w, h, mark):
    tiles = []
    for y in range(h):
        for x in range(w):
            if a[y][x] == mark:
                tiles.append([x, y])
    return tiles


def get_minimum_distance(from_what, to_candidates):
    return min([abs(from_what[0] - x[0]) + abs(from_what[1] - x[1]) for x in to_candidates])


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    h, w = read_int(2)
    a = []
    for y in range(h):
        a.append(list(read_line(w)))
    return a


def read_int(n):
    return list(map(int, read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    white_tile = '.'
    black_tile = '#'

    w, h = get_area(a)
    invalid = w * h
    memo = [[invalid for x in range(w)] for y in range(h)]

    black_tiles = collect_tiles(a, w, h, black_tile)
    white_tiles = collect_tiles(a, w, h, white_tile)

    maximum_count = 0

    for w in white_tiles:
        maximum_count = max(maximum_count, get_minimum_distance(w, black_tiles))

    return maximum_count


def get_area(a):
    w = len(a[0])
    h = len(a)
    return w, h


def collect_tiles(a, w, h, mark):
    tiles = []
    for y in range(h):
        for x in range(w):
            if a[y][x] == mark:
                tiles.append([x, y])
    return tiles


def get_minimum_distance(from_what, to_candidates):
    return min([abs(from_what[0] - x[0]) + abs(from_what[1] - x[1]) for x in to_candidates])


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    h, w = read_int(2)
    a = []
    for y in range(h):
        a.append(list(read_line(w)))
    return a


def read_int(n):
    return list(map(int, read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    white_tile = '.'
    black_tile = '#'

    w, h = get_area(a)
    invalid = w * h
    memo = [[invalid for x in range(w)] for y in range(h)]

    black_tiles = collect_tiles(a, w, h, black_tile)
    white_tiles = collect_tiles(a, w, h, white_tile)

    maximum_count = 0

    for w in white_tiles:
        maximum_count = max(maximum_count, get_minimum_distance(w, black_tiles))

    return maximum_count


def get_area(a):
    w = len(a[0])
    h = len(a)
    return w, h


def collect_tiles(a, w, h, mark):
    tiles = []
    for y in range(h):
        for x in range(w):
            if a[y][x] == mark:
                tiles.append([x, y])
    return tiles


def get_minimum_distance(from_what, to_candidates):
    return min(list(map(lambda x: abs(x[0] - from_what[0]) + abs(x[1] - from_what[1]), to_candidates)))


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    h, w = read_int(2)
    a = []
    for y in range(h):
        a.append(list(read_line(w)))
    return a


def read_int(n):
    return list(map(int, read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    white_tile = '.'
    black_tile = '#'

    w, h = get_area(a)
    invalid = w * h
    memo = [[invalid for x in range(w)] for y in range(h)]
    black_tiles = collect_tiles(a, w, h, black_tile)
    queue = []

    for bx, by in black_tiles:
        queue.append([bx, by, 0])

    while queue:
        x, y, d = queue.pop(0)
        if not (0 <= x < w and 0 <= y < h and memo[y][x] > d):
            continue

        memo[y][x] = d
        queue.append([x + 1, y, d + 1])
        queue.append([x - 1, y, d + 1])
        queue.append([x, y + 1, d + 1])
        queue.append([x, y - 1, d + 1])

    maximum_count = 0
    for y in range(h):
        maximum_count = max(maximum_count, max(memo[y]))

    return maximum_count


def get_area(a):
    w = len(a[0])
    h = len(a)
    return w, h


def collect_tiles(a, w, h, mark):
    tiles = []
    for y in range(h):
        for x in range(w):
            if a[y][x] == mark:
                tiles.append([x, y])
    return tiles


def write(result):
    print(result)


if __name__ == '__main__':
    solve()