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())
A = [list(input()) for _ in range(H)]
sharps = []
for h, line in enumerate(A):
    for w, p in enumerate(line):
        if p == '#':
            A[h][w] = 1
            sharps.append([h, w, 0])
        else:
            A[h][w] = 0

q = deque(sharps)
while q:
    i, j, score = q.popleft()
    for mi, mj in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        ni = i + mi
        nj = j + mj
        if ni < 0 or H <= ni or nj < 0 or W <= nj or A[ni][nj] == 1:
            continue
        A[ni][nj] = 1
        q.append([ni, nj, score+1])
print(score)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
h,w = map(int, input().split())
al = [input() for _ in range(h)]

inf = 10**9
m = [[inf]*w for _ in range(h)]
q = deque([])
for hi in range(h):
    for wi in range(w):
        if al[hi][wi]=="#":
            m[hi][wi] = 0
            q.append((hi,wi))

while len(q)>0:
    ch,cw = q.popleft()
    c = m[ch][cw]
    for hi,wi in [[ch+1,cw],[ch,cw+1],[ch-1,cw],[ch,cw-1]]:
        if h>hi>=0 and w>wi>=0 and m[hi][wi]>c+1:
            m[hi][wi] = c+1
            q.append((hi,wi))

res = max([max(m[i]) for i in range(h)])
print(res)

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
input = sys.stdin.readline
from collections import deque
h,w=map(int,input().split())
grid=[]
for i in range(h):
	grid.append(input())
machines=deque()
visited=[[0 for i in range(w)] for j in range(h)]
for i in range(h):
	for j in range(w):
		if grid[i][j]=="#":
			machines.append((i,j))
			visited[i][j]=1

ans=0
while True:
	#print (visited)
	new=deque()
	ans+=1
	while len(machines)!=0:
		c = machines.popleft()
		if c[0]>0:
			if visited[c[0]-1][c[1]]==0:
				visited[c[0]-1][c[1]]=1
				new.append((c[0]-1,c[1]))
		if c[0]<h-1:
			if visited[c[0]+1][c[1]]==0:
				visited[c[0]+1][c[1]]=1
				new.append((c[0]+1,c[1]))
		if c[1]>0:
			if visited[c[0]][c[1]-1]==0:
				visited[c[0]][c[1]-1]=1
				new.append((c[0],c[1]-1))
		if c[1]<w-1:
			if visited[c[0]][c[1]+1]==0:
				visited[c[0]][c[1]+1]=1
				new.append((c[0],c[1]+1))
	if len(new)==0:
		break
	else:
		machines=copy.copy(new)
#print (visited)
print (ans-1)

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque
h,w=map(int,input().split())
grid=[]
for i in range(h):
	grid.append(input())
machines=deque()
visited=[[0 for i in range(w)] for j in range(h)]
for i in range(h):
	for j in range(w):
		if grid[i][j]=="#":
			machines.append((i,j))
			visited[i][j]=1

ans=0
while True:
	#print (visited)
	new=deque()
	ans+=1
	while len(machines)!=0:
		c = machines.popleft()
		if c[0]>0:
			if visited[c[0]-1][c[1]]==0:
				visited[c[0]-1][c[1]]=1
				new.append((c[0]-1,c[1]))
		if c[0]<h-1:
			if visited[c[0]+1][c[1]]==0:
				visited[c[0]+1][c[1]]=1
				new.append((c[0]+1,c[1]))
		if c[1]>0:
			if visited[c[0]][c[1]-1]==0:
				visited[c[0]][c[1]-1]=1
				new.append((c[0],c[1]-1))
		if c[1]<w-1:
			if visited[c[0]][c[1]+1]==0:
				visited[c[0]][c[1]+1]=1
				new.append((c[0],c[1]+1))
	if len(new)==0:
		break
	else:
		machines=copy.copy(new)
