devbox
我家自动化
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【六十】【算法分析与设计】用一道题目解决dfs深度优先遍历，dfs中节点信息，dfs递归函数模板进入前维护出去前回溯，唯一解的剪枝飞升返回值true

作者：我家自动化 | 2024-04-21 16:00:21

赞

踩

【六十】【算法分析与设计】用一道题目解决dfs深度优先遍历，dfs中节点信息，dfs递归函数模板进入前维护出去前回溯，唯一解的剪枝飞升返回值true

路径之谜

题目描述

小明冒充X星球的骑士,进入了一个奇怪的城堡。

城堡里边什么都没有,只有方形石头铺成的地面。

假设城堡地面是n×n个方格。如下图所示。

1e8908abd7eb470083d000bb49a7bab3.png

按习俗,骑士要从西北角走到东南角。可以横向或纵向移动,但不能斜着音走,也不能跳跃。每走到一个新方格,就要向正北

方和正西方各射一箭。(城堡的西墙和北墙内各有12个靶子)同一个方格只允许经过一次。但不必走完所有的方格。如果只

给出靶子上箭的数目,你能推断出骑士的行走路线吗?有时是可以的,比比如上图中的例子。

本题的要求就是已知箭靶数字,求骑士的行走路径(测试)数据保证路径唯一)

输入描述

第一行一个整数N(0<N<20),表示地面有NXN个方格。

第二行N个整数,空格分开,表示北边的箭靶上的数字(自西向东)

第三行N个整数,空格分开,表示西边的箭靶上的数字(自北向南)

输出描述

输出一行若干个整数,表示骑士路径。

为了方便表示,我们约定每个小格子用一个数字代表,从西北角开始编号号:0,1,2,3

比如,上图中的方块编号为:

0 1 2 3

4 5 6 7

8 9 10 11

12 13 14 15

输入输出样例

示例

输入

4

2 4 3 4

4 3 3 3

输出

0 4 5 1 2 3 7 11 10 9 13 14 15

运行限制

最大运行时间:5s

最大运行内存:256M

12c651f1c7234b9988867f9e74ddcf2e.png

暴力递归

1.

定义dfs(i,j)表示当前节点坐标。

假设入口位置坐标是（1，1），往下是row行，往右是col列。

定义row记录从入口到当前节点这条路径西边靶子的数量，row[1]表示西边第一个靶子上箭的数量，row[2]表示西边第二个靶子上箭的数量...以此类推。

定义col记录从入口到当前节点这条路径北边靶子的数量，col[1]表示北边第一个靶子上箭的数量，col[2]表示北边第二个靶子上箭的数量...以此类推。

定义path记录从入口到当前节点的路径信息。

定义visit记录从入口到当前节点，这条路径，当前所有位置访问情况，访问过为true，没有被访问过false。

2.

也就是当前节点的信息不止有(i,j)还有path，row，col，visit四个变量共同组成。

3.

dfs内部逻辑，进入当前节点的时候，维护当前节点的所有信息。

离开当前节点返回之前，回溯，消除当前节点维护的所有信息。

4.

夹在中间的就是计算逻辑，写代码的时候先把首位维护和回溯写掉，然后在中间加主要逻辑。

 
  1. void dfs(int i, int j) {
  2.     visit[i][j] = true;
  3.     row[i]++;
  4.     col[j]++;
  5.     path.push_back((i - 1) * n + (j - 1));//数学推导不细说，找规律
  6.     //添加主要逻辑
  7.     path.pop_back();
  8.     row[i]--;
  9.     col[j]--;
  10.     visit[i][j] = false;
  11. }

 

5.

06e70e01efad4a72a6044d401aaf9bae.png

对于当前节点，下一个遍历的节点位置有四个，上下左右，但是有一些位置需要剪枝。

规则是，第一，这四个位置首先不能越界，第二，这四个位置不能被访问过，被访问过表示已经是路径上的点，已经走过了。如果满足要求就可以dfs进入下一节点。

 
  1. void dfs(int i, int j) {
  2.     visit[i][j] = true;
  3.     row[i]++;
  4.     col[j]++;
  5.     path.push_back((i - 1) * n + (j - 1));
  6.  
  7.     for (int k = 0; k < 4; k++) {
  8.         int x = i + dx[k], y = j + dy[k];
  9.         if (x >= 1 && x <= n && y >= 1 && y <= n && !visit[x][y]) {
  10.             dfs(x, y);
  11.         }
  12.     }
  13.  
  14.     path.pop_back();
  15.     row[i]--;
  16.     col[j]--;
  17.     visit[i][j] = false;
  18. }

 

