No4. 深度优先搜索

/*No.1 不撞南墙不回头-深度优先搜索
向盒子里放扑克牌，每个盒子只能放一张，共有多少种放法？

int a[10],book[10],n; 　　//C变量默认初始化为0

void dfs(int step){ 　　　//step表示第几个盒子
　　int i;
　　if(step==n+1) 　　 //n+1,表示所有的盒子都已经放好扑克牌，可以打印
　　{
　　　　for(i=1;i<=n;i++)
　　　　　　printf("%d ",a[i]);
　　　　printf("\n");

　　　　return; //返回之前的一步（最近一次调用dfs函数的地方）
　　}

　　//现在站在第step个盒子面前，尝试放哪张牌？
　　for(i=1;i<=n;i++){
　　　　if(book[i]==0){ 　　　　 //book[i]==0表示第i号扑克牌在手上，可以放入盒子
　　　　　　a[step]=i;
　　　　　　book[i]=1; 　　　　//第i号扑克牌放入盒子，并标记为已使用
　　　　　　dfs(step+1); 　　　//尝试对下一个盒子执行同样的尝试，递归到所有盒子完成
　　　　　　book[i]=0; 　　　　//对当前盒子释放纸牌，返回上一个盒子，进行其他纸牌的尝试
　　　　}
　　}
　　return;
}

int main(){
　　scanf("%d",&n);
　　dfs(1);
　　getchar();getchar();
　　return 0;
}

这是一种典型的深度优先算法DFS：其关键在于解决“当下该如何做”，至于“下一步如何做”则与“当下该如何做”是一样的！
比如上面的例子，可以理解为一种树形深度搜索：
　　1.先确定根前提，然后向下一层延伸，确定下一层条件之后，再深入；
　　2.达到叶子节点之后，先释放叶子节点并回到上一层，看下是否有其他可能的树分支：
　　　　如有，则继续1
　　　　如无，则继续2
　　3.直到所有根节点遍历完毕！

深度优先搜索的基本模型：
　　void dfs(int step){
　　　　//判断边界
　　　　for() //尝试每一种可能
　　　　{
　　　　　　dfs(step+1);
　　　　}
　　　　return;
　　}
*/

/*No.2 用上面方法重写ABC + DEF = GHI 公式
int a[10],book[10]; 　　 //注意数组大小，a[10]才有下标为9的索引，a[9]是没有的！不然会出现内存混乱现象(total)以及公式不成立问题！
int total=0;　　　　　   //全局变量，不受递归影响，用于计数
void dfs(int step){
　　int i;
　　if(step==10){
　　　　if(100*a[1]+10*a[2]+a[3]+100*a[4]+10*a[5]+a[6] == 100*a[7]+10*a[8]+a[9])
　　　　{
　　　　　　total++;
　　　　　　printf("%d%d%d + %d%d%d = %d%d%d, total=%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9], total);
　　　　}
　　　　return;
　　}
　　for(i=1;i<=9;i++){
　　　　if(book[i]==0){
　　　　　　a[step]=i;
　　　　　　book[i]=1;
　　　　　　dfs(step+1);
　　　　　　book[i]=0;
　　　　}
　　}
　　return;
}

int main(){
　　dfs(1);
　　printf("Total equations %d",total);
　　getchar();getchar();
　　return 0;
}

*/

No4. 深度优先搜索

原文：https://www.cnblogs.com/yalimy/p/15008360.html