深度优先搜索

定义

深度优先搜索，是一种按照深度优先的顺序对「问题状态空间」进行搜索的算法。

理解

对于某些特定的问题，问题状态空间可以抽象为一张图，问题状态可以类比为节点，状态之间的联系与转换关系可以类比为图中连接节点与节点的边。使用深度优先搜索算法求解这类问题，等同于在一张图上进行深度优先遍历。
深度优先搜索是基于递归的一种算法。递归是一种单纯的遍历方式，而深度优先搜索是一类包括遍历形式、状态记录与检索以及剪枝优化等算法整体设计的统称。

通过一个具体的例子理解深度优先搜索的算法思想。

现有一个如下图所示的矩形迷宫，其中某些位置是障碍物（由深灰色表示），每次移动可以从当前位置移动到上、下、左、右的位置（不可以越过边界，移动后的位置不可以是障碍物），判断能否从迷宫左上角的起点走到右下角的终点。

为了寻找走出迷宫的路径，可以从起点出发，每次依次尝试向右、下、左、上四个方向移动。在探索的过程中，一旦发现原来的移动选择不可行（越过边界或者遇到障碍物），就回退到上一步重新选择其他的移动方式，继续探索。如此反复尝试，直到到达终点。

概括一下，深度优先搜索的算法思想即为「不撞南墙不回头」。从初始状态开始，按照某种策略一直进行尝试。如果遇到不可行的情况，则回退到上一步，尝试新的可能情况。经过反复的尝试，最终会探索到可行的答案，或者发现问题无解。

算法过程

深度优先搜索解决问题的过程包括四个关键因素：

1. 状态表示：状态一般是指客观现实信息的描述，通常用 $T$ 表示。一般用 $T_0$ 表示初始状态，即问题给出的初始条件。用 $T_n$ 表示目标状态，即问题解决后的最终答案。
2. 状态转移：根据问题给定的规则控制从当前状态转移到下一个状态。整个问题的求解过程则可以抽象为一系列的状态转移步骤，从初始状态按照特定的规则一步一步转移到目标状态。
3. 状态判重：在大多数情况下，搜索的过程中会遇到重复状态，即现在达到的状态在之前的探索过程中已经遇到过，在这种情况下，需要注意避免死循环和空间的浪费。
4. 递归回溯：当把问题分成若干步骤并递归求解时，如果在当前状态已经不存在合法的状态转移步骤可以转移到下一状态，则返回上一状态进行递归调用。

代码模板

在代码层面上，深度优先搜索有最重要的两个特征：

1. 目标状态：说明了搜索过程结束的条件，当状态转移到目标状态时，可以直接输出答案或者做其他处理，不需要进行后续的搜索。
2. 状态转移：从当前状态按照问题给出的状态转移规则，依次尝试转移到下一状态。为了保证每次从当前状态开始转移时，所有可变量保持一致，回溯时根据实际情况需要选择是否还原现场。

深度优先搜索代码的一般形式如下：

void dfs(int step, 其他参数列表){
    if(到达目标状态){
        ... // 输出答案或者做计数等处理
        return;
    }

    for(int i = 1; i <= 当前状态可能的转移方式数量; i++){
        if(第 i 种状态转移方式可行){
            ... // 保存当前状态
            dfs(step + 1, 其他参数列表); // 按第 i 种状态转移方式转移到下一状态
            ... // 根据问题需求，回溯时选择是否需要还原现场（利用保存过的当前状态恢复现场，方便从当前状态向其他的状态转移）
        }
    }
    return;
}

具体应用

N 皇后问题

在 $N * N$ 的棋盘上放 $N$ 个皇后，使得他们不能相互攻击。两个皇后能相互攻击当且仅当她们在同一行，或者同一列，或者同一条对角线上。找出一共有多少种放置方法。