6.

思考递归出口，递归出口是当你走到出口的时候，即i==n&&j==n。

此时遍历row和col，看看靶子上箭的数量是不是和aim_row,aim_col目标值对上。

如果对上了此时path里面存放的就是我们要的路径，打印出来即可。

如果没有对上就返回，不需要再进入下一节点了。

返回前注意需要回溯，消除维护操作。

 
  1. void dfs(int i, int j) {
  2.     visit[i][j] = true;
  3.     row[i]++;
  4.     col[j]++;
  5.     path.push_back((i - 1) * n + (j - 1));
  6.  
  7.     if (i == n && j == n) {
  8.         int flag = 1;
  9.         for (int i = 1; i <= n; i++) {
  10.             if (row[i] != aim_row[i] || col[i] != aim_col[i]) flag = 0;
  11.         }
  12.         if (flag == 1) {
  13.             for (auto& x : path) cout << x << " ";
  14.         }
  15.                 path.pop_back();
  16.                 row[i]--;
  17.                 col[j]--;
  18.                 visit[i][j] = false;
  19.                 return;
  20.         
  21.     }
  22.     for (int k = 0; k < 4; k++) {
  23.         int x = i + dx[k], y = j + dy[k];
  24.         if (x >= 1 && x <= n && y >= 1 && y <= n && !visit[x][y]) {
  25.             dfs(x, y);
  26.         }
  27.     }
  28.  
  29.     path.pop_back();
  30.     row[i]--;
  31.     col[j]--;
  32.     visit[i][j] = false;
  33. }

 

代码1

7.

此时得到的代码如下，

 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int n; // 定义n表示城堡地面是n×n个方格
  6. vector<int> path; // 用于记录骑士的行走路径
  7. vector<int> row; // 用于记录每行射出的箭的数量
  8. vector<int> col; // 用于记录每列射出的箭的数量
  9. vector<vector<int>> visit; // 记录某个格子是否被访问过
  10. int dx[4] = { 1,-1,0,0 }; // 方向数组，用于实现上下左右移动
  11. int dy[4] = { 0,0,1,-1 };
  12. vector<int> aim_col; // 存储每列应该射出的箭的目标数量
  13. vector<int> aim_row; // 存储每行应该射出的箭的目标数量
  14.  
  15. // 深度优先搜索（DFS）函数，用于尝试所有可能的路径
  16. void dfs(int i, int j) {
  17.     visit[i][j] = true; // 标记当前格子为已访问
  18.     row[i]++; // 当前行的箭数增加
  19.     col[j]++; // 当前列的箭数增加
  20.     path.push_back((i - 1) * n + (j - 1)); // 将当前格子编号加入路径
  21.  
  22.     // 如果到达东南角，并且每行每列的箭数都符合目标
  23.     if (i == n && j == n) {
  24.         int flag = 1;
  25.         for (int i = 1; i <= n; i++) {
  26.             if (row[i] != aim_row[i] || col[i] != aim_col[i]) flag = 0;
  27.         }
  28.         if (flag == 1) {
  29.             for (auto& x : path) cout << x << " "; // 如果路径有效，输出这条路径
  30.         }
  31.         path.pop_back();
  32.         row[i]--;
  33.         col[j]--;
  34.         visit[i][j] = false;
  35.         return;
  36.     }
  37.  
  38.     // 尝试向四个方向移动
  39.     for (int k = 0; k < 4; k++) {
  40.         int x = i + dx[k], y = j + dy[k];
  41.         if (x >= 1 && x <= n && y >= 1 && y <= n && !visit[x][y]) {
  42.             dfs(x, y);
  43.         }
  44.     }
  45.  
  46.     // 回溯，撤销当前步骤的影响
  47.     path.pop_back();
  48.     row[i]--;
  49.     col[j]--;
  50.     visit[i][j] = false;
  51. }
  52.  
  53. int main() {
  54.     cin >> n; // 读入n的大小
  55.     aim_col.resize(n + 1);
  56.     for (int i = 1; i <= n; i++) cin >> aim_col[i]; // 读入每列的目标箭数
  57.     aim_row.resize(n + 1);
  58.     for (int i = 1; i <= n; i++) cin >> aim_row[i]; // 读入每行的目标箭数
  59.  
  60.     row.resize(n + 1);
  61.     col.resize(n + 1);
  62.     visit = vector<vector<int>>(n + 1, vector<int>(n + 1));
  63.  
  64.     dfs(1, 1); // 从西北角开始进行深度优先搜索
  65.  
  66.     return 0;
  67. }

