[何为 DFS]
深度优先搜索 (Depth-First-Search), 简称 DFS. 是一种常见搜索算法. 其方法是从原点不断一条路扩散, 当无路可走时回退来走下一条路, 直至找到目标或遍历.
[框架]
- int dfs(int n) {
- if(到达目标)return n;
- else{
- for(int i=0;i < 下一步走法数;++i){
- int temp=dfs(n+x);
- if(temp!=-1)return temp;
- }
- }
- return -1;
- }
[我对 DFS 的理解]
DFS 其实十分简单. 它的主旨就是只考虑当下怎么走, 换句话说就是每次函数调用只走一步, 走啊走, 走啊走, 不经意间发现自己走到了就返回结果就可以了.
你遇到一个 DFS 先不要慌张地想它的全部, 什么递归出口啦, 下一步怎么走啦, 返回什么啊...... 你啥也别想, 先写参数, 参数怎么写呢? 其实无比简单, 肯定得有一或多个参数来表示现在所在的位置吧, 其次你得有走到这儿的代价吧比如步数, 花费什么的. 一般的 DFS 有这些参数足以. 然后开始写出口, 出口那就更简单了, 直接上 if 干就行, 只要现在所在的位置是你要的目标位置就返回结果 (一般就是刚才的代价). 如果你已经完成出口那么你的 DFS 就已经完成一半了. 之后就是下一步怎么走, 这个就是异常的简单了. 会走路吗? 会走路就行. 只要调用下一层 DFS 就可以了 (注意下一层 DFS 的参数会变, 位置变成要去的位置, 代价在原来基础上加上走这步的代价). 如果下一层 DFS 的有返回值且是一个有效值就返回这个值. 最后就是应对无解, 只需在函数返回一个值代表无解就可以了. 到此为止 DFS 就写完了. 是不是无与伦比的简单呢?
[经典例题]
图的 m 着色问题 (color) AC 题解 https://www.cnblogs.com/zjd-ac/p/9747176.html
N 皇后问题 (queen.cpp) AC 题解 https://www.cnblogs.com/zjd-ac/p/9746144.html
[如何学好 DFS]
DFS 应用广泛, 大部分难的 DFS 都是在走下一步上用工夫.
要想精通需要多见题一定要多写! 一定要多写! 一定要多写! 写代码是懒人干的, 但不是给懒到连代码也懒得写的人干的! 当你精通 DFS 后你才可以看到她的美丽, 她的简练, 她的强大.
来源: http://www.bubuko.com/infodetail-2805267.html