用户自定义迷宫地图,指定入口和出口,采用图相关算法寻找一条出入口之间最短路径用C++语言写
时间: 2024-01-17 13:05:03 浏览: 25
以下是一个基于BFS算法的C++代码示例,可以用于解决用户自定义的迷宫地图中入口和出口之间最短路径的问题。
```C++
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 100;
int N, M; // 迷宫地图的行数和列数
int sx, sy; // 入口坐标
int ex, ey; // 出口坐标
int maze[MAXN][MAXN]; // 迷宫地图
int dist[MAXN][MAXN]; // 记录起点到各个点的最短路径长度
bool vis[MAXN][MAXN]; // 标记每个点是否已经被访问过
// 定义一个结构体表示一个点的坐标
struct Point {
int x, y;
};
// 定义一个结构体表示一个点的坐标和距离
struct Node {
Point p;
int d;
};
// 判断当前点是否合法
bool isValid(int x, int y) {
return (x >= 1 && x <= N && y >= 1 && y <= M && maze[x][y] == 0);
}
// BFS遍历迷宫地图,求解起点到终点的最短路径长度
int bfs() {
memset(dist, -1, sizeof(dist));
memset(vis, false, sizeof(vis));
queue<Node> q;
Node node = {{sx, sy}, 0}; // 起点
q.push(node);
vis[node.p.x][node.p.y] = true;
dist[node.p.x][node.p.y] = 0;
while (!q.empty()) {
Node cur = q.front();
q.pop();
if (cur.p.x == ex && cur.p.y == ey) { // 已经到达终点,直接返回路径长度
return cur.d;
}
// 遍历当前点的四个方向
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
for (int i = 0; i < 4; i++) {
int nx = cur.p.x + dx[i];
int ny = cur.p.y + dy[i];
if (isValid(nx, ny) && !vis[nx][ny]) { // 当前点可以走,并且没有被访问过
Node next = {{nx, ny}, cur.d + 1};
q.push(next);
vis[nx][ny] = true;
dist[nx][ny] = next.d;
}
}
}
return -1; // 没有找到路径
}
int main() {
cin >> N >> M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> maze[i][j];
}
}
cin >> sx >> sy >> ex >> ey;
int shortestDist = bfs(); // 求解最短路径长度
cout << shortestDist << endl;
return 0;
}
```
以上代码中,我们通过BFS算法遍历迷宫地图,求解起点到终点的最短路径长度,其中`isValid()`函数用于判断当前点是否可以走,`bfs()`函数用于遍历地图,寻找最短路径。在求解出最短路径长度之后,我们可以根据`dist`数组还原出具体的路径。