--- title: "搜索算法" description: "枚举、模拟、贪心、递归、二分、动态规划、图论等经典算法。" --- > Documentation Index > Fetch the complete documentation index at: https://cppguide.xyz/llms.txt > Use this file to discover all available pages before exploring further. # 搜索算法 ![](https://img.dailyup.xyz/originals/8208463026701-ba5d054c-ab3f-41d9-90a1-8d06913929ef.png) **深度优先搜索算法（DFS）** 和 **广度优先搜索算法（BFS）** 是两种最基本的图遍历算法。相当于在搜索遍历时两者走路的策略不太一致。 ## 深度优先搜索 DFS **深度优先搜索（Depth-First Search，简称 DFS）** 是一种用于遍历或搜索树或图的算法。其基本思路是，从根节点或起始节点开始，沿着一条路径一直往下走，直到走到底部（无法再往下走为止），然后返回上一层继续遍历其他路径。 这个过程类似于我们在迷宫中寻找出口，一直走到不能再走为止，然后返回之前的路口继续寻找其他路径。 例如，对于下面左图的一棵节点树，如果按照深度优先搜索算法的思路（一条路走到黑），其搜索路径应该如下图所示（可结合节点编号与遍历路径来看）。 ![](https://img.dailyup.xyz/optimized/8208463023675-702d84a2-3cff-4967-a421-264ac78c707d.png) 注意，在访问了节点 4 后，由于这条路径上的节点全都访问过了，因此会从节点 4 返回到上一层节点，也就是节点 3，再看节点 3 除了节点 4 外，还有一个节点 5，因此节点 4 访问后，会回到上一层，再按同样的方法继续往下搜索，这种回到上一层继续搜索的方式就是**回溯**。 > 为了避免重复访问已经访问过的节点，我们需要标记每个节点是否已经被访问过了！ 另外，从上面的图也可以看到，深度优先搜索算法首先是遍历一个节点的所有子节点，然后再依次遍历每个子节点的所有子节点。这种方式有点类似树的先序遍历。DFS 的算法实现一般用递归来实现（基于栈的形式，先进后出）。 ## 示例：扫地机器人 ### 题目描述 Mike 同学在为扫地机器人设计一个在矩形区域中行走的算法，Mike 是这样设计的：先把机器人放在出发点 (1, 1) 点上，机器人在每个点上都会沿用如下的规则来判断下一个该去的点是哪里。规则：优先向右，如果向右不能走（比如：右侧出了矩形或者右侧扫过了）则尝试向下，向下不能走则尝试向左，向左不能走则尝试向上；直到所有的点都扫过。 Mike 为了验证自己设计的算法是否正确，打算先模拟一下这个算法，每当机器人走过一个单元格时，会在单元格内标记一个数字，这个数字从 1 开始，每经过一个单元格数字会递增 1 ，直到所有的单元格都扫一遍，也就是所有的单元格都标记过数字，机器人会自动停止。 比如：如果机器人按照上面的规则，清扫一个 3×4 大小的矩形区域，那么标记数字的结果如下图所示。 ![img](https://img.dailyup.xyz/optimized/8208463024200-479bc834-f490-4a88-b08e-b9d01471f209.png) 再比如：如果机器人按照上面的规则，清扫一个 5×5 大小的矩形区域，那么标记数字的结果如下图所示。 ![img](https://img.dailyup.xyz/optimized/8208463024087-35df1572-d900-4cd8-be79-fe2fb4816071.png) 请你帮助 Mike 设计一个程序，按照上面的规则，将一个 $n \times m$ 大小的矩形，标记一下数字，输出最终标记的结果。 ### 输入描述 一行内有 2 个两个整数 $n$ 和 $m$ ，用空格隔开，分别代表矩形区域的行数（高）和列数（宽）。 $1 \lt n, m \lt 10$ ### 输出描述 输出按题意机器人走过每个点之后，标记数字的结果，每个数字输出时场宽设置为 3。 ### 输入输出样例 输入数据 ``` 3 4 ``` 输出数据 ``` 1 2 3 4 10 11 12 5 9 8 7 6 ``` ### 题目分析 【待补充】 ### 实现代码 ```cpp #include using namespace std; const int N = 20; int n, m, q[N][N]; void clear(int x, int y, int k) { q[x][y] = k; // 清扫的顺序依次为右、下、左、上 // 向右 if (y + 1 <= m && q[x][y + 1] == 0) clear(x, y + 1, k + 1); // 向下 if (x + 1 <= n && q[x + 1][y] == 0) clear(x + 1, y, k + 1); // 向左 if (y - 1 >= 1 && q[x][y - 1] == 0) clear(x, y - 1, k + 1); // 向上 if (x - 1 >= 1 && q[x - 1][y] == 0) clear(x - 1, y, k + 1); } int main() { cin >> n >> m; clear(1, 1, 1); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cout << setw(3) << q[i][j]; } cout << endl; // 一排结束后换行 } return 0; } ``` 继续改进，这里的递归是满足条件时才会进入。 我们也可以按下面这样来写，结果一致，但两者的判断时机不一样。 ```cpp #include using namespace std; const int N = 20; int n, m, q[N][N]; void clear(int x, int y, int k) { if (x >= 1 && x <= n && y >= 1 && y <= m && q[x][y] == 0) { q[x][y] = k; // 清扫的顺序依次为右、下、左、上 // 向右 clear(x, y + 1, k + 1); // 向下 clear(x + 1, y, k + 1); // 向左 clear(x, y - 1, k + 1); // 向上 clear(x - 1, y, k + 1); } } int main() { cin >> n >> m; clear(1, 1, 1); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cout << setw(3) << q[i][j]; } cout << endl; // 一排结束后换行 } return 0; } ``` 方法3: ```cpp #include using namespace std; const int N = 20; int n, m, q[N][N]; int dx[5] = {0, 0, 1, 0, -1}; int dy[5] = {0, 1, 0, -1, 0}; void clear(int x, int y, int k) { q[x][y] = k; // 清扫的顺序依次为右、下、左、上 // 向右 int tx, ty; for (int i = 1; i <= 4; i++) { tx = x + dx[i]; ty = y + dy[i]; if (tx >= 1 && tx <= n && ty >= 1 && ty <= m && q[tx][ty] == 0) { clear(tx, ty, k + 1); } } } int main() { cin >> n >> m; clear(1, 1, 1); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cout << setw(3) << q[i][j]; } cout << endl; // 一排结束后换行 } return 0; } ``` ## 示例：迷宫出口 ### 题目描述 一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由 $n \times n$ 的格点组成，每个格点只有 2 种状态， 0 和 1，前者表示可以通行后者表示不能通行。 同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点 A 走到点 B ，问在不走出迷宫的情况下能不能办到。 如果起点或者终点有一个不能通行(为 1)，则看成无法办到。 ### 输入描述 第 1 行是一个正整数 $n (1 \le n \le 100$)，表示迷宫的规模是 $n \times n$ 的。 接下来是一个 $n \times n$ 的矩阵，矩阵中的元素为 0 或者 1。 再接下来一行是 4 个整数 ha la hb lb，描述 A 处在第 ha 行 第 la 列，B 处在第 hb 行 第 lb 列。 ### 输出描述 能办到则输出 `YES`，否则输出 `NO`。 ### 输入输出样例 输入数据 ``` 3 0 1 1 0 0 1 1 0 0 1 1 3 3 ``` 输出数据 ``` YES ``` ### 代码实现 ```cpp #include using namespace std; const int N = 110; int n, sx, sy, ex, ey, q[N][N]; bool flag = false; int dx[5] = {0, 0, 1, 0, -1}; int dy[5] = {0, 1, 0, -1, 0}; void dfs(int x, int y) { q[x][y] = 2; // 将走过的点做标记，为 1 int tx, ty; for (int i = 1; i <= 4; i++) { tx = x + dx[i]; ty = y + dy[i]; if (tx >= 1 && tx <= n && ty >= 1 && ty <= n && q[tx][ty] == 0) { // 到终点了 if (tx == ex && ty == ey) { flag = true; } else { dfs(tx, ty); } } } } int main() { cin >> n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> q[i][j]; } } cin >> sx >> sy >> ex >> ey; if (q[sx][sy] == 1 || q[ex][ey] == 1) { cout << "NO"; } else { dfs(sx, sy); if (flag) cout << "YES"; else cout << "NO"; } return 0; } ``` ## 示例：全排列 给定一个整数 n，将数字 1 ～ n 排成一排，请你按照字典序将所有的排列方法输出。 ### 输入格式 共一行，包含一个整数 n。 ### 输出格式 按字典序输出所有排列方案，每个方案占一行。 ### 数据范围 1 ≤ n ≤ 71 ### 输入输出样例： **输入 #1** ``` 3 ``` **输出 #1** ``` 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 ``` ### 题目分析 (待更新) ### 实现代码 - 代码：https://onecompiler.com/cpp/3z4wgxxqf ```cpp #include using namespace std; const int N = 10; int n; int path[N]; bool st[N]; void dfs(int u) { if (u == n + 1) { for (int i = 1; i <= n; i++) printf("%d", path[i]); puts(""); return; } for (int i = 1; i <= n; i++) { if (!st[i]) { st[i] = true; // 标记走过的节点 path[u] = i; // 保存节点路径 dfs(u + 1); // 往下一层搜索 st[i] = false; // 恢复现场 } } } int main() { cin >> n; dfs(1); return 0; } ``` 希望通过这个例子你是理解了深度优先搜索算法的基本思路和实现过程。 ## DFS练习：N皇后问题 ### 题目描述 N 皇后问题是指将 N 个皇后放在 N×N 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。 ![](https://img.dailyup.xyz/optimized/8208463020644-ab8a1d04-ea9e-4b7d-b6be-ba8a53fb011e.png) 上面是其中两种参考的摆法。现在给定整数 n，请你输出所有的满足条件的棋子摆法。 ### 输入格式 共一行，包含整数 n。 ### 输出格式 每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。 其中 `0` 表示某一个位置的方格状态为空，`Q1 表示某一个位置的方格上摆着皇后。 每个方案输出完成后，输出一个空行。 **注意：行末不能有多余空格。** 输出方案的顺序任意，只要不重复且没有遗漏即可。 ### 数据范围 1≤n≤9 ### 输入输出样例 **输入 #1** ``` 4 ``` **输出 #1** ``` 0100 0001 1000 0010 0010 1000 0001 0100 ``` ### 题目分析 （待更新） ### 代码实现 - 源码：[3z65hj4ss - C++ - OneCompiler](https://onecompiler.com/cpp/3z65hj4ss) ```cpp #include using namespace std; const int N = 20; int n; char g[N][N]; bool col[N], dg[N], udg[N]; void dfs(int u) { if (u == n) { for (int i = 0; i < n; i++) puts(g[i]); puts(""); return; } for (int i = 0; i < n; i++) { if (!col[i] && !dg[u + i] && !udg[n - u + i]) { g[u][i] = '1'; 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] = '0'; } } } int main() { cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { g[i][j] = '0'; } } dfs(0); return 0; } ``` ## 广度优先搜索 BFS **广度优先搜索算法（Breadth-First Search，简称BFS**）是另外一种用于遍历或搜索树或图的算法。其基本思路是，**从起始节点开始，依次访问它的所有邻居节点，然后再依次访问它们的邻居节点，直到遍历完整棵树或图**。 这个过程类似于我们在迷宫中寻找出口时，先搜寻周围的所有可行路径，再逐层扩展搜索范围，直到找到出口为止。 例如，对于下面图中的这棵节点树，如果按照广度优先搜索算法的思路（按层级搜索），其搜索路径应该如下右图所示（结合节点编号来看）。 ![](https://img.dailyup.xyz/optimized/8208463020599-3474cced-6186-42bc-8015-601684785ddc.png) **广度优先搜索通常用于查找最短路径**，因为它保证在遍历完所有相邻节点（同层级节点）之前，不会访问到距离更远的节点。 广度优先搜索算法通常是借助队列（Queue）来完成，算法思想遵循的一定的框架，并不复杂。 当然，广度优先搜索并不限于一定是树，也可以是图。比如说，下面是一张用于表示朋友之间关系的图，如果我们想要找到从 A 到 F 的最短路径，怎么找？ ## BFS练习：走迷宫 ### 题目描述 给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。 编程求从 'S' 出发，到 'G' 结束 ，至少需要移动多少次。 ### 输入格式 第一行包含两个整数 n 和 m。 接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。 ### 输出格式 输出一个整数，表示从 S 移动至 G 的最少移动次数。 ### 数据范围 1≤n, m≤100 #### 输入样例： ``` 5 5 S 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 G ``` #### 输出样例： ``` 8 ``` ### 题目分析 走迷宫是一个非常典型的用于学习和理解广度优先搜索（BFS）的例子。我们只需要按照前面的广度优先搜索的实现步骤来即可。 ### 代码实现 ```cpp #include #include #include using namespace std; const int MAXN = 100; // 迷宫大小 const int dx[4] = {1, 0, -1, 0}; // 按行（y）移动的方向 const int dy[4] = {0, 1, 0, -1}; // 按列（x）移动的方向 int n, m; // 迷宫的大小 char maze[MAXN][MAXN]; // 存储迷宫图 int sx, sy; // 起点坐标 int ex, ey; // 终点坐标 int d[MAXN][MAXN]; // 距离数组，存储每个节点到起点的最短距离 // 求解从起点到终点的最短距离 int bfs() { queue> que; // 初始化距离数组 memset(d, -1, sizeof(d)); // 起点距离为0 d[sx][sy] = 0; que.push(make_pair(sx, sy)); while (!que.empty()) { pair p = que.front(); que.pop(); if (p.first == ex && p.second == ey) { break; } for (int i = 0; i < 4; i++) { int nx = p.first + dx[i]; int ny = p.second + dy[i]; if (0 <= nx && nx < n && 0 <= ny && ny < m && maze[nx][ny] != 1 && d[nx][ny] == -1) { que.push(make_pair(nx, ny)); d[nx][ny] = d[p.first][p.second] + 1; } } } return d[ex][ey]; } int main() { cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> maze[i][j]; if (maze[i][j] == 'S') { sx = i; sy = j; } if (maze[i][j] == 'G') { ex = i; ey = j; } } } int res = bfs(); cout << res << endl; return 0; } ``` ## BFS练习： （待更新） ## 小结： （待更新） Source: https://cppguide.xyz/algorithm/search/index.mdx