运行结果如下，

09945d723f644fc8a58e3ff7d6749755.png

剪枝1：唯一解找到即返回true（飞升）

8.

大部分运行超时，说明代码整体逻辑没有问题，但是剪枝操作没有做好。

重新思考剪枝操作。

题目中测试数据保证了路径的唯一性，说明我们只要找到了最终答案，就不需要回溯，后面的操作都不需要，找到最终答案就一路飞升回到第一层递归返回。

修改dfs的返回值，不使用void返回值，而使用int或者bool，意思是如果当前找到了就返回true，没有找到就返回false。

修改完返回值还需要修改进入下一层递归的代码，不能直接是dfs，而是if(dfs(x, y)) return true;。

如果返回值是true说明找到了，如果找到了什么都不用管，直接返回true。

每一层节点都接收这个信息，有没有完成工作，有没有找到路径？找到了就可以不用再工作了，直接返回。

还需要修改递归出口的逻辑，flag==1说明找到了，打印完路径后直接返回true。

 
  1. int dfs(int i, int j) {
  2.     visit[i][j] = true;
  3.     row[i]++;
  4.     col[j]++;
  5.     path.push_back((i - 1) * n + (j - 1));
  6.  
  7.     if (i == n && j == n) {
  8.         int flag = 1;
  9.         for (int i = 1; i <= n; i++) {
  10.             if (row[i] != aim_row[i] || col[i] != aim_col[i]) flag = 0;
  11.         }
  12.         if (flag == 1) {
  13.             for (auto& x : path) cout << x << " ";
  14.             return true;
  15.         }
  16.             path.pop_back();
  17.             row[i]--;
  18.             col[j]--;
  19.             visit[i][j] = false;
  20.             return;
  21.     }
  22.     for (int k = 0; k < 4; k++) {
  23.         int x = i + dx[k], y = j + dy[k];
  24.         if (x >= 1 && x <= n && y >= 1 && y <= n && !visit[x][y]) {
  25.              if(dfs(x, y)) return true;
  26.         }
  27.     }
  28.  
  29.     path.pop_back();
  30.     row[i]--;
  31.     col[j]--;
  32.     visit[i][j] = false;
  33.     
  34.     return false;
  35. }

 

代码2

9.

 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int n; // 城堡地面为n×n个方格的大小
  6. vector<int> path; // 存储骑士的行走路径
  7. vector<int> row; // 每行射箭的次数
  8. vector<int> col; // 每列射箭的次数
  9. vector<vector<int>> visit; // 标记方格是否访问过
  10. int dx[4] = { 1,-1,0,0 }; // x方向的移动：下，上，不动，不动
  11. int dy[4] = { 0,0,1,-1 }; // y方向的移动：不动，不动，右，左
  12. vector<int> aim_col; // 目标，每列应射箭的次数
  13. vector<int> aim_row; // 目标，每行应射箭的次数
  14.  
  15. // 深度优先搜索（DFS）算法，i和j表示当前位置
  16. int dfs(int i, int j) {
  17.     visit[i][j] = true; // 标记当前方格为已访问
  18.     row[i]++; // 当前行的射箭次数增加
  19.     col[j]++; // 当前列的射箭次数增加
  20.     path.push_back((i - 1) * n + (j - 1)); // 将当前方格的编号加入到路径中
  21.  
  22.     // 检查是否到达右下角，并且所有行和列的射箭次数都符合目标
  23.     if (i == n && j == n) {
  24.         int flag = 1; // 用于检查是否所有行和列的射箭次数都匹配
  25.         for (int i = 1; i <= n; i++) {
  26.             if (row[i] != aim_row[i] || col[i] != aim_col[i]) flag = 0;
  27.         }
  28.         if (flag == 1) {
  29.             for (auto& x : path) cout << x << " "; // 如果匹配，输出路径
  30.             cout << endl; // 输出换行
  31.             return true; // 返回找到有效路径
  32.         }
  33.     }
  34.  
  35.     // 尝试四个可能的移动方向
  36.     for (int k = 0; k < 4; k++) {
  37.         int x = i + dx[k], y = j + dy[k];
  38.         if (x >= 1 && x <= n && y >= 1 && y <= n && !visit[x][y]) {
  39.             if (dfs(x, y)) return true; // 递归调用dfs
  40.         }
  41.     }
  42.  
  43.     // 回溯，撤销当前步骤
  44.     path.pop_back();
  45.     row[i]--;
  46.     col[j]--;
  47.     visit[i][j] = false;
  48.  
  49.     return false; // 没有找到有效路径
  50. }
  51.  
  52. int main() {
  53.     cin >> n;
  54.     aim_col.resize(n + 1);
  55.     for (int i = 1; i <= n; i++) cin >> aim_col[i]; // 输入每列的目标射箭次数
  56.     aim_row.resize(n + 1);
  57.     for (int i = 1; i <= n; i++) cin >> aim_row[i]; // 输入每行的目标射箭次数
  58.  
  59.     row.resize(n + 1);
  60.     col.resize(n + 1);
  61.     visit = vector<vector<int>>(n + 1, vector<int>(n + 1, false)); // 初始化访问标记数组
  62.  
  63.     dfs(1, 1); // 从(1,1)开始深度优先搜索
  64.  
  65.     return 0;
  66. }

