深度优先搜索dfs

在进行搜索时，通过控制搜索进程中的各个状态，我们能设计出一个枚举顺序，从而考虑所有可能的形式。

通常，我们通过一个 dfs 函数来完成搜索枚举，而通过参数表示当前状态。例如在大部分搜索枚举问题中，可以通过 step 或 depth 表示当前枚举层数，或使用 n 表示已经选入的数量，抑或在对于一些对 和 有限制的问题中，使用 sum 表示已经选入的数量之和。

让我们来看一道使用搜索枚举实现的题目：
现有方程a_1 x_1 + a_2 x_2 + a_3 x_3 =0，其中2≤n≤10,1≤a[i]≤5,−2≤x[i]≤2,x[i]∈Z，求解的总数。

能够估算所有的状态总数在 5¹⁰ ≈10 ⁷ ，能够枚举全部的状态。虽然能够使用 10 个循环完成，但此处使用搜索枚举更为方便，更便于使用一些剪枝的方法进行优化。

int ans = 0;
void dfs(int dep, int sum) {
    if(dep == n) {
        if (sum == 0){
            ans++;
        }
        return ;
    }
    for (int i = -2; i <= 2; i++) {
        dfs(dep + 1, sum + a[dep] * i);
    }
}

状态的概念：
dep:当前枚举到第dep个值
sum:当前a[1]x[1]+a[2]x[2]+……+a[dep-1]x[dep-1]的总和
当没举完a[n]x[n]，应该dep枚举到了n+1,不要被前面的代码弄混，那个是下标从0开始到n-1的情况！

设a[1]=a[2]……=a[n]=0,n=2
在最外层，我们会枚举的是dfs(0,0)，第一次dfs时，我们枚举的是dfs(1,0+1*(-2))，即dfs(1,-2），所以我们接下来要枚举的是x[2]=-2，dfs(2,-4)……
现在，大家想一下，如果我想让最后结果成立，dfs(1,-2）过后，x[1]是2，dfs(2,-3)，……直到x[1]=2,的方式(2，0)。
最后再回到第一层，x[0]=-1,dfs(1,-1),再枚举x[1]=-2，dfs（1,-3)……

在很多搜索枚举问题中，会要求我们打印具体内容。如果我们想直到具体的方案的话可以使用数组或相应类型的vector，来保存可行的解。比如之前求方程解的问题，可将代码修改为

int ans = 0;
void dfs(int dep, int sum) {
    if(dep == n) {
        if (sum == 0){
            ans++;
        }
        return ;
    }
    for (int i = -2; i <= 2; i++) {
        dfs(dep + 1, sum + a[dep] * i);
    }
}

当然，也可以在计算过程中直接输出可行解：

void dfs(int dep, int sum) {
    if(dep==n){
        if(sum==0){
            for(int i=0;i
                cout<
        ans[dep]=i;
        dfs(dep+1,sum+a[dep]*i);
    }
}

在搜索枚举的过程中，我们能够根据题目的一些性质，对求解的过程进行剪枝优化。但是对大部分题目来说，搜索枚举很有可能达到状态的上限，所以很有必要在决定使用搜索枚举之前确定状态的总数。

枚举方程的解代码：

#include 
using namespace std;
const int N = 15;
int n;
int a[N], ans[N];
void dfs(int dep, int sum) {
    if(dep==n){
        if(sum==0){
            for(int i=0;i
                cout<
        ans[dep]=i;
        dfs(dep+1,sum+a[dep]*i);
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    dfs(0, 0);
    return 0;
}

互质序列：要求在原数组中找到长度为k的子序列，且子序列中相邻的两个数互质，输出所有符合要求的子序列。
和枚举方程不同的是，在此题中，我们本质上在枚举下一个可行的放入子序列中的数字。这里dep表示已经取到了第几个数，而len表示现在渠道的子序列长度。
那么下一个可以选择的数字位于[dep+1,n]之间，判断选入的数字是否与当前数字互指即最大公因数为1.
需要注意的是，为了让一个数都没有被选入时，也能通过相同的代码，判断下一个选入的数是否互质，我们可以将ans[0]初始化为1。
考虑什么时候枚举到已经找到长度为k的子序列？
我们dfs函数中，len=k时说明已经找到了相邻互质的子序列，那么我们就可以将保存在ans数组中的答案输出。
gcd函数为什么这么写可以见我写的gcd函数讲解
互质序列的代码：

#include 
using namespace std;
const int N = 15;
int n, k;
int a[N], ans[N] = {1};
int gcd(int a, int b) {
    if(b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}
void dfs(int dep, int len) {
    if(len==k){
        for(int i=1;i<=k;i++){
            cout<
        if(gcd(a[i],ans[len])==1){
            ans[len+1]=a[i];
            dfs(i,len+1);
        }
    }
}
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    dfs(0, 0);
    return 0;
}

N阶幻方：
幻方是一种很神奇的N×N 矩阵：它由数字1,2,3,…,N×N 构成，且每行、每列及两条对角线上的数字之和都相同。当 N 为奇数时，我们可以通过以下方法构建一个幻方：

首先将 1 写在第一行的中间。
之后，按如下方式从小到大依次填写每个数 K(K=2,3,…,N×N)：
若 (K−1) 在第一行但不在最后一列，则将 K 填在最后一行，(K−1) 所在列的右一列；
若(K−1) 在最后一列但不在第一行，则将 K 填在第一列，（K−1) 所在行的上一行；
若 (K−1) 在第一行最后一列，则将 K 填在 (K−1) 的正下方；
若 (K−1) 既不在第一行，也不在最后一列，如果 (K- 1)的右上方还未填数，则将 K 填在 （K−1) 的右上方，否则将 K 填在 (K−1) 的正下方。
现给定1≤N≤39)，请按上述方法构造 N×N 的幻方。

在这里，我们按照题意设计一个搜索方式，将幻方中的所有方格填上并输出。首先我们确认 dfs 函数中各个参数的含义，其中 x y 分别表示上一个所填写的数字位置，而 id 表示我们现在需要填写的数字。那么在 main 函数中，需要先放好 11 的位置，之后调用搜索函数。

因为当id>nn时，说明幻方中的数字都填写完成了，所以边界条件就应该是id>nn，那么我们这时就可以将幻方中的数字全部输出。要小心输出完毕后，要将函数结束，否则程序将陷入死循环。

N阶幻方的代码：

#include 
using namespace std;
const int N = 45;
int n;
int a[N][N];

void dfs(int x, int y, int id) {
    if(id>n*n){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                cout<
        a[n][y+1]=id;
        dfs(n,y+1,id+1);
    }else if(y==n && x!=1){
        a[x-1][1]=id;
        dfs(x-1,1,id+1);
    }
    else if(x==1 && y==n){
        a[x+1][y]=id;
        dfs(x+1,y,id+1);
    }else{
        if(!a[x-1][y+1]){
            a[x-1][y+1]=id;
            dfs(x-1,y+1,id+1);
        }else{
            a[x+1][y]=id;
            dfs(x+1,y,id+1);
        }
    }
}

int main()
{
    cin >> n;
	a[1][(n+1)/2]=1;
    dfs(1,(n+1)/2,2);
    return 0;
}