当前位置：首页 > ds >正文

ch07 题解

ds 2025/7/12 9:47:27

ch07 - 深度优先搜索

走迷宫

知识点：DFS 解决网格路径问题
思路：
- 对于每个位置，都有往上下左右四个方向移动的选择，且迷宫规模较小，可用 DFS 暴力罗列所有方案。
- 函数 dfs(x, y) 的功能：当前路径已经从 (1, 1) 走到 (x, y) 位置，要搜索从 (x, y) 走到 (n, m) 的所有方案。
  - 从 (x, y) 走到 (n, m) 这件事情分为两个步骤：先从 (x, y) 走一步到下一个位置 (cx, cy)，再搜索从 (cx, cy) 走到 (n, m) 的所有方案。
  - 递归的终止：当 x == n && y == m ，已经到达终点，表示当前找到了一条从 (1, 1) 走到 (n, m) 的路径。
- 时间复杂度：每个位置有 4 种移动选择（因为不能往来时的方向走，实际是 3 种），一条路径上最多有 $nm$ 个位置，根据乘法原理，复杂度为 $O(3^{nm})$ 。
  - 考虑到同一条路径不能走重复位置，也不能越过边界，所以很多位置的移动选择 < 3 种，很多路径也没有 $nm$ 个位置， $O(3^{nm})$ 的复杂度远远跑不满，但指数级的复杂度仍然非常高。
  - 得到的启示是，对于“罗列所有路径”的解法，复杂度是指数级的，而不是简单的 $O (nm)$ ，只适用于规模很小的迷宫。
- 思考：如果只能往下、往右移动，有什么更高效的解法？

代码：

const int N = 8;
char ch[N][N];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
bool inPath[N][N]; // inPath[x][y]标记(x, y)位置是否在当前路径中
int n, m, cnt;
void dfs(int x, int y) {if (x == n && y == m) {cnt++;return;}for (int i = 0; i < 4; i++) {int cx = x + dx[i], cy = y + dy[i];if (cx < 1 || cx > n || cy < 1 || cy > m || ch[cx][cy] != '.' || inPath[cx][cy]) continue;inPath[cx][cy] = true;dfs(cx, cy);inPath[cx][cy] = false; // 下一次循环换别的位置走，(cx, cy)变成不在路径中}
}
int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) cin >> ch[i][j];}inPath[1][1] = true; // 注意标记起点在路径中dfs(1, 1);cout << cnt << '\n';return 0;
}

整数替换

知识点：DFS 解决判断问题、状态标记优化
思路：
- dfs(x)：判断能否将 x 变为 m。
- 将 x 下一步能替换的数字称为 x 的后继状态
  - 如果 x 的后继状态能变为 m，那么 x 也能变为 m；
  - 如果 x 的后继状态都不能变为 m，那么 x 也不能变为 m。
- 递归的终止：
  - x == m 时，达到目标状态，返回 true；
  - x == 1 时，下一步可以替换为 0 或 2，替换为 2 再下一步又变回 1，所以 x == 1 时只能变为 <= 2 的数字。
- 本题的 DFS 有可能会重复搜索到同一个状态
  - 一个方法是用数组 vis[] 标记搜索过的状态，一个状态重复被搜索到时，说明它到达不了目标，直接返回 false。
  - 因为 x 经过替换总是很快缩小一半（奇数下一步是偶数，再下一步就缩小一半），所以即使不标记，搜索的状态数量也是很少的。

代码：

// 写法一：不标记，允许多次搜索同一个状态
bool dfs(int x) {if (x == m) return true; // 目标状态if (x == 1) return m == 2; // 1变换不出>2的数字// 偶数情况：后继状态能达到m，相当于当前状态也能达到m，所以直接return下一个状态的返回值if (x % 2 == 0) return dfs(x / 2);// 奇数情况：两个后继状态有一个是true，dfs(x)就可以返回true// 并且根据逻辑或||的“短路”特性，dfs(x - 1)是true，则不会再执行dfs(x + 1)else return dfs(x - 1) || dfs(x + 1);
}// 写法二：标记搜索过的状态
bool dfs(int x) {if (x == m) return true;// if (x == 1) return m == 2;// 优化，加上这两句：if (vis[x]) return false; // 如果x能到达m，那么函数只有return没有递进搜索了，所以能第2次遇到x，说明x不能到达mvis[x] = true;if (x % 2 == 0) return dfs(x / 2);else return dfs(x - 1) || dfs(x + 1);
}

整数替换 II