运行结果如下，

a94fedcc6cc74cd2bcb5c4451d3fd699.png

剪枝2：靶子箭数量小于目标靶子箭数量

10.

说明这个剪枝操作微不足道，没什么用。

继续思考其他剪枝操作，我们发现如果到了一个节点，如果row，col中有一个靶子的箭数量大于目标靶子的箭数量，后面的路径都不可能是最终答案。

因为靶子上箭的数量不可能减少只能增加，所以到出口之前，如果是正确路径，靶子数量一定小于目标靶子数量。

所以如果靶子箭数量大于目标靶子箭数量，直接返回。

 
  1. int dfs(int i, int j) {
  2.     visit[i][j] = true;
  3.     row[i]++;
  4.     col[j]++;
  5.     path.push_back((i - 1) * n + (j - 1));
  6.  
  7.     int flag1 = 1;
  8.     for (int i = 1; i <= n; i++) {
  9.         if (row[i] > aim_row[i] || col[i] > aim_col[i]) {
  10.             flag1 = 0;
  11.             break;
  12.         }
  13.     }
  14.     if (flag1 == 0) {
  15.         path.pop_back();
  16.         row[i]--;
  17.         col[j]--;
  18.         visit[i][j] = false;
  19.  
  20.         return false;
  21.     }
  22.  
  23.     if (i == n && j == n) {
  24.         int flag = 1;
  25.         for (int i = 1; i <= n; i++) {
  26.             if (row[i] != aim_row[i] || col[i] != aim_col[i]) {
  27.                 flag = 0;
  28.                 break;
  29.             }
  30.         }
  31.         if (flag == 1) {
  32.             for (auto& x : path) cout << x << " ";
  33.             return true;
  34.         }else{
  35.         path.pop_back();
  36.         row[i]--;
  37.         col[j]--;
  38.         visit[i][j] = false;
  39.  
  40.         return false;
  41.     }
  42.     }
  43.  
  44.     for (int k = 0; k < 4; k++) {
  45.         int x = i + dx[k], y = j + dy[k];
  46.         if (x >= 1 && x <= n && y >= 1 && y <= n && !visit[x][y]) {
  47.             if (dfs(x, y)) return true;
  48.         }
  49.     }
  50.  
  51.     path.pop_back();
  52.     row[i]--;
  53.     col[j]--;
  54.     visit[i][j] = false;
  55.  
  56.     return false;
  57. }

 