#print (visited)
print (ans-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
grid=[]
for i in range(h):
	grid.append(input())
machines=deque()
visited=[[0 for i in range(w)] for j in range(h)]
for i in range(h):
	for j in range(w):
		if grid[i][j]=="#":
			machines.append((i,j))
			visited[i][j]=1

ans=0
while True:
	#print (visited)
	new=[]
	ans+=1
	while len(machines)!=0:
		c = machines.popleft()
		if c[0]>0:
			if visited[c[0]-1][c[1]]==0:
				visited[c[0]-1][c[1]]=1
				new.append((c[0]-1,c[1]))
		if c[0]<h-1:
			if visited[c[0]+1][c[1]]==0:
				visited[c[0]+1][c[1]]=1
				new.append((c[0]+1,c[1]))
		if c[1]>0:
			if visited[c[0]][c[1]-1]==0:
				visited[c[0]][c[1]-1]=1
				new.append((c[0],c[1]-1))
		if c[1]<w-1:
			if visited[c[0]][c[1]+1]==0:
				visited[c[0]][c[1]+1]=1
				new.append((c[0],c[1]+1))
	if len(new)==0:
		break
	else:
		temp=[]
		for i in new:
			temp.append(i)
		for i in range(len(temp)):
			machines.append(temp[i])
#print (visited)
print (ans-1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int, input().split())
l=[]
d=[]
c=0
s=[[False for j in range(w)] for i in range(h)]
for i in range(h):
	l.append(list(input()))
for i in range(h):
	for j in range(w):
		if(l[i][j]=='#'):
			c+=1
			d.append((i,j))
			s[i][j]=True
count=0
g=0
while(True):
	if(c>=h*w):
		break
	k=len(d)
	f=False
	for i in range(g,k):
		a,b=d[i]
		if(a-1>=0 and not s[a-1][b]):
			d.append((a-1,b))
			s[a-1][b]=True
			c+=1
			f=True
		if(a+1<h and not s[a+1][b]):
			d.append((a+1,b))
			s[a+1][b]=True
			c+=1
			f=True
		if(b-1>=0 and not s[a][b-1]):
			d.append((a,b-1))
			s[a][b-1]=True
			c+=1
			f=True
		if(b+1<w and not s[a][b+1]):
			d.append((a,b+1))
			s[a][b+1]=True
			c+=1
			f=True
	g=k
	if(f):
		count+=1
	else:
		break
print(count)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int, input().split())
l=[]
d=[]
c=0
s=[[False for j in range(w)] for i in range(h)]
for i in range(h):
	l.append(list(input()))
for i in range(h):
	for j in range(w):
		if(l[i][j]=='#'):
			c+=1
			d.append((i,j))
			s[i][j]=True
count=0
while(len(d)!=0):
	if(c>=h*w):
		break
	k=len(d)
	f=False
	for i in range(k):
		a,b=d.pop(0)
		if(a-1>=0 and not s[a-1][b]):
			d.append((a-1,b))
			s[a-1][b]=True
			c+=1
			f=True
		if(a+1<h and not s[a+1][b]):
			d.append((a+1,b))
			s[a+1][b]=True
			c+=1
			f=True
		if(b-1>=0 and not s[a][b-1]):
			d.append((a,b-1))
			s[a][b-1]=True
			c+=1
			f=True
		if(b+1<w and not s[a][b+1]):
			d.append((a,b+1))
			s[a][b+1]=True
			c+=1
			f=True
	if(f):
		count+=1
	else:
		break
print(count)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int, raw_input().split())
l=[]
d=[]
c=0
s=[[False for j in range(w)] for i in range(h)]
for i in range(h):
	l.append(list(raw_input()))
for i in range(h):
	for j in range(w):
		if(l[i][j]=='#'):
			c+=1
			d.append((i,j))
			s[i][j]=True