知识点：DFS 解决最优化问题、记忆化搜索
思路：
- dfs(x)：将 x 变为 1 的最少步数。
- 如果 x 是偶数，先通过 1 步操作将 x 变为 x / 2，再计算 x / 2 变为 1 的最少步数，对应的步数是 1 + dfs(x / 2) 。
- 如果 x 是奇数，有 - 1 和 + 1 两种选择，在两种选择对应的步数中取最优解，1 + min(dfs(x - 1), dfs(x + 1)) 。
- 递归的终止：x == 1 时不需要变换了，0 步。
- 与“整数替换”一样，本题也有可能重复搜索同一个状态，可以通过数组标记搜索过的状态，同时还要记录该状态对应的结果（步数），这个技巧也称为“记忆化搜索”。
  - 将 f 数组赋一个不会在结果中出现的初始值，比如 -1 或无穷大值 0x3f3f3f3f ，表示还没搜索到，其他值则表示搜索过，记录了结果。

代码：

// 写法一：不标记
int dfs(int x) {if (x == 1) return 0;if (x % 2 == 0) return dfs(x / 2) + 1;return min(dfs(x - 1), dfs(x + 1)) + 1;
}// 写法二：标记搜索过的状态，记录结果
const int N = 1000010, INF = 0x3f3f3f3f;
int f[N]; // f[x]表示从x变到1的最少步数
int dfs(int x) {if (x == 1) return 0;if (f[x] != INF) return f[x]; // 记忆化，搜索过了直接返回结果if (x % 2 == 0) return f[x] = dfs(x / 2) + 1;return f[x] = min(dfs(x - 1), dfs(x + 1)) + 1;
}

单词拼接

知识点：DFS 解决判断问题、状态标记优化、字符串
思路：
- 需要逐步拼接出目标串 s，搜索的状态可以用“已经拼接出的字符串 t”表示，那么字符串 s 后面还未拼接出来的部分就是接下来要完成的任务。
- dfs(t)：已经拼接出字符串 t，判断往 t 后面继续拼接能否得到目标串 s 。
- 枚举接下来要往 t 后面拼接的字符串 w[i]，t 与 w[i] 拼接后，必须是 s 的前缀，最终才有可能拼接出 s。
  - 如果 t.size() + w[i].size() > s.size()，那么 t 与 w[i] 拼接后比 s 还长，不是 s 的前缀。
  - t 接下来需要的长度为 w[i].size() 的字符串是 need = s.substr(t.size(), w[i].size()) 。如果 w[i] == need，那么可以尝试往 t 后面拼接 w[i]，调用 dfs(t + w[i]) 判断后继状态能否达到目标。
- 在 t 的后继状态中，有一个能达到目标，说明 t 是能达到目标的，返回 true。

代码：

bool dfs(string t) {if (t == s) return true;for (int i = 0; i < n; i++) {// 跳过t+w[i]不是s的前缀的情况if (t.size() + w[i].size() > s.size() || s.substr(t.size(), w[i].size()) != w[i]) continue;if (dfs(t + w[i])) return true;}return false;
}

拓展：
- 实际上参数 t 肯定是 s 的前缀，可以用更简洁的形式表示这个状态，参数传递 t 的长度即可，这样参数只要传递一个 int 变量，不用传递字符串，提高效率。
- 本题有可能多次搜索到同一个状态，如果有严格的测试数据，以上写法是会超时的，思考如何用数组标记搜索过的状态进行优化。

滑雪

知识点：路径问题、最优化问题、记忆化搜索
思路：
- 本题是路径问题，简单的想法是 dfs 搜索所有合法路径，最长的就是答案。但一个网格中的路径数量是指数级的，这样做会超时。
- 走到一个位置 (x, y) 时，实际上只关心 (x, y) 往后还能走多长，而不是对于所有到达 (x, y) 的路径，都要继续往后搜索所有走法。
- dfs(x, y)：从 (x, y) 出发，往后最多还能走多长。
  - 下一步有 4 种选择，枚举 (x, y) 下一步能到达的位置 (cx, cy)，所有选择对应的结果取最大值就是 dfs(x, y) 的结果。
  - 要计算 $y)\to (cx, cy)\to \cdots$ 的最大长度，首先有 $(x, y)$ 这一个位置，再调用 dfs(cx, cy) 得到 $(cx,cy)→⋯(cx,cy)\to \cdots$ 的最大长度，所以这种选择对应的结果是 1 + dfs(cx, cy) 。
- 用记忆化搜索，f[x][y] 记录 dfs(x, y) 的结果，只要 f[x][y] 已经算过了，再次搜索到 dfs(x, y) 时可以直接返回结果。
- 每一个状态 (x, y) 只需要被计算一次，时间复杂度 $O (RC)$ 。
代码：

