POJ-2386Lake Counting，搜索题。。

Lake Counting

Time Limit: 1000MS		Memory Limit: 65536K

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.

Source

USACO 2004 November

这应该是搜索里面的简单题了吧，和NYOJ水池数目一模一样，刚学搜索时还不会做，然后看到大牛写的博客上说这是最简单的搜索题了。。。

思路就是用深搜，其实广搜深搜都可以，往八个方向找，只要是W则继续搜索并将该点变为‘.’，做法很多种，看代码；

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

//const int INF=0x3f3f3f3f;

const int N=150;

char a[N][N];

int n,m;

int dx[8]= {0,0,1,-1,1,1,-1,-1};

int dy[8]= {1,-1,0,0,-1,1,1,-1};

void dfs(int x,int y)

{

    if(x<n&&x>=0&&y>=0&&y<m)

    {

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

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

        {

            int xx=x+dx[i];

            int yy=y+dy[i];

            if(a[xx][yy]=='W')

                dfs(xx,yy);

        }

    }

}

int main()

{

    int i,j,sum;

    while(~scanf("%d%d",&n,&m))

    {

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

            scanf("%s",a[i]);

        sum=0;

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

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

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

                {

                    dfs(i,j);

                    sum++;

                }

        printf("%d\n",sum);

    }

    return 0;

}

搜索一定要注意的是边界问题，还有是否会陷入死循环；

巴特西

POJ-2386Lake Counting，搜索题。。

最新文章

热门文章