count=0
while(len(d)!=0):
	if(c>=h*w):
		break
	k=len(d)
	f=False
	for i in range(k):
		a,b=d.pop(0)
		if(a-1>=0 and not s[a-1][b]):
			d.append((a-1,b))
			s[a-1][b]=True
			c+=1
			f=True
		if(a+1<h and not s[a+1][b]):
			d.append((a+1,b))
			s[a+1][b]=True
			c+=1
			f=True
		if(b-1>=0 and not s[a][b-1]):
			d.append((a,b-1))
			s[a][b-1]=True
			c+=1
			f=True
		if(b+1<w and not s[a][b+1]):
			d.append((a,b+1))
			s[a][b+1]=True
			c+=1
			f=True
	if(f):
		count+=1
print count

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int, input().split())
l=[]
d=[]
c=0
s=[[False for j in range(w)] for i in range(h)]
for i in range(h):
	l.append(list(input()))
for i in range(h):
	for j in range(w):
		if(l[i][j]=='#'):
			c+=1
			d.append((i,j))
			s[i][j]=True
count=0
while(len(d)!=0):
	if(c>=h*w):
		break
	k=len(d)
	f=False
	for i in range(k):
		a,b=d.pop(0)
		if(a-1>=0 and not s[a-1][b]):
			d.append((a-1,b))
			s[a-1][b]=True
			c+=1
			f=True
		if(a+1<h and not s[a+1][b]):
			d.append((a+1,b))
			s[a+1][b]=True
			c+=1
			f=True
		if(b-1>=0 and not s[a][b-1]):
			d.append((a,b-1))
			s[a][b-1]=True
			c+=1
			f=True
		if(b+1<w and not s[a][b+1]):
			d.append((a,b+1))
			s[a][b+1]=True
			c+=1
			f=True
	if(f):
		count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int, input().split())
l=[]
d=[]
c=0
s=[[False for j in range(w)] for i in range(h)]
for i in range(h):
	l.append(list(input()))
for i in range(h):
	for j in range(w):
		if(l[i][j]=='#'):
			c+=1
			d.append((i,j))
			s[i][j]=True
count=0
while(len(d)!=0):
	if(c>=h*w):
		break
	k=len(d)
	f=False
	for i in range(k):
		a,b=d.pop(0)
		if(a-1>=0 and s[a-1][b]==False):
			d.append((a-1,b))
			l[a-1][b]='#'
			s[a-1][b]=True
			c+=1
			f=True
		if(a+1<h and s[a+1][b]==False):
			d.append((a+1,b))
			l[a+1][b]='#'
			s[a+1][b]=True
			c+=1
			f=True
		if(b-1>=0 and s[a][b-1]==False):
			d.append((a,b-1))
			l[a][b-1]='#'
			s[a][b-1]=True
			c+=1
			f=True
		if(b+1<w and s[a][b+1]==False):
			d.append((a,b+1))
			l[a][b+1]='#'
			s[a][b+1]=True
			c+=1
			f=True
	if(f):
		count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
MP=[list(input())for i in range(h)]
kyori=[[[] for i in range(w)]for i in range(h)]
def bfs(a,b):
    dist=[[0]*w for i in range(h)]
    dist[b][a]=0
    q=deque([(a,b)])
    while q:
        a,b=q.popleft()
        da=[1,0,-1,0]
        db=[0,1,0,-1]
        dd=dist[b][a]
        for i in range(4):
            na=a+da[i]
            nb=b+db[i]
            if 0<=na and na<=w-1 and 0<=nb and nb<=h-1:
                if dist[nb][na]==0 and MP[nb][na]=='.':
                    dist[nb][na]=dd+1
                    kyori[nb][na].append(dd+1)
                    q.append((na,nb))
for i in range(h):
    for j in range(w):
        if MP[i][j]=='#':
            bfs(j,i)