const int dx[] = {0, 0, -1, 1};
const int dy[] = {1, -1, 0, 0};
int f[maxn][maxn], c, r;
int a[maxn][maxn];
int dfs(int x, int y) {if (f[x][y]) return f[x][y];f[x][y] = 1;  // 从(x,y)出发，最少也有它本身一个位置的长度for (int i = 0; i < 4; i++) {int cx = x + dx[i], cy = y + dy[i];if (cx < 0 || cx >= r || cy < 0 || cy >= c || a[cx][cy] >= a[x][y])continue;f[x][y] = max(f[x][y], dfs(cx, cy) + 1);  // 从不同走法中取最长的}return f[x][y];
}
int main() {cin >> r >> c;for (int i = 0; i < r; i++) {for (int j = 0; j < c; j++) cin >> a[i][j];}int ans = 0;for (int i = 0; i < r; i++) {for (int j = 0; j < c; j++) {ans = max(ans, dfs(i, j));}}cout << ans;return 0;
}

易错点：注意最长的路径不一定是从左上角出发的，根据 dfs(x, y) 的功能，思考 main() 函数怎么写才能得到正确答案。

水桶装水

知识点：DFS 解决判断问题、状态标记优化
思路：
- dfs(a, b)：当前第一个桶的水量是 a，第二个桶的水量是 b，能否达成目标。
- 只要 (a, b) 的后继状态中有一个能达成目标，那么 (a, b) 也能达成目标。根据题目的操作，列举所有后继状态：
  - 例如装满第一个桶，那么后继状态是 (x, b)。
  - 例如要把第一个桶的水倒入第二个桶，先计算要倒过去的水量 d，取决于第一个桶“能倒出多少水”，以及第二个桶“能接收多少水”，d = min(a, y - b)，后继状态是 (a - d, b + d) 。
  - 分别对两个水桶执行三种操作，总共有六种后继状态。
- 水倒来倒去，有可能多次搜索到同一个状态，需要用数组标记搜索过的状态。
代码：


const int maxn = 1010;
bool vis[maxn][maxn];
int x, y, z;
bool dfs(int a, int b) {if (a + b == z) return true;if (vis[a][b]) return false;vis[a][b] = true;// 第一个桶往第二个桶倒水，转移水量d1。第二个桶往第一个桶倒水，转移水量d2。int d1 = min(a, y - b), d2 = min(b, x - a);int cx[6] = {x, a, 0, a, a - d1, a + d2};int cy[6] = {b, y, b, 0, b + d1, b - d2};// 思考如何列举六种后继状态并返回结果for (int i = 0; i < 6; ++i) {if (dfs(cx[i], cy[i])) return 1;}return 0;
}int main() {cin >> x >> y >> z;if (dfs(0, 0))cout << "Yes\n";elsecout << "No\n";return 0;
}

Mother’s Milk

知识点：DFS 解决判断问题、状态标记优化
思路：
- 需要搜索的状态比较明显是三个桶当前各自的牛奶量。
- 在搜索过程中，用数组将能达到的状态标记为 true，最后枚举 a 桶为空的所有状态，对于能达到的状态，从小到大输出 c 桶所剩量即可。
- dfs 过程中，从哪个桶倒到哪个桶有多种可能，手动列举比较麻烦，也容易写错，可以两层循环枚举。

代码：

