A - Lake Counting POJ - 2386

2-Day2-A
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.
Input

• 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.
  Output

• Line 1: The number of ponds in Farmer John's field.
  Sample Input
  10 12
  W........WW.
  .WWW.....WWW
  ....WW...WW.
  .........WW.
  .........W..
  ..W......W..
  .W.W.....WW.
  W.W.W.....W.
  .W.W......W.
  ..W.......W.
  Sample Output
  3
  Hint
  OUTPUT DETAILS:

There are three ponds: one in the upper left, one in the lower left,and one along the right side.

题意：油田的翻版，.和w组成多少块湖泊？

思路：BFS即可

代码如下：

#include<cstdio>
#include<queue>
#include<cmath>
#include<cstring>
#include<iostream>
using namespace std;
const int N=101;
char water[N][N];
int n,m;
void dps(int x,int y)
{
    water[x][y]='.';
    for(int dx=-1;dx<=1;dx++)
    {
        for(int dy=-1;dy<=1;dy++)
        {
            if(water[x+dx][y+dy]=='W'&&x+dx>=0&&y+dy>=0&&x+dx<n&&y+dy<m)
            dps(x+dx,y+dy);
        }
    }
return;
}


int main(void)
{
    int sum=0;
    memset(water,0,sizeof(water));
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int k=0;k<m;k++)
        {
            cin>>water[i][k];
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int k=0;k<m;k++)
        {
            if(water[i][k]=='W')
            {
                dps(i,k);
                sum++;
            }
        }
    }
    cout<<sum<<endl;
    return 0;
}