ch07 - 深度优先搜索

蚂蚁走迷宫

• 知识点：路径搜索问题：

• 思路：本题是路径问题，简单的想法是 dfs 搜索所有合法路径

• 代码：

    #include <iostream>
    using namespace std;
    const int N = 8;
    char mp[N][N];
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    bool vis[N][N];
    int n, m, cnt;
    
    // 以 (x,y) 为起点进行 dfs 至 (n, m) 
    void dfs(int x, int y) {
    	if (x == n && y == m) {
    		cnt++;
    		return ;
    	}
    	for (int i = 0; i < 4; i++) {
    		int nx = x + dx[i], ny = y + dy[i];
    		if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
    		if (mp[nx][ny] != '.' || vis[nx][ny]) continue;
    		vis[nx][ny] = true;
    		dfs(nx, ny);
    		vis[nx][ny] = false;
    	} 
    }
    int main() {
    	cin >> n >> m;
    	for (int i = 1; i <= n; i++) {
    		for (int j = 1; j <= m; j++) cin >> mp[i][j];
    	}
    	vis[1][1] = true;
    	dfs(1, 1);
    	cout << cnt;
    	return 0;
    }
  

滑雪

• 知识点：路径问题、最优化问题、记忆化搜索

• 思路：

  • 本题是路径问题，简单的想法是 dfs 搜索所有合法路径，最长的就是答案。但一个网格中的路径数量是指数级的，这样做会超时。
  • 走到一个位置 (x, y) 时，实际上只关心 (x, y) 往后还能走多长，而不是对于所有到达 (x, y) 的路径，都要继续往后搜索所有走法。
  • dfs(x, y)：从 (x, y) 出发，往后最多还能走多长。
    • 下一步有 4 种选择，枚举 (x, y) 下一步能到达的位置 (cx, cy)，所有选择对应的结果取最大值就是 dfs(x, y) 的结果。
    • 要计算 $(x,y)\to (cx,cy)\to \cdots$ 的最大长度，首先有 $(x,y)$ 这一个位置，再调用 dfs(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)$ 。

• 代码：

  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 (从(x, y)走到(cx,cy)不合法) continue;
  		f[x][y] = max(f[x][y], dfs(cx, cy) + 1); // 从不同走法中取最长的
  	}
  	return f[x][y];
  }
  

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

行走棋游戏

• 知识点：路径问题、最优化问题、记忆化搜索

• 思路：

  • 本题是路径问题，简单的想法是 dfs 搜索所有合法路径
  • 走到一个位置 x 时，实际上只关心 x 往后还的最大得分
  • dfs(x)：从 x 出发，走到 > n 的位置的最大得分。
    • 下一步只有有 1 种选择，x 下一步能到达的位置 x + a[x]，所以dfs(x) = a[x] + dfs(x + a[x])
  • 用记忆化搜索，dp[x] 记录 dfs(x) 的结果，只要 dp[x] 已经算过了，再次搜索到 dfs(x) 时可以直接返回结果。
  • 每一个状态 (x) 只需要被计算一次，时间复杂度 $O(n)$ 。

• 代码：

    // dfs(x):求解从位置 x 出发到达结束位置的最分数 
    LL dfs(int x){
    	if(x > n) return 0;
    	if(dp[x] != -1) return dp[x]; 
    	// 如果dp[x]中不是-1，则说明已经求解过答案，不需要再次求解
    	return  dp[x] = a[x] + dfs(x + a[x]);
    }
  

水桶装水

• 知识点：DFS 解决判断问题、状态标记优化

• 思路：

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

• 代码：

  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);
      // 思考如何列举六种后继状态并返回结果
  }
  

Mother’s Milk

• 知识点：DFS 解决判断问题、状态标记优化

• 思路：

  • 需要搜索的状态比较明显是三个桶当前各自的牛奶量。
  • 在搜索过程中，用数组将能达到的状态标记为 true，最后枚举 a 桶为空的所有状态，对于能达到的状态，从小到大输出 c 桶所剩量即可。
  • dfs 过程中，从哪个桶倒到哪个桶有多种可能，可以手动列举出来

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) 这个位置，这样可以保证每个位置只被搜索一次。

• 代码：

  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) {
  		// 输出结果
  		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() {
      // 省略输入
  	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 范围内。

• 代码：

  int dfs(int x, int y, int t) {
  	if (t == 0) { // 时间用完了，到达终点说明是一条满足要求的路径，方案数为1，没到终点则是0
  		return (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];
  }
  

• 拓展：

  • 为什么 dfs(x, y, t) 要定义为从 (x, y) 位置出发，经过 t 秒到达终点的路径方案数？
  • 能不能定义为从起点出发，经过 t 秒到达 (x, y) 位置的方案数？思考并尝试。