c++设计回溯算法实现迷宫求解
时间: 2023-08-17 11:14:43 浏览: 103
好的,下面是C++的代码实现。
首先,我们需要定义一个迷宫的二维数组,用 0 表示可以通过的路,用 1 表示障碍物。接下来,我们需要定义一个函数,用来判断当前位置是否可以通过。如果当前位置已经到达迷宫的出口,则直接返回 True。否则,我们需要先判断当前位置是否越界,如果越界或者是障碍物,则返回 False。如果当前位置是可以通过的路,则将该位置标记为已经走过,并递归地调用上下左右四个方向的函数。如果四个方向都走不通,则将该位置标记为不可走,并返回 False。
以下是 C++ 代码实现:
```cpp
#include<iostream>
using namespace std;
const int MAXN = 1010;
int maze[MAXN][MAXN];
int n, m;
bool dfs(int x, int y) {
if (x == n - 1 && y == m - 1) {
return true;
}
if (x < 0 || y < 0 || x >= n || y >= m || maze[x][y] == 1) {
return false;
}
maze[x][y] = 1;
if (dfs(x - 1, y) || dfs(x + 1, y) || dfs(x, y - 1) || dfs(x, y + 1)) {
return true;
}
maze[x][y] = 0;
return false;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> maze[i][j];
}
}
if (dfs(0, 0)) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
return 0;
}
```
我们可以将迷宫表示为以下二维数组:
```
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
```
最后,我们只需要调用函数并传入起点的坐标即可。
```cpp
if (dfs(0, 0)) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
```
该函数返回 true 表示找到了一条从起点到出口的路径,返回 false 表示没有找到路径。
阅读全文
相关推荐


















