Advertisement

洛谷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)

还没有任何评论哟~