寻宝
难度:
标签:
题目描述
English description is not available for the problem. Please switch to Chinese.
代码结果
运行时间: 1592 ms, 内存: 46.6 MB
解释
方法:
本题解采用了广度优先搜索（BFS）、动态规划以及状态压缩的策略。首先，通过广度优先搜索确定地图中起点、石头堆、机关和终点的位置。其次，使用 BFS 确定石头堆到每个点的最短路径，并据此建立起点和所有机关点的距离矩阵。然后，使用状态压缩的动态规划策略，记录在达到所有机关的各种状态下，到达每个机关的最小步数。最后，通过另一次 BFS 计算从终点到其他所有点的最短距离，并结合动态规划的结果确定能否拿到宝藏，并计算最小步数。
时间复杂度:
O(O*M*N + 2^M * M^2 + M)
空间复杂度:
O(M*N + M*2^M)
代码细节讲解
🦆
为什么在构建机关点列表时需要将起点加入到机关列表中？这样的操作有什么特别的意义吗？
▷🦆
在使用BFS构建距离矩阵时，为什么要通过每个石堆计算并更新距离，直接从机关到机关计算不行吗？
▷🦆
动态规划中的状态压缩是如何定义的？每个位代表什么意义？
▷