问题的初始状态是棋盘上没有皇后，目标状态是棋盘上摆放了 $N$ 个皇后，且相互之间不会攻击。目标状态可能有多个，目标状态的数量即为答案。
考虑一个一个依次摆放皇后，由于两个皇后不能在同一行，因此每个步骤是将一个皇后放在新的一行上合适的位置。每次放置新的皇后时，可以放在新的一行中不会引起冲突的任何位置。
为了快速判断是否存在冲突，可以根据每列和两个方向的每条对角线是否有皇后占据建立标志数组。每次新放置一个皇后时对所影响的列和对角线位置进行标记，回溯时挪动一个旧皇后的位置则需要清除原有标记。
对于对角线的冲突判断，有两个简便的规律：

1. 对于从左上往右下的对角线，位于同一条对角线上的位置 (i, j) 满足 i - j 的值始终相等。
2. 对于从左下往右上的对角线，位于同一条对角线上的位置 (i, j) 满足 i + j 的值始终相等。

以 $4 * 4$ 棋盘放置 $4$ 皇后为例，每个状态即为一个棋盘，部分搜索过程如下：

int n; // 棋盘的大小
int ans = 0; // 保存最终结果
vector<bool> vis_col(n, false); // 对应列的标记数组
vector<bool> vis_diag_0(2 * n, false), vis_diag_1(2 * n, false); // 对应两条对角线的标记数组

// 每次调用 dfs 函数，将一个皇后放在新的一行上合适的位置，参数 row 表示在当前步骤，准备放置皇后的是第几行
void dfs(int row){
    if(row >= n){ // 前 n 行都已经放置好皇后，说明找到一种放置方案
        ans++;
        return;
    }
    for(int col = 0; col < n; col++){ // 枚举每一列，看是否能够在 (row, col) 的位置放置一个皇后
        // 如果对应列，或者对应对角线已经被占用，则当前位置无法放置新的皇后
        if(vis_col[col] || vis_diag_0[row + col] || vis_diag_1[row - col + n])  continue;
        // 如果该位置可以放置新的皇后，则标记对应的列和对角线，继续考虑下一行
        vis_col[col] = true;
        vis_diag_0[row + col] = true;
        vis_diag_1[row - col + n] = true;
        dfs(row + 1);

        // 后续情况已经搜索完成
        // 回溯阶段需要还原现场，即释放对应的列和对角线，继续考虑 (row, col + 1) 的位置能否放置一个皇后
        vis_col[col] = false;
        vis_diag_0[row + col] = false;
        vis_diag_1[row - col + n] = false;
    }
    return;
}

dfs(0); // 调用 dfs 函数，从第 0 行开始考虑
cout << ans << endl;

迷宫问题

有一个 $N \times M$ 方格的迷宫，迷宫里的部分方格处有障碍物，障碍物不可通过。在迷宫中移动有上下左右四种方式，每次只能从当前方格移动到与之相邻的方格。给定起点位置和终点位置，每个方格最多经过一次，问有多少种从起点到终点的方案。

问题的初始状态是人位于起点，目标状态是人通过某种移动方式到达了终点，目标状态可能有多个，目标状态的数量即为答案。
考虑每个步骤是从当前方格分别尝试向上、下、左、右移动一步。每次移动会有三种情况导致移动无法完成：

1. 移动后的目标方格处于迷宫边界之外。
2. 移动后的目标方格是障碍物。
3. 移动后的目标方格在之前已经访问过，即违背了“每个方格最多经过一次”的题目要求。为了快速判断这种冲突，可以建立与迷宫大小相同的标志数组将已经访问过的方格进行标记，但回溯时则需要清除这部分方格的原有标记。

int n, m;
vector<vector<int>> maze; // n * m 的迷宫，其中有障碍物的方格用 1 表示，没有障碍物的方格用 0 表示
int sx, sy; // 起点位置
int fx, fy; // 终点位置
vector<vector<bool>> vis(n, vector<int>(m, false)); // 对应迷宫各个方格的标记数组
int ans = 0;

