路径之谜
题目描述
小明冒充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.
剪枝操作提前返回，注意返回之前一定要回溯，也就是消除维护当前节点信息的操作！！！
结尾
最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。
同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。
谢谢您的支持，期待与您在下一篇文章中再次相遇！