Lake Counting POJ - 2386

题目

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
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    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

1
3

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

思路

dfs算法的简单应用。
对整张图来说

  • 遍历整个图
  • 每遇到一个W,这水池数加1,同时将它改为.
  • 以上一步遇到的W为起点,搜索与它相连的位置,若发现W,则将它改为.,然后又搜索这个点周围的位置
  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    #include<iostream>
    #include<string>
    #include<vector>
    using namespace std;
    const int MAXSIZE=100+5;
    string str[MAXSIZE];
    int N,M;
    void DFS(int x,int y){
    str[x][y]='.';
    for(int i=x-1;i<=x+1;i++)
    for(int j=y-1;j<=y+1;j++){
    if(i>=0&&i<N&&j>=0&&j<M&&str[i][j]=='W')
    DFS(i,j);
    }
    }
    int main(){

    while(cin>>N>>M){
    for(int i=0;i<N;i++) cin>>str[i];
    int ans=0;
    for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
    if(str[i][j]=='W'){
    ans++;
    DFS(i,j);
    }
    }
    }
    cout<<ans<<endl;
    }
    return 0;
    }
    -------------本文结束感谢您的阅读-------------
    0%