Problem:


Score : 300 points

Problem Statement

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

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

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

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

Constraints

1 \leq H,W \leq 1000

A_{ij} is # or ..

The given grid has at least one black square.

Input

Input is given from Standard Input in the following format:

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

Output

Print the number of operations that will be performed.

Sample Input 1

3 3
...
.#.
...

Sample Output 1

2

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

Sample Input 2

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

Sample Output 2

3



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


Sample output:
2

Submission status: Time Limit Exceeded

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


def bfs():
    q = deque()
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '#':
                for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    nx = i + dx
                    ny = j + dy
                    if (0 <= nx < H) and (0 <= ny < W) and grid[nx][ny] != '#':
                        q.append((nx, ny))
    res = len(q)
    while (len(q)):
        np = q.popleft()
        grid[np[0]][np[1]] = '#'

    return res


res = 0
while (bfs()):
    res += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
H, W = map(int, input().split())
gridgraph = []
for line in sys.stdin.readlines():
    line = line.rstrip()
    gridgraph.append(line)

q = deque()
visited = [[False]*W for _ in range(H)]
ans = [[1e+9]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if gridgraph[i][j] == "#":
            q.append((i, j))
            visited[i][j] = True
            ans[i][j] = 0
while len(q):
    cy, cx = q.popleft()
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        if not (cy+dy >= 0 and H-1 >= cy+dy and cx+dx >= 0 and W-1 >= cx+dx):
            continue
        if visited[cy+dy][cx+dx]:
            continue
        visited[cy+dy][cx+dx] = True
        ans[cy+dy][cx+dx] = min(ans[cy+dy][cx+dx], ans[cy][cx]+1)
        q.append((cy+dy, cx+dx))

min_value = 0
for a in ans:
    min_value = max(min_value, max(a))
print(min_value)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
H, W = map(int, input().split())
gridgraph = []
for line in sys.stdin.readlines():
    line = line.rstrip()
    gridgraph.append(list(line))

q = deque()
visited = [[False]*W for _ in range(H)]
ans = [[1e+9]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if gridgraph[i][j] == "#":
            q.append((i, j))
            visited[i][j] = True
            ans[i][j] = 0
# for a, b in q:
#     print(a, b)
# exit()
while len(q):
    cy, cx = q.popleft()
    # print(cy, cx)
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        if not (cy+dy >= 0 and H-1 >= cy+dy and cx+dx >= 0 and W-1 >= cx+dx):
            continue
        if visited[cy+dy][cx+dx]:
            continue
        visited[cy+dy][cx+dx] = True
        ans[cy+dy][cx+dx] = min(ans[cy+dy][cx+dx], ans[cy][cx]+1)
        q.append((cy+dy, cx+dx))
    # print(ans)
    # exit()

min_value = 0
for a in ans:
    min_value = max(min_value, max(a))
print(min_value)

Submission status: Time Limit Exceeded

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

m=[[-1 for i in range(W+2)]]
mm=[[-1]+[0 for i in range(W)]+[-1] for j in range(H)]
m=m+mm+m

nexts=[]
for i in range(1, H+1):
  c=input()
  for j in range(1, W+1):
    if c[j-1]=='#':
      nexts.append([i, j])
      m[i][j]=1
      
def f(math, in_nexts):
  n=len(in_nexts)
  out_nexts=[]
  for i in range(n):
    x=in_nexts[i][0]
    y=in_nexts[i][1]
    if math[x-1][y]==0:
      math[x-1][y]=math[x][y]+1
      out_nexts.append([x-1, y])
    if math[x+1][y]==0:
      math[x+1][y]=math[x][y]+1
      out_nexts.append([x+1, y])
    if math[x][y-1]==0:
      math[x][y-1]=math[x][y]+1
      out_nexts.append([x, y-1])
    if math[x][y+1]==0:
      math[x][y+1]=math[x][y]+1
      out_nexts.append([x, y+1])
      
  return math, out_nexts

counter=0
while len(nexts)>0:
  m, nexts=f(m, nexts)
  counter+=1
  
print(counter-1)

Submission status: Time Limit Exceeded

Solution code:
def main():

    H, W = map(int, input().split())
    A = []
    white = 0
    h = []
    visited = set()
    for i in range(H):
        A.append(input())
        for j in range(W):
            if A[i][j] == '#':
                visited.add((i, j))
                h.append([i, j])
            else:
                white += 1

    cnt = 0
    mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while h and white > 0:
        temp = []
        cnt += 1
        for i, j in h:
            for di, dj in mv:
                i1, j1 = i+di, j+dj
                if 0<=i1<H and 0<=j1<W and (i1, j1) not in visited:
                    temp.append([i1, j1])
                    visited.add((i1, j1))
                    white -= 1
        h = temp
    return cnt

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
if sys.platform =='win32':
  sys.stdin=open('./input.txt')
input = sys.stdin.readline
def MAP(): return [int(x) for x in input().split()]

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

H, W = [int(s) for s in input().split()]

M = []

for i in range(H):
	M.append([s for s in input().rstrip()]) 

syx = []
for i in range(H):
	for j in range(W):
		if M[i][j] == '#': syx.append([i,j])
# print(syx)

dist = [[-1 for _ in range(W)] for _ in range(H)]
queue = deque()

for s in syx:
	dist[s[0]][s[1]] = 0

queue.append(syx)

while queue:
	nodelist = queue.popleft()
	# print(nodelist)
	nextnode = []

	for node in nodelist:
		y, x = node
		# print(y,x)
		
		for i in range(4):
			ny = y+dy[i]
			nx = x+dx[i]
			# print(ny, nx)
			
			if ny>=H or ny<0 or nx>=W or nx<0:
				continue
			if dist[ny][nx] != -1:
				continue
			
			if M[ny][nx] == '.':
				dist[ny][nx] = dist[y][x]+1
				nextnode.append([ny,nx])

	# print(nextnode)
	if nextnode:
		queue.append(nextnode)

ans = 0
for d in dist:
  ans = max(ans, max(d))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# AGC033A
# http://drken1215.hatenablog.com/entry/2019/05/05/223200
# を参考に解いた
# 多点スタートと考えて解く

from collections import deque
# 入力
H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]

# 4方向を定義
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

# BFSのためのデータ構造
dist = [[-1] * W for _ in range(H)]
que_x = deque()     # H
que_y = deque()     # W

# 多点スタート地点を決める
# スタート地点は0とする
for i in range(H):
    for k in range(W):
        if field[i][k] == "#":
            dist[i][k] = 0
            que_x.append(i)
            que_y.append(k)

# 多点スタート
# 0のところから順に1を増やしていく
# ex): 3地点a, b, cからスタートとすると
# aから周囲4箇所に1をつける -> bから周囲4箇所に1をつける -> cから周囲4箇所に1をつける
# aの周囲4箇所の内1点から周囲4箇所に2をつける -> aの周囲4箇所の内2点目から周囲4箇所に2をつける
# aの周囲4箇所が終われば次はbの周囲4箇所，それが終わればcの周囲4箇所
while que_x and que_y:
    x = que_x[0]
    y = que_y[0]
    que_x.popleft()
    que_y.popleft()
    for direct in range(4):
        nx = x + dx[direct]
        ny = y + dy[direct]
        if nx < 0 or H <= nx or ny < 0 or W <= ny:      # 場外はスルー
            continue
        if dist[nx][ny] == -1:      # まだ見ていない時
            que_x.append(nx)
            que_y.append(ny)
            dist[nx][ny] = dist[x][y] + 1       # 距離の更新

# distの最大値が答え (= 最も遠いところ)
tmp = [0] * H
for i in range(H):
    tmp[i] = max(dist[i])

print(max(tmp))

Submission status: Time Limit Exceeded

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

INF = float('inf')

d = [[INF] * W for _ in range(H)]


def bfs(i, j):
    q = deque()
    q.append((i, j))
    d[i][j] = 0

    while len(q):
        x, y = q.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy

            if (0 <= nx < H) and (0 <= ny < W) and d[nx][ny] > d[x][y] + 1:
                q.append((nx, ny))
                if grid[nx][ny] == '#':
                    d[nx][ny] = 0
                else:
                    d[nx][ny] = d[x][y] + 1


for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            bfs(i, j)
            break
    else:
        continue
    break

res = 0
for i in range(H):
    for j in range(W):
        res = max(res, d[i][j])

print(res)

Submission status: Time Limit Exceeded

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

INF = float('inf')

d = [[INF] * W for _ in range(H)]


def bfs(i, j):
    q = deque()
    q.append((i, j))
    d[i][j] = 0

    while len(q):
        x, y = q.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy

            if (0 <= nx < H) and (0 <= ny < W) and d[nx][ny] > d[x][y] + 1:
                q.append((nx, ny))
                d[nx][ny] = d[x][y] + 1


if H < W:
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '#':
                bfs(i, j)

    res = 0
    for i in range(H):
        for j in range(W):
            res = max(res, d[i][j])
else:
    for j in range(W):
        for i in range(H):
            if grid[i][j] == '#':
                bfs(i, j)

    res = 0
    for j in range(W):
        for i in range(H):
            res = max(res, d[i][j])


print(res)

Submission status: Time Limit Exceeded

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

INF = float('inf')

d = [[INF] * W for _ in range(H)]


def bfs(i, j):
    q = deque()
    q.append((i, j))
    d[i][j] = 0

    while len(q):
        x, y = q.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy

            if (0 <= nx < H) and (0 <= ny < W) and d[nx][ny] > d[x][y] + 1:
                q.append((nx, ny))
                d[nx][ny] = d[x][y] + 1


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

res = 0
for i in range(H):
    for j in range(W):
        res = max(res, d[i][j])

print(res)

Submission status: Time Limit Exceeded

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

INF = float('inf')
d = [[INF for _ in range(W)] for _ in range(H)]
# for i in range(H):
#     for j in range(W):
#         if grid[i][j] == '#':
#             d[i][j] = 0


def bfs(i, j):
    q = deque()
    q.append((i, j))
    d[i][j] = 0

    while len(q):
        x, y = q.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy

            if (0 <= nx < H) and (0 <= ny < W) and d[nx][ny] > d[x][y] + 1:
                q.append((nx, ny))
                d[nx][ny] = d[x][y] + 1


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

res = 0
for i in range(H):
    for j in range(W):
        res = max(res, d[i][j])

print(res)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
field=[]
new=False
black=[]
for i in range(h):
	b=[]
	a=input()
	for j in range(w):
		if a[j]=="#":
			b.append(1)
			black.append([i,j])
		else:
			b.append(0)
	field.append(b)
ans=0
while len(black):
	black_new=[]
	q=len(black)
	for k in range(q):
		i,j=black[k][0],black[k][1]
		if i!=0 and field[i-1][j]==False:
			field[i-1][j]=True
			black_new.append([i-1,j])
		if i!=h-1 and field[i+1][j]==False:
			field[i+1][j]=True
			black_new.append([i+1,j])
		if j!=0 and field[i][j-1]==False:
			field[i][j-1]=True
			black_new.append([i,j-1])
		if j!=w-1 and field[i][j+1]==False:
			field[i][j+1]=True
			black_new.append([i,j+1])
	black=black_new
	ans+=1
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
field=[]
new=False
black=[]
for i in range(h):
	b=[]
	a=input()
	for j in range(w):
		if a[j]=="#":
			b.append(1)
			new=True
			black.append([i,j])
		else:
			b.append(0)
	field.append(b)
ans=0
while new:
	p=0
	black_new=[]
	new=False
	black.sort()
	q=len(black)
	for k in range(q):
		i,j=black[k][0],black[k][1]
		if p>=q:
			break
		if [i,j]==black[p]:
			p+=1
			if i!=0 and field[i-1][j]==False:
				field[i-1][j]=True
				black_new.append([i-1,j])
				new=True
			if i!=h-1 and field[i+1][j]==False:
				field[i+1][j]=True
				black_new.append([i+1,j])
				new=True
			if j!=0 and field[i][j-1]==False:
				field[i][j-1]=True
				black_new.append([i,j-1])
				new=True
			if j!=w-1 and field[i][j+1]==False:
				field[i][j+1]=True
				black_new.append([i,j+1])
				new=True
	black=black_new
	ans+=1
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
field=[]
new=False
black=[]
for i in range(h):
	b=[]
	a=input()
	for j in range(w):
		if a[j]=="#":
			b.append(1)
			new=True
			black.append([i,j])
		else:
			b.append(0)
	field.append(b)
ans=0
while new:
	p=0
	black_new=[]
	new=False
	black.sort()
	q=len(black)
	for i in range(h):
		for j in range(w):
			if p>=q:
				break
			if [i,j]==black[p]:
				p+=1
				if i!=0 and field[i-1][j]==False:
					field[i-1][j]=True
					black_new.append([i-1,j])
					new=True
				if i!=h-1 and field[i+1][j]==False:
					field[i+1][j]=True
					black_new.append([i+1,j])
					new=True
				if j!=0 and field[i][j-1]==False:
					field[i][j-1]=True
					black_new.append([i,j-1])
					new=True
				if j!=w-1 and field[i][j+1]==False:
					field[i][j+1]=True
					black_new.append([i,j+1])
					new=True
	black=black_new
	ans+=1
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
field=[]
new=False
black=[]
for i in range(h):
	b=[]
	a=input()
	for j in range(w):
		if a[j]=="#":
			b.append(1)
			new=True
			black.append([i,j])
		else:
			b.append(0)
	field.append(b)
ans=0
while new:
	p=0
	black_new=[]
	new=False
	black.sort()
	for i in range(h):
		for j in range(w):
			if p>=len(black):
				break
			if [i,j]==black[p]:
				p+=1
				if i!=0 and field[i-1][j]==False:
					field[i-1][j]=True
					black_new.append([i-1,j])
					new=True
				if i!=h-1 and field[i+1][j]==False:
					field[i+1][j]=True
					black_new.append([i+1,j])
					new=True
				if j!=0 and field[i][j-1]==False:
					field[i][j-1]=True
					black_new.append([i,j-1])
					new=True
				if j!=w-1 and field[i][j+1]==False:
					field[i][j+1]=True
					black_new.append([i,j+1])
					new=True
	black=black_new
	ans+=1
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
field=[]
new=False
black=[]
for i in range(h):
	b=[]
	a=input()
	for j in range(w):
		if a[j]=="#":
			b.append(1)
			new=True
			black.append([i,j])
		else:
			b.append(0)
	field.append(b)
ans=0
while new:
	black_new=[]
	new=False
	for i in range(h):
		for j in range(w):
			if [i,j] in black:
				if i!=0 and field[i-1][j]==False:
					field[i-1][j]=True
					black_new.append([i-1,j])
					new=True
				if i!=h-1 and field[i+1][j]==False:
					field[i+1][j]=True
					black_new.append([i+1,j])
					new=True
				if j!=0 and field[i][j-1]==False:
					field[i][j-1]=True
					black_new.append([i,j-1])
					new=True
				if j!=w-1 and field[i][j+1]==False:
					field[i][j+1]=True
					black_new.append([i,j+1])
					new=True
	black=black_new
	ans+=1
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():

    h, w = map(int, input().split())
    a = ["#" * (w + 2)] + ["#" + input() + "#" for _ in range(h)] + ["#" * (w + 2)]

    d = [[-1] * (w + 2) for _ in range(h + 2)]

    def bfs():
        q = deque()
        for i in range(1, h + 1):
            for j in range(1, w + 1):
                if a[i][j] == "#":
                    q.append((j, i))
                    d[i][j] = 0

        dxy = (1, 0), (-1, 0), (0, 1), (0, -1)

        ans = 0
        while q:
            ux, uy = q.popleft()
            for dx, dy in dxy:
                vx = ux + dx
                vy = uy + dy
                if d[vy][vx] == -1 and a[vy][vx] == ".":
                    d[vy][vx] = d[uy][ux] + 1
                    ans = max(ans, d[vy][vx])
                    q.append((vx, vy))

        return ans

    ans = bfs()
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():

    h, w = map(int, input().split())
    a = ["#" * (w + 2)] + ["#" + input() + "#" for _ in range(h)] + ["#" * (w + 2)]

    d = [[-1] * (w + 2) for _ in range(h + 2)]

    def bfs():
        q = deque()
        for i in range(1, h + 1):
            for j in range(1, w + 1):
                if a[i][j] == "#":
                    q.append((j, i))
                    d[i][j] = 0

        dxy = (1, 0), (-1, 0), (0, 1), (0, -1)

        ans = 0
        while q:
            ux, uy = q.popleft()
            for dx, dy in dxy:
                vx = ux + dx
                vy = uy + dy
                if a[vy][vx] == "." and d[vy][vx] == -1:
                    d[vy][vx] = d[uy][ux] + 1
                    ans = max(ans, d[vy][vx])
                    q.append((vx, vy))

        return ans

    ans = bfs()
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():

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

    d = [[-1] * w for _ in range(h)]

    def bfs():
        q = deque()
        for i in range(h):
            for j in range(w):
                if a[i][j] == "#":
                    q.append((j, i))
                    d[i][j] = 0

        dxy = (1, 0), (-1, 0), (0, 1), (0, -1)

        ans = 0
        while q:
            ux, uy = q.popleft()
            for dx, dy in dxy:
                vx = ux + dx
                vy = uy + dy
                if 0 <= vx <= w - 1 and 0 <= vy <= h - 1 and a[vy][vx] == "." and d[vy][vx] == -1:
                    d[vy][vx] = d[uy][ux] + 1
                    ans = max(ans, d[vy][vx])
                    q.append((vx, vy))

        return ans

    ans = bfs()
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

d = [[-1] * w for _ in range(h)]


def bfs():
    q = deque()
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                q.append((j, i))
                d[i][j] = 0

    dxy = (1, 0), (-1, 0), (0, 1), (0, -1)

    ans = 0
    while q:
        ux, uy = q.popleft()
        for dx, dy in dxy:
            vx = ux + dx
            vy = uy + dy
            if 0 <= vx <= w - 1 and 0 <= vy <= h - 1 and a[vy][vx] == "." and d[vy][vx] == -1:
                d[vy][vx] = d[uy][ux] + 1
                ans = max(ans, d[vy][vx])
                q.append((vx, vy))

    return ans


ans = bfs()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

d = [[-1] * w for _ in range(h)]


def bfs():
    q = deque()
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                q.append((j, i))
                d[i][j] = 0

    dxy = [[1, 0], [-1, 0], [0, 1], [0, -1]]

    while q:
        ux, uy = q.popleft()
        for dx, dy in dxy:
            vx = ux + dx
            vy = uy + dy
            if 0 <= vx <= w - 1 and 0 <= vy <= h - 1 and a[vy][vx] == "." and d[vy][vx] == -1:
                d[vy][vx] = d[uy][ux] + 1
                q.append((vx, vy))


bfs()

ans = 0
for row in d:
    for e in row:
        ans = max(ans, e)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

d = [[-1] * w for _ in range(h)]


def bfs():
    s = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                s.append([j, i])

    q = deque()
    for sx, sy in s:
        q.append([sx, sy])
        d[sy][sx] = 0
    dxy = [[1, 0], [-1, 0], [0, 1], [0, -1]]

    while q:
        ux, uy = q.popleft()
        for dx, dy in dxy:
            vx = ux + dx
            vy = uy + dy
            if 0 <= vx <= w - 1 and 0 <= vy <= h - 1 and a[vy][vx] == "." and d[vy][vx] == -1:
                d[vy][vx] = d[uy][ux] + 1
                q.append([vx, vy])


bfs()

ans = 0
for row in d:
    for e in row:
        ans = max(ans, e)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W=map(int,input().split())
d={}
for i in range(H):    
    for j,c in enumerate(input()):
        d[(i,j)]=0 if c=='#' else -1
q=deque()
for s in d:
    if not d[s]:
        q.append(s)
while q:
    u=q.popleft()
    ui,uj=u
    for v in [(ui-1,uj),(ui+1,uj),(ui,uj-1),(ui,uj+1)]:
        vi,vj=v
        if 0<=vi<=H-1 and 0<=vj<=W-1 and d[v]==-1:
            d[v]=d[u]+1
            q.append(v)
print(max(d.values()))

Submission status: Time Limit Exceeded

Solution code:
#import pysnooper
#import numpy
#import os,re,sys,operator
from collections import Counter,deque
#from operator import itemgetter
#from itertools import accumulate,combinations,groupby,combinations_with_replacement,permutations
from sys import stdin,setrecursionlimit
#from bisect import bisect_left
#from copy import deepcopy
#import heapq
#import math
#import string
#from time import time
#from functools import lru_cache
setrecursionlimit(10**6)
input=stdin.readline

h,w=map(int,input().split())
a=[list(input()) for _ in range(h)]
d=[[False]*w for _ in range(h)]
dx=[1,-1,0,0]
dy=[0,0,1,-1]
q=deque()
nowi=[]
ans=0

for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            nowi.append((i,j))
            d[i][j]=True
q.append(nowi)
#print(nowi)
while len(q):
    nowq=q.popleft()
    nextq=[]
    #print(nowq)
    for i in nowq:
        ny,nx=i
        for yx in range(4):
            if ny+dy[yx]<0 or ny+dy[yx]>=h:
                continue
            if nx+dx[yx]<0 or nx+dx[yx]>=w:
                continue
            if d[ny+dy[yx]][nx+dx[yx]]:
                continue
            nextq.append((ny+dy[yx],nx+dx[yx]))
            d[ny+dy[yx]][nx+dx[yx]]=True
    if len(nextq):
        q.append(nextq)
        ans+=1
    #print(nextq)
print(ans)

Submission status: Time Limit Exceeded

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

field = [] # 白黒情報を持つリスト
mark = [] # 操作回数を保持するリスト
INF = 10**6

for i in range(h):
    field.append(list(input()))
    mark.append([0 for i in range(w)])

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

queue = deque()
for i in range(h):
    for j in range(w):
        if field[i][j] == "#":
            queue.append([i, j])

while len(queue) > 0:
    y, x = queue.popleft()
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= ny < h and 0 <= nx < w:
            if field[ny][nx] == ".":
                mark[ny][nx] = mark[y][x] + 1
                queue.append([ny, nx])
                field[ny][nx] = "#"

ans=0

for i in mark:
    ans = max(ans, max(i))

print(ans)

Submission status: Time Limit Exceeded

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

field=[]
m=[]
INF=10**6

for i in range(h):
    row=list(input())
    field.append(row)
    m.append([INF for i in range(w)])

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

queue=deque()
for i in range(h):
    for j in range(w):
        if field[i][j]=="#":
            m[i][j]=0
            queue.append([i,j])

while len(queue)>0:
    y,x=queue.popleft()
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=ny<h and 0<=nx<w:
            if m[ny][nx]>m[y][x]+1 and field[ny][nx]==".":
                m[ny][nx]=m[y][x]+1
                queue.append([ny,nx])
                field[ny][nx]="#"

ans=0

for i in range(h):
    ans=max(ans,max(m[i]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

field=[]
m=[]
INF=10**6

for i in range(h):
    row=list(input())
    field.append(row)
    m.append([INF for i in range(w)])

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

queue=[]
for i in range(h):
    for j in range(w):
        if field[i][j]=="#":
            m[i][j]=0
            queue.append([i,j])

while len(queue)>0:
    y,x=queue.pop(0)
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=ny<h and 0<=nx<w:
            if m[ny][nx]>m[y][x]+1 and field[ny][nx]==".":
                m[ny][nx]=m[y][x]+1
                queue.append([ny,nx])
                field[ny][nx]="#"

ans=0

for i in range(h):
    ans=max(ans,max(m[i]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

field=[]
m=[]
INF=10**6

for i in range(h):
    row=list(input())
    field.append(row)
    m.append([INF for i in range(w)])

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

queue=[]
for i in range(h):
    for j in range(w):
        if field[i][j]=="#":
            m[i][j]=0
            queue.append([i,j])

while len(queue)>0:
    y,x=queue.pop(0)
    field[y][x]="#"
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=ny<h and 0<=nx<w:
            if m[ny][nx]>m[y][x]+1 and field[ny][nx]==".":
                m[ny][nx]=m[y][x]+1
                queue.append([ny,nx])

ans=0

for i in range(h):
    ans=max(ans,max(m[i]))

print(ans)

Submission status: Time Limit Exceeded

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

field=[]
m=[]
INF=10**4

for i in range(h):
    row=list(input())
    field.append(row)
    m.append([INF for i in range(w)])

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

queue=[]
for i in range(h):
    for j in range(w):
        if field[i][j]=="#":
            m[i][j]=0
            queue.append([i,j])
while len(queue)>0:
    y,x=queue.pop(0)
    field[y][x]="#"
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=ny<h and 0<=nx<w:
            if m[ny][nx]>m[y][x]+1 and field[ny][nx]==".":
                m[ny][nx]=m[y][x]+1
                queue.append([ny,nx])

ans=0

for i in range(h):
    ans=max(ans,max(m[i]))

print(ans)

Submission status: Time Limit Exceeded

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

# coding: utf-8
# Your code here!
h,w=map(int,input().split())

field=[]
m=[]
INF=10**4

for i in range(h):
    row=list(input())
    field.append(row)
    m.append([INF for i in range(w)])

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

queue=[]
for i in range(h):
    for j in range(w):
        if field[i][j]=="#":
            m[i][j]=0
            queue.append([i,j])
while len(queue)>0:
    y,x=queue.pop(0)
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=ny<h and 0<=nx<w:
            if m[ny][nx]>m[y][x]+1 and field[ny][nx]==".":
                m[ny][nx]=m[y][x]+1
                queue.append([ny,nx])

ans=0

for i in range(h):
    ans=max(ans,max(m[i]))

print(ans)

Submission status: Time Limit Exceeded

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

# coding: utf-8
# Your code here!
h,w=map(int,input().split())

field=[]
m=[]
INF=10**4

for i in range(h):
    row=list(input())
    field.append(row)
    m.append([INF for i in range(w)])

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

for i in range(h):
    for j in range(w):
        if field[i][j]=="#":
            m[i][j]=0
            queue=[]
            queue.append([i,j])
            while len(queue)>0:
                y,x=queue.pop(0)
                for k in range(4):
                    nx=x+dx[k]
                    ny=y+dy[k]
                    if 0<=ny<h and 0<=nx<w:
                        if m[ny][nx]>m[y][x]+1 and field[ny][nx]==".":
                            m[ny][nx]=m[y][x]+1
                            queue.append([ny,nx])

ans=0

for i in range(h):
    ans=max(ans,max(m[i]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
q=deque()
l=[]
for i in range(h):
  l.append(list(input()))
lb=[[0 for i in range(w)] for j in range(h)]
for i in range(h):
  for j in range(w):
    if l[i][j]=="#":
      q.append([i,j])
move=[[1,0],[-1,0],[0,1],[0,-1]]
count=0
b=True
q2=deque()
while b:
  while q:
    q1=q.popleft()
    x1=q1[0]
    y1=q1[1]
    for i in range(4):
      dx=move[i][0]
      dy=move[i][1]
      x=x1+dx
      y=y1+dy
      if x<0 or x>h-1 or y<0 or y>w-1:
        pass
      elif l[x][y]=="#":
        pass
      else:
        l[x][y]="#"
        q2.append([x,y])
  if len(q2)!=0:
    q=q2
    q2=deque()
    count+=1
  else:
    b=False
print(count)

Submission status: Time Limit Exceeded

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

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

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


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

ans = 0
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)]
cnt = [[float('inf')]*w for _ in range(h)]
moves = ((0, 1), (0, -1), (1, 0), (-1, 0))

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

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

import numpy as np
for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      used = [[0]*w for _ in range(h)]
      bfs(i, j)

print(np.max(np.array(cnt)))