lqb省赛日志[8/37]-[搜索·DFS·BFS]

本文主要是介绍lqb省赛日志[8/37]-[搜索·DFS·BFS]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一只小蒟蒻备考蓝桥杯的日志

文章目录

- 笔记
- - DFS
  - - 记忆化搜索
- 刷题
- 心得
- 小结

笔记

DFS

参考深度优先搜索(DFS) 总结(算法+剪枝+优化总结)
DFS的模板框架:

function dfs(当前状态){if(当前状态 == 目的状态){···}for(···寻找新状态){if(状态合法){vis[访问该点]；dfs(新状态);?是否需要恢复现场->vis[恢复访问]} }if(找不到新状态){···}
}

搜索要点：
状态控制：1. 初始状态 2. 递归产生的合法新状态 3. 目标状态
用一个数组存放产生的所有状态，存每一个状态
1.判断当前状态是否和前面的状态重复，如果重复则回到上一个状态，产生它的另一状态
2.判断当前状态是否为目标状态，如果是目标目标状态，则找到一个解答，根据实际问题需求，选择继续寻找答案或是直接返回。
3.如果数组为空，说明对于该问题无解。