ans=0
for i in range(h):
    for j in range(w):
        if MP[i][j]=='.':
            if kyori[j][i] !=[]:
                ans=max(ans, min(kyori[j][i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque 
H, W = map(int, input().split())
board = []
search_point = deque([])
min_distance_board = []
inf = 1000000000
for i in range(H):
    board.append(input())
    min_distance_board.append([inf if point == '.' else 0 for point in board[i]])
    for j in range(len(board[i])):
        if board[i][j] == '#': search_point.append([i, j, 0])

direction_list = [[1,0],[-1,0],[0,1],[0,-1]]
ans = 0
while search_point:
    now_point = search_point.popleft()
    for direction in direction_list:
        next_point = [now_point[0] + direction[0], now_point[1] + direction[1], now_point[2] + 1]
        if next_point[0] < 0 or next_point[0] >= H or next_point[1] < 0 or next_point[1] >= W \
        or min_distance_board[next_point[0]][next_point[1]] < inf:
            continue
        ans = max(next_point[2], ans)
        min_distance_board[next_point[0]][next_point[1]] = next_point[2]
        search_point.append(next_point)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())  # 迷路の縦、横の長さ
maze = [input() for iiii in range(H)]

# print(maze)
dist = [[-1] * W for iii in range(H)]  # スタートからの距離
check_que = deque()

for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            dist[i][j] = 0
            check_que.append((i, j))
# print(dist)


def bfs(check_que, dist):  # distを編集する関数
    #print("{},{}".format(tate, yoko))
    d = 0
    while check_que:

        h, w = check_que.popleft()
        d = dist[h][w]
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            h_prime, w_prime = h + dh, w + dw

            if 0 > h_prime or h_prime >= H or 0 > w_prime or w_prime >= W:
                continue
            if dist[h_prime][w_prime] == -1:
                dist[h_prime][w_prime] = d + 1
                check_que.append((h_prime, w_prime))

    return d


dis = bfs(check_que, dist)
# print(dist)
print(dis)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())  # 迷路の縦、横の長さ
maze = [input() for iiii in range(H)]

# print(maze)
dist = [[-1] * W for iii in range(H)]  # スタートからの距離
check_que = deque()
check_set = set()
for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            dist[i][j] = 0
            check_que.append((i, j))
            check_set.add((i, j))
# print(dist)


def bfs(check_que, dist, check_set):  # distを編集する関数
    #print("{},{}".format(tate, yoko))
    while check_que:

        h, w = check_que.popleft()
        d = dist[h][w]
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            h_prime, w_prime = h + dh, w + dw

            if 0 > h_prime or h_prime >= H or 0 > w_prime or w_prime >= W:
                continue
            if (h_prime, w_prime) not in check_set:
                dist[h_prime][w_prime] = d + 1
                check_que.append((h_prime, w_prime))
                check_set.add((h_prime, w_prime))

    return d


dis = bfs(check_que, dist, check_set)
# print(dist)
print(dis)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())  # 迷路の縦、横の長さ
maze = [input() for iiii in range(H)]

# print(maze)
dist = [[-1] * W for iii in range(H)]  # スタートからの距離
check_que = deque()

for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            dist[i][j] = 0
            check_que.append((i, j))
# print(dist)


def bfs(check_que,dist):  # distを編集する関数
    #print("{},{}".format(tate, yoko))
    while check_que:

        h, w = check_que.popleft()
        d = dist[h][w]
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            h_prime, w_prime = h + dh, w + dw

            if 0 > h_prime or h_prime >= H or 0 > w_prime or w_prime >= W:
                continue
            if dist[h_prime][w_prime] == -1:
                dist[h_prime][w_prime] = d + 1
                check_que.append((h_prime, w_prime))

    return d


dis = bfs(check_que,dist)
# print(dist)
print(dis)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())  # 迷路の縦、横の長さ
maze = [input() for iiii in range(H)]

# print(maze)
dist = [[-1] * W for iii in range(H)]  # スタートからの距離
check_que = deque()

