迷宫问题寻宝(c++实现,求最短路径,显示路径)
dfs算法迷宫问题寻宝,c++
·
定义一个二维数组: int maze[n][m];
它表示一个迷宫,其中的1表示道路不通,0表示可以走的路,3 表示宝藏。只能横着走或竖着走,不能斜着走,要求编程序找出找到宝藏的最短路路径,题目保证有解且只有一个最短路径。且只能从迷宫边缘进入迷宫。
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 3, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};输出路径为
{{2,0},{2,1},{2,2}}
代码为
#include<iostream>
#include<algorithm>
#include <stack>
#include <set>
#include <map>
#include <queue>
#include<sstream>
using namespace std;
vector<vector<int>> res;
bool cmp(vector<int>& v1, vector<int>& v2) {
return v1.size() < v2.size();
}
void dfs(vector<vector<int>>& matrix, vector<int>& trace, int i, int j) {
int m = matrix.size();
int n = matrix[0].size();
if (i < 0 || i >= m || j < 0 || j >= n) return;
if (matrix[i][j] == 1 || matrix[i][j] == -10) {
return;
}
if (matrix[i][j] == 3) {
//添加宝藏坐标
trace.push_back(i);
trace.push_back(j);
res.push_back(trace);
//回溯
trace.pop_back();
trace.pop_back();
return;
}
//添加路径坐标
trace.push_back(i);
trace.push_back(j);
matrix[i][j] =-10;//防止往回走
dfs(matrix, trace, i, j + 1);
dfs(matrix, trace, i, j - 1);
dfs(matrix, trace, i + 1, j);
dfs(matrix, trace, i - 1, j);
matrix[i][j] = 0;
trace.pop_back();
trace.pop_back();
}
int main() {
vector<vector<int>>matrix = { { 0, 1, 1, 1 } ,{0,0,0,1},{1,0,3,1}, {1,0,1,1} };
int m = matrix.size();
int n = matrix[0].size();
vector<int>trace;
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
dfs(matrix, trace, i, 0);
}
if (matrix[i][n - 1] == 0) {
dfs(matrix, trace, i, n-1);
}
}
for (int i = 0; i < n; i++) {
if (matrix[0][i] == 0) {
dfs(matrix, trace, 0, i);
}
if (matrix[m-1][i] == 0) {
dfs(matrix, trace, m-1,i );
}
}
sort(res.begin(), res.end(), cmp);
vector<vector<int>>ans;
vector<int>temp = res[0];
for (int j = 0; j < temp.size(); j += 2) {
ans.push_back({ temp[j], temp[j + 1] });
}
for (int i = 0; i < ans.size(); i++) {
cout << ans[i][0] <<"\t" << ans[i][1] << endl;
}
//输出ans即可
}
更多推荐
已为社区贡献1条内容
所有评论(0)