学会深度优先搜索前一定要深刻理解递归，先来看一段代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 void dfs(int x){
 4     if(x==0) 
 5         return;
 6     cout<<x<<endl;
 7     dfs(x-1);
 8     cout<<"*"<<x<<endl;
 9 }
10 int main(){
11     dfs(5);
12     return 0;
13 }

结果为：

5
4
3
2
1
*1
*2
*3
*4
*5

因为函数的不断嵌套，cout<<"*"<<x<<endl;  始终不会运行，只有x-1=0时才会一层一层由小到大执行这一行。

正文开始！！！

来看深度优先搜索（回溯算法）：

 1 回溯算法的一般形式如下:
 2 void dfs(int k) { // k代表递归层数,或者说要填第几个空
 3     if(所有空已经填完了){
 4         判断最优解/记录答案;
 5         return;    
 6     }
 7     for (枚举这个空能填的选项)
 8         if (这个选项是合法的){//查看这个情况有没有被占位 
 9             记录下这个空(保存现场);//有时还需占位，例如四阶数独中的行、列、块记录 
10             dfs(k+1);
11             取消这个空(恢复现场);//如果占位了还需要取消占位 
12         }
13 }