相信聪明的你一定做出了上期的题目
本期让我们来升华一下
下面为了防止大家忘记，把队列的成员函数放在下面:
queue <int> q;//创建一个变量名为q,类型为int的队列，注意，类型可以是结构体等等
q.empty()//返回值为true或false，表示队列是否为空
q.size()//队列里还有的元素数量
q.front()//返回队头
q.pop()//压出队头
q.push(x)//压入x
然后我们来想，如何用队列完成广度优先搜索？
广度优先搜索就如同一颗石子掉进水里，然后不断的扩散，最终找到节点
我们知道，队列恰恰是先进先出
这和广度优先相似，同样是从多个当前节点找到多个新的节点，先进先出，而我们可以利用这一特性，使得先进入队列的节点优先出去，而出去也就意味着这个节点
需要扩散，就可以找到新的节点，并把他们加入队列，遍历整个队列即可得到答案
下面是例题:
题意：有一块的土地，雨后积起了水，有水标记为，干燥为。八连通的积水被认为是连接在一起的。请求出院子里共有多少水洼？
第一行两个整数
然后是地图
一行一个整数，表示有多少水坑
10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W.
3 上面这题，需要我们求出有多少水坑，样例是3个对吧，但是我们要让机器来做这个事
我们怎么做？
首先，遍历地图，如果遇到一个有水的节点，那么就代表这里会产生一个水坑，ans++
但是呢，如果遍历下一个节点a[i][j]正好就是上个节点的水坑怎么办？ans就不能++
这时，我们可以标记这个水坑不能ans++
那怎么标记呢？你会发现，找这个水坑与他相连的水坑很像广度优先搜索
所以便可使用他来完成了
下面是代码:（请不要试图抄袭，作者会持续关注评测里的这一道题，抄袭将上报管理员）
#include <bits/stdc++.h>
using namespace std;
int m, n;
int ans = 0;
char a[1000][1000];//地图不用多说了吧
bool vis[1000][1000];//这里就是标记,vis[i][j]==0时,这个水坑没被标记，ans++
int dx[8] = {1, -1, 0, 0, 1, -1, -1, 1}; //有人会问，怎么控制方向，其实很简单，我们可以直接去开个数组表示上下左右等等
int dy[8] = {0, 0, 1, -1, 1, -1, 1, -1};
struct tdot { //为了方便记录队列里的坐标，可以开一个结构体
int x;
int y;
};
void bfs(int i, int j) {
tdot d;//首先，我们需要将初始节点加入队列，这是搜索的第一层
d.x = i;
d.y = j;
queue <tdot> qu;
qu.push(d);//定义队列，并放入初始节点
vis[i][j] = true; //标记初始节点(最好还是标一下)
while (!qu.empty()) { //如果队列中还有节点（搜索没有结束）
tdot fro = qu.front(); //利用先进先出的特性，把先来的节点取出并记录
qu.pop();
for (int k = 0; k < 8; k++) {
int nx = dx[k] + fro.x;
int ny = dy[k] + fro.y; //广度优先他的各个相邻节点
if (nx >= 0 && nx < m && ny >= 0 && ny < n && a[nx][ny] == 'W' && vis[nx][ny] == false) { //如果相邻节点没越界，并且是水，并且没被标记（减少时间复杂度，否则会死循环）
tdot nd;//那么就可以把这个节点加入队列
nd.x = nx;
nd.y = ny;
vis[nx][ny] = true; //标记这个节点
qu.push(nd);
}
}
}
}
int main() {
cin >> m >> n;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] == 'W' && !vis[i][j]) { //看，如果这个格子是水，并且没有被标记，那么ans++，并且进入广度优先搜索
bfs(i, j);
ans++;
}
}
}
cout << ans << endl;
return 0;
}
最后，请大家尝试用所学的知识完成:#250.走迷宫,相信聪明的你一定能做出来
共 1 条回复
👍