gov域名网站有哪些,长沙做网站美工的公司,海淀区城市建设档案馆网站,百度风云榜官网题目描述
小A与小B
算法思路
小A一次移动一步#xff0c;但有八个方向#xff0c;小B一次移动两步#xff0c;只有四个方向#xff0c;要求小A和小B最早的相遇时间。用两个队列分别记录下小A和小B每一步可以走到的位置#xff0c;通过一个简单的bfs就能找到这些位置并…
题目描述
小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# 广度优先搜索函数t0表示小At1表示小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个方向小Adx, 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) # 输出最短相遇时间
