路径之谜

题目描述

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

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

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

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

方和正西方各射一箭。(城堡的西墙和北墙内各有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

暴力递归

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.

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

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

 

5.

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

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

void dfs(int i, int j) {visit[i][j] = true;row[i]++;col[j]++;path.push_back((i - 1) * n + (j - 1));for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 1 && x <= n && y >= 1 && y <= n && !visit[x][y]) {dfs(x, y);}}path.pop_back();row[i]--;col[j]--;visit[i][j] = false;
}

 

6.

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

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

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

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

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

void dfs(int i, int j) {visit[i][j] = true;row[i]++;col[j]++;path.push_back((i - 1) * n + (j - 1));if (i == n && j == n) {int flag = 1;for (int i = 1; i <= n; i++) {if (row[i] != aim_row[i] || col[i] != aim_col[i]) flag = 0;}if (flag == 1) {for (auto& x : path) cout << x << " ";}path.pop_back();row[i]--;col[j]--;visit[i][j] = false;return;}for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 1 && x <= n && y >= 1 && y <= n && !visit[x][y]) {dfs(x, y);}}path.pop_back();row[i]--;col[j]--;visit[i][j] = false;
}

 

代码1

7.

此时得到的代码如下，

#include <iostream>
#include<bits/stdc++.h>
using namespace std;int n; // 定义n表示城堡地面是n×n个方格
vector<int> path; // 用于记录骑士的行走路径
vector<int> row; // 用于记录每行射出的箭的数量
vector<int> col; // 用于记录每列射出的箭的数量
vector<vector<int>> visit; // 记录某个格子是否被访问过
int dx[4] = { 1,-1,0,0 }; // 方向数组，用于实现上下左右移动
int dy[4] = { 0,0,1,-1 };
vector<int> aim_col; // 存储每列应该射出的箭的目标数量
vector<int> aim_row; // 存储每行应该射出的箭的目标数量// 深度优先搜索（DFS）函数，用于尝试所有可能的路径
void dfs(int i, int j) {visit[i][j] = true; // 标记当前格子为已访问row[i]++; // 当前行的箭数增加col[j]++; // 当前列的箭数增加path.push_back((i - 1) * n + (j - 1)); // 将当前格子编号加入路径// 如果到达东南角，并且每行每列的箭数都符合目标if (i == n && j == n) {int flag = 1;for (int i = 1; i <= n; i++) {if (row[i] != aim_row[i] || col[i] != aim_col[i]) flag = 0;}if (flag == 1) {for (auto& x : path) cout << x << " "; // 如果路径有效，输出这条路径}path.pop_back();row[i]--;col[j]--;visit[i][j] = false;return;}// 尝试向四个方向移动for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 1 && x <= n && y >= 1 && y <= n && !visit[x][y]) {dfs(x, y);}}// 回溯，撤销当前步骤的影响path.pop_back();row[i]--;col[j]--;visit[i][j] = false;
}int main() {cin >> n; // 读入n的大小aim_col.resize(n + 1);for (int i = 1; i <= n; i++) cin >> aim_col[i]; // 读入每列的目标箭数aim_row.resize(n + 1);for (int i = 1; i <= n; i++) cin >> aim_row[i]; // 读入每行的目标箭数row.resize(n + 1);col.resize(n + 1);visit = vector<vector<int>>(n + 1, vector<int>(n + 1));dfs(1, 1); // 从西北角开始进行深度优先搜索return 0;
}

运行结果如下，

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

8.

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

重新思考剪枝操作。

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

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

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

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

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

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

int dfs(int i, int j) {visit[i][j] = true;row[i]++;col[j]++;path.push_back((i - 1) * n + (j - 1));if (i == n && j == n) {int flag = 1;for (int i = 1; i <= n; i++) {if (row[i] != aim_row[i] || col[i] != aim_col[i]) flag = 0;}if (flag == 1) {for (auto& x : path) cout << x << " ";return true;}path.pop_back();row[i]--;col[j]--;visit[i][j] = false;return;}for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 1 && x <= n && y >= 1 && y <= n && !visit[x][y]) {if(dfs(x, y)) return true;}}path.pop_back();row[i]--;col[j]--;visit[i][j] = false;return false;
}

 

代码2

9.

