@TOC

题目描述

描述
Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water ('W') or dry land ('.'). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors.

Given a diagram of Farmer John's field, determine how many ponds he has.
输入

• Line 1: Two space-separated integers: N and M
• Lines 2..N+1: M characters per line representing one row of Farmer John's field. Each character is either 'W' or '.'. The characters do not have spaces between them.

输出

• Line 1: The number of ponds in Farmer John's field.

样例输入
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

这道题的要求就是求出有多少块不相邻的w组成的池塘

AC代码

这里的思路是碰到W就开始以w的坐标为起点广搜，搜到相连的W就修改地图，这样子遍历到第一个W的时候整个连起来的W就都处理完毕了，并且答案记得++

#include<iostream>
#include<cmath>
#include<cstdio>
#include<queue>//队列头文件
#include<cstring>
using namespace std;
int n,m,xx,yy,op=0,ans=0;
int dx[9]={0,0,0,1,-1,1,1,-1,-1};
int dy[9]={0,1,-1,0,0,1,-1,1,-1};//方向数组，上，下，左，右，左上，左下，右上，右下，八个方向（我广搜的时候喜欢循环1开始，所以方向数组下标为0的位置我全部给到0，从下标为1开始写方向）
char mp[404][404];
struct abc{
    int x,y;
};
void bfs(int x,int y){
    queue<abc>p;//想手写队列也可以，这里没有给出代码（我觉得这么写方便。。。）
    p.push((abc){x,y});
    while(!p.empty()){
        abc a=p.front();
        for(int i=1;i<=8;i++){
            int tx=a.x+dx[i];
            int ty=a.y+dy[i];
            if(tx<1||ty<1||tx>n||ty>m||mp[tx][ty]=='.') continue;
            op++;//排除出界和.的情况后就只剩下了W，所以修改地图并且入队即可
            mp[tx][ty]='.';
            p.push((abc){tx,ty});

        }
        p.pop();
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf(" %c",&mp[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            op=0;
            if(mp[i][j]=='W') {
                op=1;//如果碰到W就开始广搜

                bfs(i,j);
            }
            if(op) ans++;

        }
    }
    cout<<ans;
}

@^ _ ^@