题解 | #Lake Counting#

链接：https://ac.nowcoder.com/acm/problem/24739
来源：牛客网

题目描述

中文意思简单来说就是：有一块 N×MN×M 的土地，雨后积起了水，有水标记为 W，干燥为 .，积水被认为是八连通的，求出院子里共有多少处水洼

思路：肯定还是BFS，只不过改成遍历求BFS，每次遇到未被标志的W就对其求BFS，把与其连通的W全部标志一遍

至于BFS，没什么好说的，直接套模板就行

代码如下（用了STL库函数）：

#include<stdio.h>
#include<queue>
using namespace std;
int vis[120][120],N,M;
int dir[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
char mp[120][120];
struct node{
    int x,y;
};
queue<node>q;
void bfs(){
    while(!q.empty()){
        node temp=q.front();
        q.pop();
        for(auto i=0;i<8;i++){
            auto xx=temp.x+dir[i][0];
            auto yy=temp.y+dir[i][1];
            if(vis[xx][yy]==1 || xx<0 || yy<0 || xx>=N || yy>=M || mp[xx][yy]=='.'){
                continue;
            }
            vis[xx][yy]=1;
            q.push(node{xx,yy});
        }
    }
}
int main(){
    auto num=0;
    scanf("%d %d",&N,&M);
    for(auto i=0;i<N;i++){
        scanf("%s",mp[i]);
    }
    for(auto i=0;i<N;i++){
        for(auto j=0;j<M;j++){
            if(mp[i][j]=='W' && !vis[i][j]){
                vis[i][j]=1;
                q.push(node{i,j});
                bfs();
                num++;
            }
        }
    }
    printf("%d\n",num);
    return 0;
}

未用STL库函数（时间相等）代码如下：

#include<stdio.h>
int vis[111][111]={0},h=0,t=0,sum=0;
int s[111][111];
char ss[111][111];
int dir[8][2]={{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
struct ss{
    int x,y;
}que[10001];
void bfs(int n,int m){
    int i,xx,yy;
    vis[n][m]=1;
    for(i=0;i<8;i++){
        xx=n+dir[i][0];
        yy=m+dir[i][1];
        if(vis[xx][yy]==0 && s[xx][yy]!=0){
            vis[xx][yy]=1;
            que[t].x=xx;
            que[t].y=yy;
            t++;
        }
    }
    h++;
    if(h!=t) bfs(que[h].x,que[h].y);
}
int main(){
    int n,m,i,j;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++){
        scanf("%s",ss[i]);
    }
    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            if(ss[i][j]=='.') s[i][j]==0;
            else s[i][j]=1;
        }
    }
    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            if(vis[i][j]==0 && s[i][j]!=0){
                que[t].x=i;
                que[t].y=j;
                t++;
                bfs(i,j);
                sum++;
            }    
        }
    }
    printf("%d\n",sum);
    return 0;
}