const int N = 21;
bool f[N][N][N];
int c[3], a[3]; // c[i]表示第i个桶的容量，a[i]表示当前状态第i个桶的牛奶量
// 从第i个桶倒到第j个桶
void pour(int i, int j) {int d = min(a[i], c[j] - a[j]);a[i] -= d;a[j] += d;
}
// 当前搜索状态是(a[0], a[1], a[2])
void dfs() {if (f[a[0]][a[1]][a[2]]) return ; // 记忆化f[a[0]][a[1]][a[2]] = true;int b[3];memcpy(b, a, sizeof(a)); // b用来临时储存a数组的值for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {if (i == j) continue;pour(i, j);dfs();memcpy(a, b, sizeof(b)); // pour()中a数组的值被修改，此处要改回来}}
}
int main() {cin >> c[0] >> c[1] >> c[2];a[2] = c[2];dfs();for (int i = 0; i <= c[2]; i++) { // c桶所剩量for (int j = 0; j <= c[2] - i; j++) { // b桶所剩量if (f[0][j][i]) {cout << i << " ";break;}}}return 0;
}

Cows on Skates

知识点：网格路径问题、DFS 搜索优化
思路：
- 本题属于需要记录路径的网格路径问题，但网格规模较大，路径数量太多，罗列所有路径会超时。
- 优化1：题目中路径可以走重复位置，但仍然可以限制同一条路径不允许走重复位置，因为对于“走到终点”这个目标来说，绕圈是没有意义的。
- 优化2：如果搜索过一个位置 (x, y) ，这个位置无法到终点，那么其他路径也无需再尝试这个位置了。
  - 因为 (x, y) 无法到终点分为 2 种情况：一是被障碍挡住，那么显然这个位置没有前途，其他路径也无需走这里；二是被路径中的其他位置 (x1, y1) 挡住，那么 (x1, y1) 比 (x, y) 更接近终点，应该回退到 (x1, y1) 去搜索，其他路径也无需搜索这个比 (x1, y1) 更劣的位置。
  - 所以不是用 inPath[x][y] 标记 (x, y) 有没有在当前路径中，可以用 vis[x][y] 标记有没有搜索过 (x, y) 这个位置，这样可以保证每个位置只被搜索一次。
代码：

const int N = 120;
const int dx[4] = { -1, 1, 0, 0 };
const int dy[4] = { 0, 0, -1, 1 };
char ch[N][N];  // 输入的迷宫
int n, m;       // 迷宫的行数和列数
struct P {int x, y;
} path[N * N];   // 记录状态（路径）的数组
bool vis[N][N];  // vis[x][y]标记(x,y)这个位置有没有搜索过
// (x,y)是当前状态（路径）的末尾位置，len是当前路径的长度
void dfs(int x, int y, int len) {if (vis[x][y])return;vis[x][y] = true;if (x == n && y == m) {for (int i = 1; i <= len; i++) {cout << path[i].x << " " << path[i].y << '\n';}return;}for (int i = 0; i < 4; i++) {int cx = x + dx[i], cy = y + dy[i];if (cx < 1 || cx > n || cy < 1 || cy > m || ch[cx][cy] != '.')continue;path[len + 1] = { cx, cy };  // 新位置放入路径中dfs(cx, cy, len + 1);}
}int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> ch[i][j];}}path[1] = { 1, 1 };  // 注意起点放入路径中dfs(1, 1, 1);return 0;
}

Cow Travelling

知识点：路径问题、记忆化搜索、基本计数原理
思路：
- 与”滑雪“类似，不能去罗列所有路径，会超时。要有将原问题分解为子问题解决的思维，重复的子问题通过记忆化搜索避免重复计算，以此提高效率。
- 关键信息是位置和时间，那么状态中应该包含位置和时间。
- dfs(x, y, t)：从 (x, y) 位置出发，经过 t 秒到达终点的路径方案数。
- 考虑下一步到达的位置 (cx, cy)，有上下左右四种走法，分为四类情况统计从 (x, y) 出发的路径方案数：
  - 从 (x, y) 走到 (cx, cy) 用掉了 1 秒，那么只剩下 t - 1 秒从 (cx, cy) 走到终点，调用 dfs(cx, cy, t - 1) 得到这一类走法的方案数。
  - 分类统计，应用加法原理。
- 花同样的时间，走不同路径，是有可能到达同一个位置的，所以会重复搜索到同一个状态，需要记忆化搜索。
- 答案的范围：因为题目输入的时间 T 最大是 15，每一步最多有 4 种走法选择，最多走 15 步，根据乘法原理，路径方案数不会超过 $4^{15}$ ，在 int 范围内。
代码：

const int N = 110;
const int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
int f[N][N][16];
char ch[N][N];
int n, m, T, r1, c1, r2, c2; int dfs(int x, int y, int t) {if (t == 0) { // 时间用完了，到达终点说明是一条满足要求的路径，方案数为1，没到终点则是0return (x == r2 && y == c2 ? 1 : 0);}if (f[x][y][t] != -1) return f[x][y][t]; // 方案数不会是-1，用-1作为f的初始值表示没搜索到这个状态f[x][y][t] = 0;for (int i = 0; i < 4; i++) {int cx = x + dx[i], cy = y + dy[i];if (cx < 1 || cx > n || cy < 1 || cy > m || ch[cx][cy] == '*') continue;f[x][y][t] += dfs(cx, cy, t - 1); // 分为往上下左右四类走法，分类用加法原理}return f[x][y][t];}int main() {memset(f, -1, sizeof(f));cin >> n >> m >> T;for (int i = 1; i <= n; i++) {cin >> ch[i] + 1;}cin >> r1 >> c1 >> r2 >> c2;cout << dfs(r1, c1, T) << '\n';return 0;
}