#include <iostream>
#include<bits/stdc++.h>
using namespace std;int n; // 城堡地面为n×n个方格的大小
vector<int> path; // 存储骑士的行走路径
vector<int> row; // 每行射箭的次数
vector<int> col; // 每列射箭的次数
vector<vector<int>> visit; // 标记方格是否访问过
int dx[4] = { 1,-1,0,0 }; // x方向的移动：下，上，不动，不动
int dy[4] = { 0,0,1,-1 }; // y方向的移动：不动，不动，右，左
vector<int> aim_col; // 目标，每列应射箭的次数
vector<int> aim_row; // 目标，每行应射箭的次数// 深度优先搜索（DFS）算法，i和j表示当前位置
int dfs(int i, int j) {visit[i][j] = true; // 标记当前方格为已访问row[i]++; // 当前行的射箭次数增加col[j]++; // 当前列的射箭次数增加path.push_back((i - 1) * n + (j - 1)); // 将当前方格的编号加入到路径中// 检查是否到达右下角，并且所有行和列的射箭次数都符合目标if (i == n && j == n) {int flag = 1; // 用于检查是否所有行和列的射箭次数都匹配for (int i = 1; i <= n; i++) {if (row[i] != aim_row[i] || col[i] != aim_col[i]) flag = 0;}if (flag == 1) {for (auto& x : path) cout << x << " "; // 如果匹配，输出路径cout << endl; // 输出换行return true; // 返回找到有效路径}}// 尝试四个可能的移动方向for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 1 && x <= n && y >= 1 && y <= n && !visit[x][y]) {if (dfs(x, y)) return true; // 递归调用dfs}}// 回溯，撤销当前步骤path.pop_back();row[i]--;col[j]--;visit[i][j] = false;return false; // 没有找到有效路径
}int main() {cin >> n;aim_col.resize(n + 1);for (int i = 1; i <= n; i++) cin >> aim_col[i]; // 输入每列的目标射箭次数aim_row.resize(n + 1);for (int i = 1; i <= n; i++) cin >> aim_row[i]; // 输入每行的目标射箭次数row.resize(n + 1);col.resize(n + 1);visit = vector<vector<int>>(n + 1, vector<int>(n + 1, false)); // 初始化访问标记数组dfs(1, 1); // 从(1,1)开始深度优先搜索return 0;
}

运行结果如下，

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

10.

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

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

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

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

int dfs(int i, int j) {visit[i][j] = true;row[i]++;col[j]++;path.push_back((i - 1) * n + (j - 1));int flag1 = 1;for (int i = 1; i <= n; i++) {if (row[i] > aim_row[i] || col[i] > aim_col[i]) {flag1 = 0;break;}}if (flag1 == 0) {path.pop_back();row[i]--;col[j]--;visit[i][j] = false;return false;}if (i == n && j == n) {int flag = 1;for (int i = 1; i <= n; i++) {if (row[i] != aim_row[i] || col[i] != aim_col[i]) {flag = 0;break;}}if (flag == 1) {for (auto& x : path) cout << x << " ";return true;}else{path.pop_back();row[i]--;col[j]--;visit[i][j] = false;return false;}}for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 1 && x <= n && y >= 1 && y <= n && !visit[x][y]) {if (dfs(x, y)) return true;}}path.pop_back();row[i]--;col[j]--;visit[i][j] = false;return false;
}

 

代码3

#include <iostream>
#include<bits/stdc++.h>  // 引入常用库，包含STL等
using namespace std;// 定义全局变量
int n;  // 地图大小
vector<int> path;  // 记录路径
vector<int> row;  // 记录每行走过的次数
vector<int> col;  // 记录每列走过的次数
vector<vector<int>> visit;  // 访问标记数组
int dx[4] = { 1,-1,0,0 };  // 方向数组，表示行的移动
int dy[4] = { 0,0,1,-1 };  // 方向数组，表示列的移动
vector<int> aim_col;  // 目标列的箭数
vector<int> aim_row;  // 目标行的箭数// 深度优先搜索函数
int dfs(int i, int j) {visit[i][j] = true;  // 标记当前单元格已访问row[i]++;  // 增加当前行的计数col[j]++;  // 增加当前列的计数path.push_back((i - 1) * n + (j - 1));  // 记录路径int flag1 = 1;// 检查所有行列是否满足条件for (int i = 1; i <= n; i++) {if (row[i] > aim_row[i] || col[i] > aim_col[i]) {flag1 = 0;break;}}if (flag1 == 0) {  // 如果条件不满足，则回退操作path.pop_back();row[i]--;col[j]--;visit[i][j] = false;return false;}// 检查是否到达最后一个方格if (i == n && j == n) {int flag = 1;for (int i = 1; i <= n; i++) {if (row[i] != aim_row[i] || col[i] != aim_col[i]) {flag = 0;break;}}if (flag == 1) {  // 如果满足最终条件，输出路径for (auto& x : path) cout << x << " ";return true;} else {  // 否则，进行回退操作path.pop_back();row[i]--;col[j]--;visit[i][j] = false;return false;}}// 遍历四个方向for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 1 && x <= n && y >= 1 && y <= n && !visit[x][y]) {if (dfs(x, y)) return true;}}// 回退操作path.pop_back();row[i]--;col[j]--;visit[i][j] = false;return false;
}int main() {cin >> n;aim_col.resize(n + 1);for (int i = 1; i <= n; i++) cin >> aim_col[i];  // 输入北边靶子箭数aim_row.resize(n + 1);for (int i = 1; i <= n; i++) cin >> aim_row[i];  // 输入西边靶子箭数row.resize(n + 1);col.resize(n + 1);visit = vector<vector<int>>(n + 1, vector<int>(n + 1));  // 初始化访问矩阵dfs(1, 1);  // 从(1,1)开始搜索return 0;
}

总结结论

1.

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

vector<int> path;

vector<int> row;

vector<int> col;

vector<vector<int>> visit;

(i,j）

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

2.

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

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

 

3.

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

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

4.

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

结尾

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

 

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

 

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