for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            dist[i][j] = 0
            check_que.append((i, j))
# print(dist)


def bfs(initial_d):  # distを編集する関数
    #print("{},{}".format(tate, yoko))
    while check_que:

        h, w = check_que.popleft()
        d = dist[h][w]
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            h_prime, w_prime = h + dh, w + dw

            if 0 > h_prime or h_prime >= H or 0 > w_prime or w_prime >= W:
                continue
            if dist[h_prime][w_prime] == -1:
                dist[h_prime][w_prime] = d + 1
                check_que.append((h_prime, w_prime))

    return d


dis = bfs(0)
# print(dist)
print(dis)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())  # 迷路の縦、横の長さ
maze = []
for _ in range(H):
    maze.append(input())
# print(maze)
dist = [[-1] * W for iii in range(H)]  # スタートからの距離
check_que = deque()

for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            dist[i][j] = 0
            check_que.append((i, j))
# print(dist)


def bfs(initial_d):  # distを編集する関数
    #print("{},{}".format(tate, yoko))
    while check_que:

        h, w = check_que.popleft()
        d = dist[h][w]
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            h_prime, w_prime = h + dh, w + dw

            if 0 > h_prime or h_prime >= H or 0 > w_prime or w_prime >= W:
                continue
            if dist[h_prime][w_prime] == -1:
                dist[h_prime][w_prime] = d + 1
                check_que.append((h_prime, w_prime))

    return d


dis = bfs(0)
# print(dist)
print(dis)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())  # 迷路の縦、横の長さ
maze = []
for _ in range(H):
    maze.append(input())
# print(maze)
dist = [[-1] * W for iii in range(H)]  # スタートからの距離
check_que = deque()

d = 0

for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            dist[i][j] = 0
            check_que.append((i, j))
# print(dist)


def bfs(initial_d):  # distを編集する関数
    #print("{},{}".format(tate, yoko))
    while check_que:

        h, w = check_que.popleft()
        d = dist[h][w]
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            h_prime, w_prime = h + dh, w + dw

            if 0 <= h_prime <= H - 1 and 0 <= w_prime <= W - 1:
                if dist[h_prime][w_prime] == -1:
                    dist[h_prime][w_prime] = d + 1
                    check_que.append((h_prime, w_prime))

    return d


dis = bfs(0)
# print(dist)
print(dis)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())  # 迷路の縦、横の長さ
maze = []
for _ in range(H):
    maze.append(input())
# print(maze)
dist = [[-1] * W for iii in range(H)]  # スタートからの距離
check_que = deque()

d = 0

for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            dist[i][j] = 0
            check_que.append((i, j))
# print(dist)


def bfs(initial_d):  # distを編集する関数
    dis = 0
    #print("{},{}".format(tate, yoko))
    while check_que:

        h, w = check_que.popleft()
        d = dist[h][w]
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            h_prime, w_prime = h + dh, w + dw

            if 0 <= h_prime <= H - 1 and 0 <= w_prime <= W - 1:
                if dist[h_prime][w_prime] == -1:
                    dist[h_prime][w_prime] = d + 1
                    check_que.append((h_prime, w_prime))
                    if d + 1 > dis:
                        dis = d+1
    return dis


dis = bfs(0)
# print(dist)
print(dis)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())  # 迷路の縦、横の長さ
maze = []
for _ in range(H):
    maze.append(input())
# print(maze)
dist = [[-1] * W for iii in range(H)]  # スタートからの距離
check_que = deque()

d = 0

for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            dist[i][j] = 0
            check_que.append((i, j))
# print(dist)


def bfs(initial_d):  # distを編集する関数
    dis = 0
    #print("{},{}".format(tate, yoko))
    while len(check_que) != 0:

        h, w = check_que.popleft()
        d = dist[h][w]
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            h_prime, w_prime = h + dh, w + dw

            if 0 <= h_prime <= H - 1 and 0 <= w_prime <= W - 1:
                if dist[h_prime][w_prime] == -1:
                    dist[h_prime][w_prime] = d + 1
                    check_que.append((h_prime, w_prime))
                    if d + 1 > dis:
                        dis = d+1
    return dis


