【Python刷题】广度优先搜索相关问题

题目描述

小A与小B

算法思路

小A一次移动一步，但有八个方向，小B一次移动两步，只有四个方向，要求小A和小B最早的相遇时间。用两个队列分别记录下小A和小B每一步可以走到的位置，通过一个简单的bfs就能找到这些位置并存到他们各自的队列中。在一个while循环中调用这个bfs函数，小A调用一次，小B调用两次。用一个矩阵v来标记小A和小B访问过的位置，一但发现其中一者当前走到的位置已经被另一者访问过就退出循环并且输出步数。否则就在bfs里将当前能到达的为止从队列中取出然后更新成下一步能到达的位置。如果最终两个队列都空了还是没能相遇就结束while循环然后返回-1

代码实现

import collections
# 读取迷宫的行数和列数
n, m = map(int, input().split())
# 初始化队列，q[0]用于存储小A的位置，q[1]用于存储小B的位置
q = [collections.deque() for i in range(2)]
# 初始化迷宫的矩阵，g[i][j]存储迷宫中(i, j)位置的字符
g = [[''] * m for i in range(n)]
# 初始化访问标记矩阵，v[0][i][j]和v[1][i][j]分别表示小A和小B是否访问过(i, j)位置
v = [[[0] * m for i in range(n)] for j in range(2)]
# 读取迷宫数据并初始化队列
for i in range(n):r = [x for x in input().split()]for j in range(m):# 如果当前位置是小A的位置，标记为已访问并将位置加入q[0]if r[j] == 'C':v[0][i][j] = 1q[0].append([i, j])# 如果当前位置是小B的位置，标记为已访问并将位置加入q[1]if r[j] == 'D':v[1][i][j] = 1q[1].append([i, j])# 存储当前位置的字符到迷宫矩阵g[i][j] = r[j]
# 定义小A的8个移动方向和小B的4个移动方向
dis = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]]
# 主函数，返回最早相遇的时间或-1（无法相遇）
def sol():ans = 0  # 初始化步数计数器while len(q[0]) or len(q[1]):  # 只要有一个队列不为空就继续循环ans += 1  # 每轮循环增加一步# 首先扩展小A的移动if bfs(0): return ans  # 如果小A和B相遇，返回当前步数# 然后扩展小B的第一次移动if bfs(1): return ans  # 如果小A和B相遇，返回当前步数# 最后扩展小B的第二次移动if bfs(1): return ans  # 如果小A和B相遇，返回当前步数return -1  # 如果没有相遇且队列为空，返回-1# 广度优先搜索函数，t=0表示小A，t=1表示小B
def bfs(t):for _ in range(len(q[t])):  # 遍历当前队列中的所有元素i, j = q[t].popleft()  # 取出队列中的一个点for k in range(4 if t else 8):  # 根据t的值选择4个方向（小B）或8个方向（小A）dx, dy = dis[k]  # 获取移动方向的坐标变化量x, y = i + dx, j + dy  # 计算新的坐标# 如果新坐标超出迷宫范围、已访问过或遇到障碍物，跳过if x < 0 or x >= n or y < 0 or y >= m or v[t][x][y] or g[x][y] == '#': continue# 如果新坐标已经被另一种类型的点访问过（小A和小B相遇），返回1if v[1 - t][x][y]: return 1v[t][x][y] = 1  # 标记新坐标为已访问q[t].append([x, y])  # 将新坐标加入队列，以便继续扩展return 0  # 如果当前队列中所有元素都扩展完毕且没有找到交集，返回0
# 调用主函数获取结果
ans = sol()
# 输出结果
if ans == -1:print('NO')  # 无法相遇
else:print('YES')  # 可以相遇print(ans)  # 输出最短相遇时间