代码3

 
  1. #include <iostream>
  2. #include<bits/stdc++.h>  // 引入常用库，包含STL等
  3. using namespace std;
  4.  
  5. // 定义全局变量
  6. int n;  // 地图大小
  7. vector<int> path;  // 记录路径
  8. vector<int> row;  // 记录每行走过的次数
  9. vector<int> col;  // 记录每列走过的次数
  10. vector<vector<int>> visit;  // 访问标记数组
  11. int dx[4] = { 1,-1,0,0 };  // 方向数组，表示行的移动
  12. int dy[4] = { 0,0,1,-1 };  // 方向数组，表示列的移动
  13. vector<int> aim_col;  // 目标列的箭数
  14. vector<int> aim_row;  // 目标行的箭数
  15.  
  16. // 深度优先搜索函数
  17. int dfs(int i, int j) {
  18.     visit[i][j] = true;  // 标记当前单元格已访问
  19.     row[i]++;  // 增加当前行的计数
  20.     col[j]++;  // 增加当前列的计数
  21.     path.push_back((i - 1) * n + (j - 1));  // 记录路径
  22.  
  23.     int flag1 = 1;
  24.     // 检查所有行列是否满足条件
  25.     for (int i = 1; i <= n; i++) {
  26.         if (row[i] > aim_row[i] || col[i] > aim_col[i]) {
  27.             flag1 = 0;
  28.             break;
  29.         }
  30.     }
  31.     if (flag1 == 0) {  // 如果条件不满足，则回退操作
  32.         path.pop_back();
  33.         row[i]--;
  34.         col[j]--;
  35.         visit[i][j] = false;
  36.         return false;
  37.     }
  38.  
  39.     // 检查是否到达最后一个方格
  40.     if (i == n && j == n) {
  41.         int flag = 1;
  42.         for (int i = 1; i <= n; i++) {
  43.             if (row[i] != aim_row[i] || col[i] != aim_col[i]) {
  44.                 flag = 0;
  45.                 break;
  46.             }
  47.         }
  48.         if (flag == 1) {  // 如果满足最终条件，输出路径
  49.             for (auto& x : path) cout << x << " ";
  50.             return true;
  51.         } else {  // 否则，进行回退操作
  52.             path.pop_back();
  53.             row[i]--;
  54.             col[j]--;
  55.             visit[i][j] = false;
  56.             return false;
  57.         }
  58.     }
  59.  
  60.     // 遍历四个方向
  61.     for (int k = 0; k < 4; k++) {
  62.         int x = i + dx[k], y = j + dy[k];
  63.         if (x >= 1 && x <= n && y >= 1 && y <= n && !visit[x][y]) {
  64.             if (dfs(x, y)) return true;
  65.         }
  66.     }
  67.  
  68.     // 回退操作
  69.     path.pop_back();
  70.     row[i]--;
  71.     col[j]--;
  72.     visit[i][j] = false;
  73.     return false;
  74. }
  75.  
  76. int main() {
  77.     cin >> n;
  78.     aim_col.resize(n + 1);
  79.     for (int i = 1; i <= n; i++) cin >> aim_col[i];  // 输入北边靶子箭数
  80.     aim_row.resize(n + 1);
  81.     for (int i = 1; i <= n; i++) cin >> aim_row[i];  // 输入西边靶子箭数
  82.  
  83.     row.resize(n + 1);
  84.     col.resize(n + 1);
  85.     visit = vector<vector<int>>(n + 1, vector<int>(n + 1));  // 初始化访问矩阵
  86.  
  87.     dfs(1, 1);  // 从(1,1)开始搜索
  88.  
  89.     return 0;
  90. }

72a4030d74204f56b86d822e926b7774.png

总结结论

1.

递归函数dfs，用同样的函数完成相同的逻辑问题，但是需要用其他遍历辅助判断当前位于那个节点。

vector<int> path;

vector<int> row;

vector<int> col;

vector<vector<int>> visit;

(i,j）

以上都是当前节点的信息。

2.

每一次进入dfs维护当前节点信息，每一次出去之前回溯，消除维护的信息。

 
  1. void dfs(int i, int j) {
  2.     visit[i][j] = true;
  3.     row[i]++;
  4.     col[j]++;
  5.     path.push_back((i - 1) * n + (j - 1));//数学推导不细说，找规律
  6.     //添加主要逻辑
  7.     path.pop_back();
  8.     row[i]--;
  9.     col[j]--;
  10.     visit[i][j] = false;
  11. }

 

3.

如果只需要找唯一解，找到即返回，找到就不用工作，找到就飞升。

修改返回值，进入下一层逻辑，出口逻辑。

7401f170df974efcb1dc440636a9fd40.png

4.

剪枝操作提前返回，注意返回之前一定要回溯，也就是消除维护当前节点信息的操作！！！

结尾

最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。

 

同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。

 

谢谢您的支持，期待与您在下一篇文章中再次相遇！

 

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/463917
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号