dis = bfs(0)
# print(dist)
print(dis)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = map(int,input().split())
s = [None]*h

for i in range(h):
    s[i] = input()

d = [[10000000 for i in range(w)] for j in range(h)]
sharp = 0

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

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            sx.append(j)
            sy.append(i)
            d[i][j] = 0
            
            
def bfs():
    que = deque()
    ans = 0
    for i in range(len(sx)):
        que.append([sy[i],sx[i]])
    
    while que:
        y,x = que.popleft()
        
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            
            if 0<=nx and nx<w and 0<=ny and ny<h and d[ny][nx] == 10000000:
                if d[ny][nx] > d[y][x]+1:
                    d[ny][nx] = d[y][x]+1
                    que.append([ny,nx])
                    
                    if d[ny][nx] > ans:
                        ans = d[ny][nx]
    
    print(ans)
        
bfs()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = map(int,input().split())
s = [None]*h

for i in range(h):
    s[i] = input()

d = [[10000000 for i in range(w)] for j in range(h)]
sharp = 0

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

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            sx.append(j)
            sy.append(i)
            d[i][j] = 0
            
            
def bfs():
    que = deque()
    for i in range(len(sx)):
        que.append([sy[i],sx[i]])
    
    while que:
        y,x = que.popleft()
        
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            
            if 0<=nx and nx<w and 0<=ny and ny<h and d[ny][nx] == 10000000:
                if d[ny][nx] > d[y][x]+1:
                    d[ny][nx] = d[y][x]+1
                    que.append([ny,nx])

    ans = 0
    for l in range(h):
        ans = max(max(d[l]) , ans)
    print(ans)
        
bfs()

Submission status: Time Limit Exceeded

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

H, W = map(int, input().split())
table = []
dist = [[-1]*W for i in range(H)]
Q = deque()
dx = [0,1,0,-1]
dy = [1,0,-1,0]
ans = 0

for y in range(H):
    A = list(input())
    for x in range(W):
        if A[x] == "#":
            Q.append((y,x))
            dist[y][x] = 0
    table.append(A)

while Q:
    y,x = Q.popleft()
    for i in range(4):
        ny = y+dy[i]
        nx = x+dx[i]
        if 0<=ny<H and 0<=nx<W and dist[ny][nx] == -1 and table[ny][nx] == ".":
            dist[ny][nx] = dist[y][x]+1
            Q.append((ny,nx))
