上面迷宫问题的代码请给我一个实例
时间: 2024-02-22 22:59:32 浏览: 14
好的,这是一个简单的迷宫问题的代码示例,使用DFS算法求解:
```
#include <iostream>
#include <vector>
using namespace std;
const int N = 5; // 迷宫大小为 5x5
int maze[N][N] = {
{0, 1, 0, 0, 0},
{0, 1, 0, 1, 0},
{0, 0, 0, 0, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 1, 0}
}; // 迷宫地图,0 表示可以通过,1 表示障碍物
vector<pair<int, int>> path; // 记录路径
bool dfs(int x, int y) {
if (x == N - 1 && y == N - 1) { // 到达终点
path.push_back({x, y});
return true;
}
if (maze[x][y] == 0) { // 可以通过
maze[x][y] = 1; // 标记为已访问
path.push_back({x, y}); // 记录路径
if (x > 0 && dfs(x - 1, y)) return true; // 上
if (x < N - 1 && dfs(x + 1, y)) return true; // 下
if (y > 0 && dfs(x, y - 1)) return true; // 左
if (y < N - 1 && dfs(x, y + 1)) return true; // 右
maze[x][y] = 0; // 回溯
path.pop_back(); // 回溯
}
return false;
}
int main() {
if (dfs(0, 0)) { // 从起点开始搜索
cout << "找到了一条路径:";
for (auto p : path) cout << "(" << p.first << ", " << p.second << ") -> ";
cout << endl;
} else {
cout << "没有找到路径!" << endl;
}
return 0;
}
```
这个示例中,我们用一个 $5\times 5$ 的二维数组 `maze` 表示迷宫地图,其中 $0$ 表示可以通过,$1$ 表示障碍物。我们使用 DFS 算法从起点 $(0, 0)$ 开始搜索,找到一条路径到达终点 $(4, 4)$。在搜索过程中,我们记录下路径,最后输出路径结果。