万能的搜索的学习——深度优先搜索

深度优先遍历图的方法是，从图中某顶点v出发：

• 访问顶点v；
• 依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
• 若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止

理解深度优先搜索的关键在于解决“当下该如何做”。至于“下一步如何做”，则与“当下该如何做”事一样的。下面代码就是深度优先搜索的基本模型。

  void dfs(int step)
{
  //判断边界
  //尝试每一种可能 
  for(int i = 1; i <= n; i++){
      //继续下一步
      dfs(step+1);
  }
}

下面我们来看一道奥数题，口口口+口口口=口口口，将数字1~9分别填入9个口中，每个数字只能使用一次使得等式成立。例如173+286=459就是一个合理的组合，请问一个有多少种合理的组合呢？

我们尝试一下用深度优先搜索来解一下这道题，1_{9个数字，我们就把它看成是1}9的九张扑克牌，然后将这九张扑克牌放到九个盒子中，使得等式成立。我们用a[9]来表示盒子里面的扑克牌，那么只要判断一下 a[1]100+a[2]10+a[3]+a[4]100+a[5]10+a[6] = a[7]100+a[8]10+a[9]这个等式是否成立。
代码和解释如下：

#include <stdio.h>

int a[10], mark[10], total = 0;

// step表示现在站在第几个盒子面前
void depthFirstSearch(int step)
{
    int i;
    // 如果站在第10盒子面前，则表示前9个盒子已经放好扑克牌
    if (step == 10) {
        // 判断是否满足等式
        if (a[1]*100+a[2]*10+a[3]+a[4]*100+a[5]*10+a[6] == a[7]*100+a[8]*10+a[9]) {
            // 如果满足要求可行性的解+1，并打印这个解
            total++;
            printf("可行性的解%d: %d%d%d + %d%d%d = %d%d%d\n",total,a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
        }
        // 返回最近调用函数的地方
        return;
    }
    
        // 此时站在第step个盒子前，应该放那张牌，按照1、2、3...n尝试
        
        for (i = 1; i <=9; i++) {
            // 判断扑克牌i是否还没有用
            if (mark[i] ==0) {

                a[step] = i;    // 将i放到第step个盒子中
                mark[i] = 1;    // 将mark[i]的值设为1，表示扑克牌i已经被用过了
                
                // 接下来是利用递归放置下一个盒子的牌了
                depthFirstSearch(step+1);
                // 将刚才尝试的扑克牌收回，才能进行下一次的尝试
                mark[i] = 0;
                
            }
    }
    return;
}

int main(int argc, const char * argv[]) {

    depthFirstSearch(1);
    
    // 因为 173+286 = 459 和 286+173 = 459是同一个组合
    printf("有%d组",total / 2);
    
    getchar();getchar();
    return 0;
}