POJ 2386 Lake Counting（经典dfs）

系统管理员 2022-09-30 13:53 13阅读 0赞

Lake Counting  
Time Limit: 1000MS Memory Limit: 65536K  
Total Submissions: 33538 Accepted: 16715  
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

3  
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

dfs经典题  
题解：一次dfs后与初始的这个W连接的所有W都替换为‘.’,直到图中不存在W为止，总共进行的dfs的次数就是答案。

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    const int maxn = 105;
    char field[maxn][maxn];
    int n,m;
    void dfs(int x,int y)//现在的位置
    {
        field[x][y] = '.';//替换为.
        for(int dx = -1;dx<=1;dx++)//循环遍历八个方向
        {
            for(int dy = -1;dy<=1;dy++)
            {
                int nx = dx+x;
                int ny = dy+y;
                if(0<=nx&&nx<n&&0<=ny&&ny<m&&field[nx][ny] == 'W')//是否超出范围，是否有积水
                    dfs(nx,ny);
            }
        }
        return;
    }
    int main()
    {
        cin>>n>>m;
        char s;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                cin>>field[i][j];
            }
        }
        int cnt =0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(field[i][j] == 'W')//从W开始遍历
                    {
                        dfs(i,j);
                        cnt++;
                    }
            }
        }
        cout<<cnt<<endl;
        return 0;
    }