深度优先搜索(DFS)

目标

深度优先搜索模板题，尝试理解“状态”这个概念。

DFS是什么

搜索，又称状态空间搜索，是指通过搜索从初始状态到目标状态的路径以完成问题求解的算法。

depth first search(dfs)， 按照深度优先的顺序对“问题状态空间”进行搜索的算法（理解理解搜索树，是不是深度优先?）

“深搜”，是一种包括遍历形式、状态记录与检索、剪枝优化等算法整体设计的统称。提前学习建图方法后，掌握在图上进行遍历，进一步把“问题空间”类比为一张图。

研究 dfs 算法之前，要定义该过程产生的 “搜索树” 结构，整个深搜算法就是基于该搜索树完成的（用递归实现的指数型枚举、排列性枚举、组合型枚举，其实就是深搜的三种最简单的形式）。

dfs，常常指利用递归函数实现暴力枚举的算法。

递归搜索，该类搜索算法的特点在于，将要搜索的目标分成若干“层”，每层基于前几层的状态进行决策，直到达到目标状态。

八皇后问题

上图是，四皇后，递归搜索树的示例

#include <iostream>
using namespace std;
const int N = 20;

int n;
char g[N][N];
bool col[N], dg[N], udg[N];

void dfs(int u) {
    // u == n 表示已经搜了n行，故输出方案
    if (u == n) {
        for (int i = 0; i < n; i ++ ) puts(g[i]);   // 等价于cout << g[i] << endl;
        puts("");  // 换行
        return;
    }

    //对每行的n个位置按行搜索
    for (int i = 0; i < n; i ++ )
        //剪枝(对于不满足要求的点，不再继续往下搜索)
        //udg[n - u + i]，+n是为了保证大于0
        if (!col[i] && !dg[u + i] && !udg[n - u + i]) {
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true;
            dfs(u + 1);
            // 恢复现场 这步很关键
            col[i] = dg[u + i] = udg[n - u + i] = false;
            g[u][i] = '.';
        }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            g[i][j] = '.';

    dfs(0); // 函数的调用

    return 0;
}

// 按行枚举
// 这里dfs(u)表示的是，第u行

// bool数组用来判断搜索的下一个位置是否可行
// col列，dg对角线，udg反对角线
// g[N][N]用来存路径

//（1）反对角线 y=x+b, 截距 b=y−x，因为我们要把 b 当做数组下标，所以 b 不能是负的
// 所以我们 +n，保证是结果是正的
//（2）而对角线 y=−x+b, 截距是 b=y+x，这里截距一定是正的，所以不需要加偏移量

// 反对角线，左上到右下
// 对角线，左下到右上

// 反对角线udg[n−u+i]，对角线 dg[u+i]中的下标
// n−u+i，u+i 表示的是截距

代码框架

void dfs(int u) {
    // 问题的边界

    // 求解子问题

}

总结

DFS 是一个非常重要的基础算法，虽然基础，但可以用到最后的算法。

其难度，随着题面逻辑的复杂而提升，抽象的问题定义，将会成为难点。

俗话说的好，“暴力拿省一”，甚至，暴力拿金牌。

虽然都是暴力，但是人家的暴力，可是高级的暴力。

一个题目，人家说，暴力。可能你连题目说的是什么，都无法有效的阅读理解。

在普及组阶段，应该不贪多，学到了 DFS，就做一个阵地战，把 DFS 打死打穿，就不往后面走了。直接去参加比赛，也依然没有大问题，甚至表现还要优于贪多理论知识的选手。

打磨技能的这个过程中，我们将获得基础能力的积累和提升，为后续算法的有效推进，做好准备。