for i in range(H):
    ans = max(ans,max(dist[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque
H,W=map(int, input().split())
A=[[-1]*W for _ in range(H)]
d=deque()
for h in range(H):
  s=input()
  for w in range(W):
    if s[w]=='.':
      pass
    else:
      A[h][w]=0
      d.append((h,w))

DIF=[(1,0),(0,1),(-1,0),(0,-1)]
while d:
  point=d.popleft()
  for dif in DIF:
    x=point[0]+dif[0]
    y=point[1]+dif[1]
    if 0<=x<H and 0<=y<W and A[x][y]==-1:
      d.append((x,y))
      A[x][y]=A[point[0]][point[1]]+1
ans=0    
for h in range(H):
  Amax=max(A[h])
  ans=max(ans,Amax)
#print(A)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
H,W=map(int, input().split())
A=[[-1]*W for _ in range(H)]
d=[]
for h in range(H):
  s=input()
  for w in range(W):
    if s[w]=='.':
      pass
    else:
      A[h][w]=0
      d.append((h,w))

cnt=1
DIF=[(1,0),(0,1),(-1,0),(0,-1)]
tmp=[]
while d:
  point=d.pop()
  for dif in DIF:
    x=point[0]+dif[0]
    y=point[1]+dif[1]
    if 0<=x<H and 0<=y<W and A[x][y]==-1:
      tmp.append((x,y))
      A[x][y]=cnt
  if not d:
    #print(tmp)
    d=copy.deepcopy(tmp)
    tmp=[]
    #print(d)
    cnt+=1
ans=0    
for h in range(H):
  Amax=max(A[h])
  ans=max(ans,Amax)
#print(A)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
def main():
  H,W=map(int, input().split())
  A=[]
  d=[]
  for h in range(H):
    a=[]
    s=input()
    for w in range(W):
      if s[w]=='.':
        a.append(-1)
      else:
        a.append(0)
        d.append((h,w))
    A.append(a)
  cnt=1
  DIF=[(1,0),(0,1),(-1,0),(0,-1)]
  tmp=[]
  while d:
    point=d.pop()
    for dif in DIF:
      x=point[0]+dif[0]
      y=point[1]+dif[1]
      if 0<=x<H and 0<=y<W and A[x][y]==-1:
        tmp.append((x,y))
        A[x][y]=cnt
    if not d:
      #print(tmp)
      d=copy.deepcopy(tmp)
      tmp=[]
      #print(d)
      cnt+=1
  ans=0    
  for h in range(H):
    Amax=max(A[h])
    ans=max(ans,Amax)
  #print(A)
  print(ans)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import copy
H,W=map(int, input().split())
A=[]
d=[]
for h in range(H):
  a=[]
  s=input()
  for w in range(W):
    if s[w]=='.':
      a.append(-1)
    else:
      a.append(0)
      d.append((h,w))
  A.append(a)
cnt=1
DIF=[(1,0),(0,1),(-1,0),(0,-1)]
tmp=[]
while d:
  point=d.pop()
  for dif in DIF:
    x=point[0]+dif[0]
    y=point[1]+dif[1]
    if 0<=x<H and 0<=y<W and A[x][y]==-1:
      tmp.append((x,y))
      A[x][y]=cnt
  if not d:
    #print(tmp)
    d=copy.deepcopy(tmp)
    tmp=[]
    #print(d)
    cnt+=1
ans=0    
for h in range(H):
  Amax=max(A[h])
  ans=max(ans,Amax)
#print(A)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
H,W=map(int, input().split())
A=[]
d=deque()
for h in range(H):
  a=[]
  s=input()
  for w in range(W):
    if s[w]=='.':
      a.append(-1)
    else:
      a.append(0)
      d.append((h,w))
  A.append(a)
cnt=1
DIF=[(1,0),(0,1),(-1,0),(0,-1)]
tmp=deque()
while d:
  point=d.popleft()
  for dif in DIF:
    x=point[0]+dif[0]
    y=point[1]+dif[1]
    if 0<=x<H and 0<=y<W and A[x][y]==-1:
      tmp.append((x,y))
      A[x][y]=cnt
  if not d:
    #print(tmp)
    d=copy.deepcopy(tmp)
    tmp=deque()
    #print(d)
    cnt+=1
ans=0    
for h in range(H):
  Amax=max(A[h])
  ans=max(ans,Amax)
#print(A)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
lis = set()
num = [[0] * w for i in range(h)]
s = [str(input()) for i in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            lis.add((i,j))
            num[i][j] = 1
cnt = -1
while lis != ():
    cnt += 1
    tmp = set()
    for x,y in lis:
        if x > 0:
            if num[x-1][y] == 0:
                num[x-1][y] = 1
                tmp.add((x-1,y))
        if x < h-1:
            if num[x+1][y] == 0:
                num[x+1][y] = 1
                tmp.add((x+1,y))
        if y > 0:
            if num[x][y-1] == 0:
                num[x][y-1] = 1
                tmp.add((x,y-1))
        if y < w-1:
            if num[x][y+1] == 0:
                num[x][y+1] = 1
                tmp.add((x,y+1))
    lis = tmp
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
lis = []
num = [[0] * w for i in range(h)]
s = [str(input()) for i in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            lis.append([i,j])
            num[i][j] = 1
cnt = -1
while lis != []:
    cnt += 1
    tmp = []
    for x,y in lis:
        if x > 0:
            if num[x-1][y] == 0:
                num[x-1][y] = 1
                tmp.append([x-1,y])
        if x < h-1:
            if num[x+1][y] == 0:
                num[x+1][y] = 1
                tmp.append([x+1,y])
        if y > 0:
            if num[x][y-1] == 0:
                num[x][y-1] = 1
                tmp.append([x,y-1])
        if y < w-1:
            if num[x][y+1] == 0:
                num[x][y+1] = 1
                tmp.append([x,y+1])
    lis = tmp
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
lis = []
s = [str(input()) for i in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            lis.append([i, j])
ans = 0
for i in range(h):
    for j in range(w):
        num = 10 ** 7
        for x, y in lis:
            num = min(num, abs(i - x) + abs(j - y))
        ans = max(ans, num)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from collections import deque


def solve(*args: str) -> str:
    h, w = map(int, args[0].split())
    A = [[c == '.' for c in s] for s in args[1:]]

    Q = deque()
    for y in range(h):
        for x in range(w):
            if not A[y][x]:
                Q.append((x, y, 0))

    ret = 0
    while Q:
        x, y, n = Q.popleft()

        ret = max(ret, n)
        if 0 < x and A[y][x-1]:
            Q.append((x-1, y, n+1))
            A[y][x-1] = False

        if x+1 < w and A[y][x+1]:
            Q.append((x+1, y, n+1))
            A[y][x+1] = False

        if 0 < y and A[y-1][x]:
            Q.append((x, y-1, n+1))
            A[y-1][x] = False

        if y+1 < h and A[y+1][x]:
            Q.append((x, y+1, n+1))
            A[y+1][x] = False

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from collections import deque


def solve(*args: str) -> str:
    h, w = map(int, args[0].split())
    A = [[c for c in s] for s in args[1:]]

    Q = deque()
    for y in range(h):
        for x in range(w):
            if A[y][x] == '#':
                A[y][x] = '.'
                Q.append((x, y, 0))

    ret = 0
    while Q:
        x, y, n = Q.popleft()
        if A[y][x] == '.':
            A[y][x] = '#'
            ret = max(ret, n)
            if 0 < x:
                Q.append((x-1, y, n+1))
            if x+1 < w:
                Q.append((x+1, y, n+1))
            if 0 < y:
                Q.append((x, y-1, n+1))
            if y+1 < h:
                Q.append((x, y+1, n+1))

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

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

q=deque()

#黒マスを探す
for w in range(W):
    for h in range(H):
        if A[h][w]=='#':
            q.append((h,w,0))

#BFS
ans=0
while q:
    h,w,d = q.popleft()
    ans=max(ans,d)
    for dh,dw in [(0,1),(1,0),(0,-1),(-1,0)]:
        nh,nw = h+dh, w+dw
        if nh<0 or nh>=H or nw<0 or nw>=W:
            continue
        if A[nh][nw]=='#':
            continue
        A[nh][nw]='#'
        q.append((nh,nw,d+1))

print(ans)

Submission status: Time Limit Exceeded

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

blacks=[]
whites=[]

#黒マス白マスをリストアップ
for w in range(W):
    for h in range(H):
        if A[h][w]=='#':
            blacks.append((h,w))
        else:
            whites.append((h,w))

ans=0
#各白マスについて黒マスとの最短距離を求め、その最大値を探す(マンハッタン距離)
for white in whites:
    dist=H+W+1
    for black in blacks:
        dist=min(dist,abs(black[0]-white[0])+abs(black[1]-white[1]))
    ans=max(ans,dist)

print(ans)