Lake Counting

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 53301		Accepted: 26062

Description

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

Hint

OUTPUT DETAILS:

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

题意：W代表水塘，. 代表土地，问一共有多少个联通的水塘

#include<iostream>

#include<string.h>

#include<string>

#include<algorithm>

using namespace std;

int dir[][]={{,-},{,},{,},{-,},{-,},{,},{-,-},{,-}};

char a[][];

int n,m;

int check(int x,int y)

{

    if(x>=&&x<n&&y>=&&y<m&&a[x][y]=='W')

        return ;

    else

        return ;

}

void dfs(int x,int y)

{

    if(check(x,y)==)

        return;

    if(a[x][y]=='W')

        a[x][y]='.';

    for(int i=;i<;i++)

    {

        int dx,dy;

        dx=x+dir[i][];

        dy=y+dir[i][];

        dfs(dx,dy);

    }

}

int main()

{

    cin>>n>>m;

    int cnt=;

    for(int i=;i<n;i++)

        cin>>a[i];

    for(int i=;i<n;i++)

    {

        for(int j=;j<m;j++)

        {

            if(a[i][j]=='W')

            {

                dfs(i,j);

                cnt++;

            }

        }

    }

    cout<<cnt<<endl;

    return ;

}

巴特西

POJ 2386 Lake Counting 八方向棋盘搜索

Lake Counting

最新文章

热门文章