C++迷宫类深度搜索
时间: 2023-08-11 13:07:16 浏览: 50
对于迷宫类的深度搜索算法,你可以使用递归来实现。下面是一个示例的C++代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
class Maze {
public:
Maze(vector<vector<int>>& maze) : maze(maze) {
rows = maze.size();
cols = maze[0].size();
}
bool solveMaze(int startX, int startY, int endX, int endY) {
vector<vector<bool>> visited(rows, vector<bool>(cols, false));
return dfs(startX, startY, endX, endY, visited);
}
private:
vector<vector<int>> maze;
int rows;
int cols;
bool isValid(int x, int y, vector<vector<bool>>& visited) {
if (x >= 0 && x < rows && y >= 0 && y < cols && maze[x][y] == 0 && !visited[x][y]) {
return true;
}
return false;
}
bool dfs(int x, int y, int endX, int endY, vector<vector<bool>>& visited) {
// 到达终点
if (x == endX && y == endY) {
return true;
}
// 标记当前位置为已访问
visited[x][y] = true;
// 尝试四个方向的移动
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (isValid(newX, newY, visited)) {
if (dfs(newX, newY, endX, endY, visited)) {
return true;
}
}
}
// 四个方向都无法到达终点,回溯
visited[x][y] = false;
return false;
}
};
int main() {
vector<vector<int>> maze = {
{0, 1, 0, 0},
{0, 0, 0, 1},
{0, 1, 0, 0},
{0, 0, 0, 0}
};
Maze mazeObj(maze);
bool canReachEnd = mazeObj.solveMaze(0, 0, 3, 3);
if (canReachEnd) {
cout << "可以到达终点" << endl;
} else {
cout << "无法到达终点" << endl;
}
return 0;
}
```
上面的代码实现了一个迷宫类 `Maze`,其中 `solveMaze` 方法用于判断是否能从起点 `(startX, startY)` 到达终点 `(endX, endY)`。在 `dfs` 方法中,使用递归进行深度搜索,通过判断当前位置的四个相邻位置是否可行来进行移动。
以上是一个简单的深度搜索迷宫类的示例,你可以根据实际需求进行更改和扩展。