POJ 2386 Lake Counting

题目描述

Lake Counting

Time Limit: 1000MS Memory Limit: 65536K

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表示有水，.表示无水，有水的周围八个方向内有水都算成是一个水洼。样例中的三个水洼可以加强对题意的理解。因为需要对每一个状态进行查询，所以这里我们需要用到dfs。

代码实现

#include<bits/stdc++.h>
using namespace std;
char p[105][105];
int d[8][2]={0,1, 0,-1, 1,0, -1,0, 1,1, 1,-1, -1,1, -1,-1};//方向变量的定义，周围八个方向。
int m,n,sum;
void dfs(int x,int y)
{
    if(x>=0&&y>=0&&x<n&&y<m)//判断每次进行递归的时候x和y是否还在合理的范围内，否则直接退出当前循环。
    {
        if(p[x][y]=='W')
        {
            p[x][y]='.';//把查询到的W(有水)变成.(无水)。
            for(int i=0;i<8;i++)
                dfs(x+d[i][0],y+d[i][1]);//对每个有水地方的八个方向进行dfs，用来向下一步递归
        }
    }
}
int main()
{
    sum=0;
    cin>>n>>m;
    getchar();
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>p[i][j];//存图
        }
        getchar();
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(p[i][j]=='W')//从0，0开始，查询到W就开始dfs。
            {
                dfs(i,j);
                sum++;//每次dfs完回来之后，及说明与i，j相邻的水地没有了，所以水洼的数量加一
            }
        }
    }
    cout<<sum<<endl;
    return 0;
}

参考白书之后，发现如果是八个方向的话，可以不用方向向量而是使用两层循环

for(int i=-1;i<=1;i++)
    for(int j=1;j<=1;j++)
    {
        int nx=x+i;
        int ny=y+j;
        ……
        dfs(nx,ny);
    }

这个就看个人喜好了。

我的个人喜好？

赏