请用C++编写迷宫代码
时间: 2024-02-18 17:04:54 浏览: 35
好的,以下是一个简单的C++迷宫代码示例:
```c++
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int ROW = 10;
const int COL = 10;
// 迷宫地图
int maze[ROW][COL] = {
{0, 1, 0, 0, 0, 0, 0, 1, 0, 0},
{0, 1, 0, 1, 1, 1, 0, 1, 0, 1},
{0, 1, 0, 0, 0, 0, 0, 1, 0, 0},
{0, 1, 1, 1, 0, 1, 1, 1, 1, 0},
{0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 1, 1, 0, 1, 1, 1, 0},
{0, 1, 0, 0, 1, 0, 0, 0, 1, 0},
{0, 1, 1, 0, 1, 1, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
{0, 1, 1, 1, 1, 1, 1, 1, 1, 0}
};
// 记录路径的结构体
struct Node{
int row;
int col;
Node* parent;
};
// 查找迷宫路径
bool findPath(int startRow, int startCol, int endRow, int endCol, vector<Node*>& path) {
// 判断起点和终点是否在迷宫范围内
if (startRow < 0 || startRow >= ROW || startCol < 0 || startCol >= COL ||
endRow < 0 || endRow >= ROW || endCol < 0 || endCol >= COL) {
return false;
}
// 判断起点和终点是否为障碍物
if (maze[startRow][startCol] == 1 || maze[endRow][endCol] == 1) {
return false;
}
// 初始化栈,将起点入栈
stack<Node*> s;
Node* startNode = new Node{ startRow, startCol, nullptr };
s.push(startNode);
// 记录是否已经访问过的二维数组
bool visited[ROW][COL] = { false };
visited[startRow][startCol] = true;
// 开始搜索迷宫路径
while (!s.empty()) {
// 取出栈顶元素
Node* curNode = s.top();
s.pop();
// 判断是否为终点
if (curNode->row == endRow && curNode->col == endCol) {
// 将路径记录到vector中
while (curNode) {
path.push_back(curNode);
curNode = curNode->parent;
}
return true;
}
// 向四个方向扩展搜索
if (curNode->row - 1 >= 0 && maze[curNode->row - 1][curNode->col] == 0 && !visited[curNode->row - 1][curNode->col]) {
Node* nextNode = new Node{ curNode->row - 1, curNode->col, curNode };
s.push(nextNode);
visited[curNode->row - 1][curNode->col] = true;
}
if (curNode->row + 1 < ROW && maze[curNode->row + 1][curNode->col] == 0 && !visited[curNode->row + 1][curNode->col]) {
Node* nextNode = new Node{ curNode->row + 1, curNode->col, curNode };
s.push(nextNode);
visited[curNode->row + 1][curNode->col] = true;
}
if (curNode->col - 1 >= 0 && maze[curNode->row][curNode->col - 1] == 0 && !visited[curNode->row][curNode->col - 1]) {
Node* nextNode = new Node{ curNode->row, curNode->col - 1, curNode };
s.push(nextNode);
visited[curNode->row][curNode->col - 1] = true;
}
if (curNode->col + 1 < COL && maze[curNode->row][curNode->col + 1] == 0 && !visited[curNode->row][curNode->col + 1]) {
Node* nextNode = new Node{ curNode->row, curNode->col + 1, curNode };
s.push(nextNode);
visited[curNode->row][curNode->col + 1] = true;
}
}
return false;
}
int main() {
// 查找迷宫路径
vector<Node*> path;
findPath(0, 0, ROW - 1, COL - 1, path);
// 输出迷宫路径
for (int i = path.size() - 1; i >= 0; i--) {
cout << "(" << path[i]->row << ", " << path[i]->col << ")" << endl;
}
return 0;
}
```
该代码使用了DFS算法,通过栈来实现搜索。在搜索过程中,使用visited数组记录已经访问过的位置,避免重复搜索。如果找到终点,就将路径记录到vector中,最后输出路径即可。
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)