BFS：flood-filled模型与题目详解acm

#写在前面

洪水覆盖算法
就是染色法

百度一下呗

不一定要用bfs实现
可以在线性时间复杂度内，找到某个点所在的连通块

##池塘计数

https://www.acwing.com/problem/content/1099/

----c++版

#include<iostream>
#include<algorithm>#define x first
#define y second
//为了方便using namespace std;
const int N=1010, M=N*N;
typedef pair<int, int> pll;int n,m;
char g[N][N];
pll q[M];
bool st[N][N];//判重数组，一般都会用到void bfs(int sx, int sy){
    int hh=0, tt=0;//注意有一个当前起点入队 所以tt=0，不是-1q[0] = {
    sx, sy};//当前起点入队st[sx][sy] = true;while(hh<=tt){
    pll t = q[hh++];//这里没有用漂移数组来模拟方向，而是用了两层循环//因为是8连通的，这样比较方便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]);int cnt = 0;for(int i=0; i<n; i++)for(int j=0; j<m; j++)if(g[i][j]=='W' && !st[i][j]){
    bfs(i, j);cnt++;}printf("%d", cnt);return 0;
}

##城堡问题

https://www.acwing.com/problem/content/1100/

----c++版

#include<iostream>
#include<algorithm>
#include<cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> pll;
const int N=55, M=N*N;int n,m;
int g[N][N];
pll q[M];
bool st[N][N];int bfs(int sx, int sy){
    int dx[4]={
    0, -1, 0, 1}, 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){
    pll 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, 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++;}cout<<cnt<<endl;cout<<area<<endl;return 0;
}

##山峰和山谷

https://www.acwing.com/problem/content/1108/

----c++版

#include<iostream>
#include<algorithm>
using namespace std;
#define x first
#define y second
const int N=1010;
typedef pair<int, int> pll;int n;
int h[N][N];
pll q[N*N];
bool st[N][N];void bfs(int sx, int sy, bool &h_h, bool &h_l){
    int hh=0, tt=0;q[0]={
    sx, sy};st[sx][sy]=true;while(hh<=tt){
    pll 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])h_h=true;else h_l=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 has_higher=false, has_lower=false;bfs(i, j, has_higher, has_lower);if(!has_higher)peak++;if(!has_lower)valley++;}printf("%d %d\n", peak, valley);return 0;
}