前天经过我们小组的商量，我们集资买了一门于大佬认为超级不错的课程，之后买完听到老师已经题目，表示豁然开朗，然后

我先观看我们比较喜欢的搜索题目，bfs的习题吧，发现其实bfs搜索的题目其实也是有一定的模板，规律和技巧的，所以我打算

发布一下近期写的题目，同时向大家推荐我观看的视频，小伙伴们有需要的可以买啊，超级划算的：acwing

题目传送门：https://www.acwing.com/problem/content/1099/

写这种bfs的题目一般用到队列的思想，然后我拿pair来存放数组的下标，千万一定要注意判断条件的时候千万不能漏写

这些题根据老师所讲的内容叫一种：洪水思想（我瞎起名字，其实名字是英文）。

下面给出ac代码：

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int ,int> pii;
const int N=1005,M=N*N;
char g[N][N];
int n,m;
pii q[M];
bool st[N][N];
int cnt=0;
void dfs(int sx,int sy){
        int hh=0,tt=0;
        q[0]={sx,sy};
        st[sx][sy]=true;
        while(hh<=tt){
                pii t=q[hh++];
                for(int i=t.x-1;i<=t.x+1;i++)
                        for(int j=t.y-1;j<=t.y+1;j++){
                                if(i==t.x&&j==t.y) continue;
                                if(i<0||i>=n||j<0||j>=m) continue;
                                if(g[i][j]=='.'||st[i][j]) continue;
                                q[++tt]={i,j};
                                st[i][j]=true;
                }
        }
}
int main(){
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++) scanf("%s",g[i]);
        for(int i=0;i<n;i++)
                for(int j=0;j<m;j++)
                        if(g[i][j]=='W'&&!st[i][j]){
                                dfs(i,j);
                                cnt++;
                        }
                        printf("%d\n",cnt);
        return 0;
}

 

题目传送门：https://www.acwing.com/problem/content/1100/

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int ,int >pii;
pii q[10000080];
int n,m;
const int maxn=100;
int g[maxn][maxn];
bool st[maxn][maxn];
int bfs(int sx,int sy){
        int dx[4]={0,-1,0,1};
        int dy[4]={-1,0,1,0};
        int hh=0,tt=0;
        int area=0;
        q[0]={sx,sy};
        st[sx][sy]=true;
        while(hh<=tt){
                pii t=q[hh++];
                area++;
                for(int i=0;i<4;i++){
                        int a=t.x+dx[i],b=t.y+dy[i];
                        if(a<0||a>=n||b<0||b>=m) continue;
                        if(st[a][b]) continue;
                        if(g[t.x][t.y]>>i&1) continue;

                        q[++tt]={a,b};
                        st[a][b]=true;
                }
        }
        return area;
}
int main(){
        cin>>n>>m;
        for(int i=0;i<n;i++)
                for(int j=0;j<m;j++)
                cin>>g[i][j];
        int cnt=0;
        int area=0;
        for(int i=0;i<n;i++)
                for(int j=0;j<m;j++)
                if(!st[i][j]){
                        area=max(area,bfs(i,j));
                        cnt++;
                }
                printf("%d\n%d\n",cnt,area);
        return 0;
}

FGD小朋友特别喜欢爬山，在爬山的时候他就在研究山峰和山谷。

为了能够对旅程有一个安排，他想知道山峰和山谷的数量。

给定一个地图，为FGD想要旅行的区域，地图被分为 n×nn×n 的网格，每个格子 (i,j)(i,j) 的高度 w(i,j)w(i,j) 是给定的。

若两个格子有公共顶点。

这道题是一道判断山峰和山谷的题目：

想法和思路和前面的题目类似

题目传送门：https://www.acwing.com/problem/content/1108/

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N=1005;
int n;
const int M=N*N;
typedef pair<int ,int > pii;
pii q[M];
int h[N][N];
bool st[N][N];
void bfs(int sx,int sy,bool& high,bool& low){
        int hh=0,tt=0;
        q[0]={sx,sy};
        st[sx][sy]=true;
        while(hh<=tt){
                pii t=q[hh++];
                for(int i=t.x-1;i<=t.x+1;i++)
                for(int j=t.y-1;j<=t.y+1;j++){
                        if(i<0||i>=n||j<0||j>=n) continue;
                        if(h[i][j]!=h[t.x][t.y]){
                                if(h[i][j]>h[t.x][t.y]) high=true;
                                else low=true;
                        }
                        else if(!st[i][j]){
                                q[++tt]={i,j};
                                st[i][j]=true;
                        }
                }
        }
}
int main(){
        scanf("%d",&n);
        for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                scanf("%d",&h[i][j]);
                int peak=0,valley=0;
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
                if(!st[i][j]){
                        bool high=false,low=false;
                        bfs(i,j,high,low);
                        if(!high) peak++;
                        if(!low) valley++;
                }
                printf("%d %d",peak,valley);
        return 0;
}