queue+c+++使用
时间: 2023-08-03 09:31:41 浏览: 43
C++ 中使用队列(queue)需要包含头文件 `<queue>`,然后定义一个队列对象。下面是一个使用队列实现 BFS(广度优先搜索)的示例代码:
```c++
#include <iostream>
#include <queue>
using namespace std;
const int N = 100;
int n, m; // 表示图的大小为 n * m
char g[N][N]; // 存储图
bool visited[N][N]; // 记录每个点是否被访问过
// 定义一个结构体表示一个点的坐标
struct Point {
int x, y;
Point(int x, int y) : x(x), y(y) {}
};
// 判断一个点是否可以访问
bool isValid(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= m) return false; // 越界
if (g[x][y] == '#') return false; // 障碍物
if (visited[x][y]) return false; // 已经访问过
return true;
}
// 定义一个 BFS 函数,从起点 (x1, y1) 开始搜索,到终点 (x2, y2) 结束
int bfs(int x1, int y1, int x2, int y2) {
queue<Point> q; // 定义一个队列存储待访问的点
q.push(Point(x1, y1)); // 将起点放入队列
visited[x1][y1] = true; // 标记已访问
int step = 0; // 记录步数
while (!q.empty()) {
int sz = q.size(); // 记录当前队列的大小
for (int i = 0; i < sz; i++) {
Point p = q.front(); // 取出队首元素
q.pop(); // 弹出队首元素
int x = p.x, y = p.y;
if (x == x2 && y == y2) return step; // 到达终点,返回步数
// 将当前点的相邻未访问点加入队列
if (isValid(x-1, y)) { q.push(Point(x-1, y)); visited[x-1][y] = true; }
if (isValid(x+1, y)) { q.push(Point(x+1, y)); visited[x+1][y] = true; }
if (isValid(x, y-1)) { q.push(Point(x, y-1)); visited[x][y-1] = true; }
if (isValid(x, y+1)) { q.push(Point(x, y+1)); visited[x][y+1] = true; }
}
step++; // 计数器加一
}
return -1; // 搜索失败,返回 -1
}
int main() {
cin >> n >> m;
int x1, y1, x2, y2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> g[i][j];
if (g[i][j] == 'S') { x1 = i; y1 = j; } // 记录起点位置
if (g[i][j] == 'E') { x2 = i; y2 = j; } // 记录终点位置
}
}
int ans = bfs(x1, y1, x2, y2);
cout << ans << endl;
return 0;
}
```
在这个示例中,我们使用队列来存储待访问的点,并使用 `visited` 数组来记录每个点是否被访问过。在广度优先搜索中,我们需要每次将当前点的相邻未访问点加入队列,然后再取出队首元素进行访问。最后,我们记录每个点到起点的步数,直到访问到终点。