c++采用递归算法求解迷宫问题,并输出从入口到出口的所有迷宫路径。
时间: 2023-12-10 10:38:16 浏览: 49
好的,下面是一个采用递归算法求解迷宫问题的示例代码:
```cpp
#include <iostream>
using namespace std;
const int MAX_SIZE = 10; // 迷宫大小
int maze[MAX_SIZE][MAX_SIZE]; // 迷宫数组
bool visited[MAX_SIZE][MAX_SIZE]; // 标记数组,标记已访问过的位置
// 记录路径
struct Point {
int x;
int y;
};
Point path[MAX_SIZE * MAX_SIZE]; // 路径数组
int top = -1; // 栈顶指针
// 判断当前位置是否合法
bool is_valid(int x, int y) {
if (x >= 0 && x < MAX_SIZE && y >= 0 && y < MAX_SIZE && maze[x][y] == 0 && !visited[x][y]) {
return true;
}
return false;
}
// 递归求解迷宫问题
void dfs(int x, int y) {
if (x == MAX_SIZE - 1 && y == MAX_SIZE - 1) { // 到达终点
path[++top] = {x, y}; // 将当前位置加入路径
cout << "Path: ";
for (int i = 0; i <= top; i++) {
cout << "(" << path[i].x << ", " << path[i].y << ")";
if (i != top) {
cout << " -> ";
}
}
cout << endl;
top--; // 回溯
return;
}
if (is_valid(x, y)) {
visited[x][y] = true; // 标记当前位置已访问
path[++top] = {x, y}; // 将当前位置加入路径
// 向上走
dfs(x - 1, y);
// 向右走
dfs(x, y + 1);
// 向下走
dfs(x + 1, y);
// 向左走
dfs(x, y - 1);
visited[x][y] = false; // 取消标记
top--; // 回溯
}
}
int main() {
cout << "Please input the maze:" << endl;
for (int i = 0; i < MAX_SIZE; i++) {
for (int j = 0; j < MAX_SIZE; j++) {
cin >> maze[i][j];
}
}
dfs(0, 0); // 从起点开始搜索
return 0;
}
```
这段代码中,使用了一个 `visited` 数组来标记已访问过的位置,`path` 数组记录路径,`top` 变量表示栈顶指针。
在 `dfs` 函数中,首先判断当前位置是否为终点,如果是,则将路径输出并回溯。否则,判断当前位置是否合法,如果是,则将当前位置标记为已访问,将当前位置加入路径中,然后分别向上、右、下、左四个方向递归搜索,搜索完后取消当前位置的标记并回溯。
在 `main` 函数中,先输入迷宫数组,然后从起点开始搜索。