用C++写一个迷宫BFS算法的代码并记录完整的路径
时间: 2024-09-12 12:13:50 浏览: 44
迷宫一个走迷宫的程序.rar_迷宫_迷宫 C++_迷宫 代码
迷宫广度优先搜索(BFS)算法是一种用于在图中找到两个节点之间最短路径的算法。以下是使用C++实现的迷宫BFS算法,它可以找到从起点到终点的路径,并记录下完整的路径。
```cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 方向数组,分别表示上下左右四个方向
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
// 迷宫的行数和列数
const int ROW = 5;
const int COL = 5;
// 检查是否可以移动到坐标(x, y)
bool isValid(int x, int y, vector<vector<int>>& maze, vector<vector<bool>>& visited) {
return (x >= 0) && (x < ROW) && (y >= 0) && (y < COL) &&
maze[x][y] == 1 && !visited[x][y];
}
// BFS函数,找到从起点到终点的路径
bool BFS(vector<vector<int>>& maze, pair<int, int> start, pair<int, int> end) {
// 如果起点不可通行,则返回false
if (maze[start.first][start.second] != 1) return false;
// 初始化迷宫的访问状态
vector<vector<bool>> visited(ROW, vector<bool>(COL, false));
// 初始化队列,存储坐标和路径
queue<pair<pair<int, int>, vector<pair<int, int>>>> q;
q.push({start, {start}});
while (!q.empty()) {
auto front = q.front();
q.pop();
pair<int, int> curr = front.first;
vector<pair<int, int>> path = front.second;
// 检查是否到达终点
if (curr == end) {
// 输出路径
for (auto p : path) {
cout << "(" << p.first << ", " << p.second << ") ";
}
cout << endl;
return true;
}
// 遍历四个方向
for (int i = 0; i < 4; ++i) {
int x = curr.first + dx[i];
int y = curr.second + dy[i];
// 如果可以移动到新位置
if (isValid(x, y, maze, visited)) {
visited[x][y] = true;
vector<pair<int, int>> newPath = path;
newPath.push_back({x, y});
q.push({{x, y}, newPath});
}
}
}
// 如果没有路径到达终点
return false;
}
int main() {
// 创建迷宫,1表示通道,0表示障碍物
vector<vector<int>> maze = {
{1, 0, 0, 0, 1},
{1, 1, 0, 1, 0},
{0, 1, 0, 0, 0},
{1, 1, 1, 1, 1},
{0, 0, 0, 1, 1}
};
// 起点和终点坐标
pair<int, int> start = {0, 0};
pair<int, int> end = {4, 4};
// 调用BFS算法
if (!BFS(maze, start, end)) {
cout << "没有找到从起点到终点的路径" << endl;
}
return 0;
}
```
这段代码定义了一个5x5的迷宫,使用BFS算法从(0, 0)位置开始搜索到(4, 4)位置的路径。如果找到路径,程序会输出路径;如果没有找到路径,则输出相应的提示信息。
阅读全文