迷宫问题用队列实现的代码
时间: 2023-03-28 19:00:32 浏览: 58
以下是用队列实现迷宫问题的代码:
```
#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 100;
int maze[MAXN][MAXN]; // 迷宫
int vis[MAXN][MAXN]; // 标记数组
int n, m; // 迷宫的行数和列数
struct Node {
int x, y; // 当前位置的坐标
int step; // 到达当前位置的步数
};
// 判断当前位置是否合法
bool isValid(int x, int y) {
if (x < || x >= n || y < || y >= m) {
return false;
}
if (maze[x][y] == 1 || vis[x][y] == 1) {
return false;
}
return true;
}
// BFS 搜索迷宫
int bfs(int sx, int sy, int ex, int ey) {
queue<Node> q;
Node start = {sx, sy, };
q.push(start);
vis[sx][sy] = 1;
while (!q.empty()) {
Node cur = q.front();
q.pop();
if (cur.x == ex && cur.y == ey) {
return cur.step;
}
// 向上走
if (isValid(cur.x - 1, cur.y)) {
Node next = {cur.x - 1, cur.y, cur.step + 1};
q.push(next);
vis[cur.x - 1][cur.y] = 1;
}
// 向下走
if (isValid(cur.x + 1, cur.y)) {
Node next = {cur.x + 1, cur.y, cur.step + 1};
q.push(next);
vis[cur.x + 1][cur.y] = 1;
}
// 向左走
if (isValid(cur.x, cur.y - 1)) {
Node next = {cur.x, cur.y - 1, cur.step + 1};
q.push(next);
vis[cur.x][cur.y - 1] = 1;
}
// 向右走
if (isValid(cur.x, cur.y + 1)) {
Node next = {cur.x, cur.y + 1, cur.step + 1};
q.push(next);
vis[cur.x][cur.y + 1] = 1;
}
}
return -1; // 无法到达终点
}
int main() {
cin >> n >> m;
for (int i = ; i < n; i++) {
for (int j = ; j < m; j++) {
cin >> maze[i][j];
}
}
int sx, sy, ex, ey;
cin >> sx >> sy >> ex >> ey;
int ans = bfs(sx, sy, ex, ey);
cout << ans << endl;
return ;
}
```