牛客 23486 小A与小B
方法1:BFS
from collections import deque
from typing import List
def bfs(pos: tuple, direction: int) -> List[List[int]]:
ans = [[MAX] * M for _ in range(N)]
vis = [[False] * M for _ in range(N)]
queue = deque(); queue.append((pos, 0)); vis[pos[0]][pos[1]] = True
while queue:
(x, y), time = queue.popleft(); ans[x][y] = time
for i in range(direction):
dx, dy = x + directions[i][0], y + directions[i][1]
if 0 <= dx < N and 0 <= dy < M and maze[dx][dy] != '#' and not vis[dx][dy]:
queue.append(((dx, dy), time + 1)); vis[dx][dy] = True
return ans
MAX = 10 ** 6
directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
N, M = map(int, input().split())
maze = [list(input().split()) for _ in range(N)]
posA, posB = (0, 0), (0, 0)
for i in range(N):
for j in range(M):
if maze[i][j] == 'C':
posA = (i, j)
elif maze[i][j] == 'D':
posB = (i, j)
ans1, ans2, res = bfs(posA, 8), bfs(posB, 4), MAX
for i in range(N):
for j in range(M):
res = min(res, max(ans1[i][j], (ans2[i][j] + 1) // 2))
print("NO" if res == MAX else "YES\n" + str(res))
标签:系列,vis,List,pos,queue,牛客,001,range
From: https://www.cnblogs.com/XuGui/p/18331175