洛谷P2196挖地雷(深搜与记忆化搜索)
发布时间
阅读量:
阅读量
深度优先搜索,记忆化搜索
本题关键点:
1、dp[k] 用于表示从k点出发进行搜索时,所能获取的最大地雷数目,数组dp初始值设定为-1,代表该位置尚未被访问过,同时具备类似vis数组的功能。
2、dfs(int x) 函数用于遍历x点所连接的所有相邻节点y,若dp[y]不等于-1,则说明y点尚未被处理过,此时需要递归调用dfs(y),否则直接返回dp[y]的值。
3、关于路径的输出问题,可以通过维护一个Next[k]数组来实现,其中Next[k]用于记录k点的下一个访问节点。在整个过程中持续更新该数组即可。
最终确定dp数组中数值最大的位置(假设为k点),然后依次通过Next数组追踪即可获得完整路径。
#include <cstdio>
#include <cstring>
全部评论 (0)
还没有任何评论哟~