int dir[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 使用一个数组记录向四个方向移动时横纵坐标的变化

bool check(int x, int y){ // 判断位置 (x, y) 是否位于迷宫边界之外
    if(x >= 0 && x < n && y >= 0 && y < m) return true;
    return false;
}

// 每次调用 dfs 函数，从位置 (x, y) 尝试向上、下、左、右移动一步
void dfs(int x, int y){
    if(x == fx && y == fy){ // 如果已经到达终点，说明找到一种路径方案
        ans++;
        return;
    }
    for(int i = 0; i < 4; i++){
        int nextx = x + dir[i][0], nexty = y + dir[i][1];
        // 如果当前移动不会出现三种冲突，则移动一步并继续考虑下一个位置的移动方式
        if(check(nextx, nexty) && maze[nextx][nexty] == 0 && !vis[nextx][nexty]){
            vis[nextx][nexty] = true; // 标记该位置为已经访问过，继续考虑下一个位置
            dfs(nextx, nexty);
            vis[nextx][nexty] = false; // 后续情况已经搜索完成。回溯阶段需要还原现场，即清除该位置的标记
        }
    }
    return;
}

// 调用 dfs 函数，从起点开始考虑（起点需要标记为已访问过）
vis[sx][sy] = true;
dfs(sx, sy);
cout << ans << endl;

池塘计数

给定一个 N 行 M 列的区域，每个区域用 * 表示有水，用 # 表示陆地。如果一个区域有水且它相邻的区域也有水，则两个区域同属于一个水塘。一个区域最多有八个相邻的区域，即上、下、左、右、左上、左下、右上、右下。计算整个区域中有多少个水塘。

考虑每次寻找一个完整的水塘，初始状态是从一个有水的区域开始，目标状态是到达一个有水的区域后，无法继续拓展，即周围的区域是陆地或者是已经访问过的有水区域。每个步骤是从当前有水的区域分别尝试向上、下、左、右、左上、左下、右上、右下拓展一个有水的区域。每次拓展会有三种情况导致当前区域的拓展结束：

1. 拓展后的区域处于边界之外。
2. 拓展后的区域是陆地。
3. 拓展后的区域在之前已经访问过，无需重复拓展。可以建立与整体区域大小相同的标志数组将已经访问过的方格进行标记，并且回溯时不需要清除这部分方格的原有标记，即每个区域只在第一次访问时进行标记，表示该区域属于当前搜索的这个水塘。

寻找一个水塘的过程是一次深度优先搜索的过程。要统计整个区域中水塘的数量，只需要每次找到一个还未标记过的有水区域，开始一次深度优先搜索，则可以拓展出一个新的水塘，并且这个水塘中的所有区域在标记数组中都会被标记。因此，当下一次找到一个还未标记过的有水区域时，则从该区域拓展出的水塘必然是一个新的水塘，从而保证了算法的正确性。

int n, m;
vector<string> mp(n); // n * m 的地图，其中是陆地的区域用 # 表示，是有水的区域用 * 表示
vector<vector<bool>> vis(n, vector<bool>(m, false)); // 对应各个区域的标记数组

int dir[8][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}}; // 使用一个数组记录向八个方向移动时横纵坐标的变化

bool check(int x, int y){ // 判断位置 (x, y) 是否位于区域边界之外
    if(x >= 0 && x < n && y >= 0 && y < m) return true;
    return false;
}

// 每次调用 dfs 函数，从位置 (x, y) 尝试向上、下、左、右、左上、左下、右上、右下拓展一格，无法拓展则调用结束，找到一个新的水塘
void dfs(int x, int y){
    vis[x][y] = true; // 标记该位置为已经访问过，继续考虑下一个位置
    for(int i = 0; i < 8; i++){
        int nextx = x + dir[i][0], nexty = y + dir[i][1];
        // 如果当前移动不会出现三种冲突，则拓展一格并继续考虑下一个位置的拓展
        if(check(nextx, nexty) && mp[nextx][nexty] == '*' && !vis[nextx][nexty]){
            dfs(nextx, nexty);
        }
    }
}

int ans = 0;
for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
        if(mp[i][j] == '*' && !vis[i][j]){ // 每当遇到一个未标记的有水区域，则开始一次搜索，寻找一个新的水塘
            dfs(i, j);
            ans++;
        }
    }
}
cout << ans << endl;