题解 P1596 【[USACO10OCT]湖计数Lake Counting】

· · 题解

我想说的是：这个题的话与之前做的油田类似，不知你们做过没。

基本思路：

找到一块有水的地方，计数器加加，然后将它的周围四面八方的水的水都变成旱地，再去找下一个。既然这么简单的思路，那么就可以使用dfs来进行。

dfs代码如下：

int dfs(int i,int j)
{
    maps[i][j]='.';//将水变成旱地 
    if(maps[i-1][j-1]=='W')//左上角 
        dfs(i-1,j-1);
    if(maps[i-1][j]=='W')//正上方 
        dfs(i-1,j);
    if(maps[i][j-1]=='W')//左边 
        dfs(i,j-1);
    if(maps[i+1][j]=='W')//正下方 
        dfs(i+1,j);
    if(maps[i+1][j+1]=='W')//右下角 
        dfs(i+1,j+1);
    if(maps[i+1][j-1]=='W')//左下角 
        dfs(i+1,j-1);
    if(maps[i-1][j+1]=='W')//右上角 
        dfs(i-1,j+1);
    if(maps[i][j+1]=='W')//右方 
        dfs(i,j+1);
}

其实就是这样，完整代码如下：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m;
int ans=0;
char maps[101][101];
int dfs(int i,int j)
{
    maps[i][j]='.';//将水变成旱地 
    if(maps[i-1][j-1]=='W')//左上角 
        dfs(i-1,j-1);
    if(maps[i-1][j]=='W')//正上方 
        dfs(i-1,j);
    if(maps[i][j-1]=='W')//左边 
        dfs(i,j-1);
    if(maps[i+1][j]=='W')//正下方 
        dfs(i+1,j);
    if(maps[i+1][j+1]=='W')//右下角 
        dfs(i+1,j+1);
    if(maps[i+1][j-1]=='W')//左下角 
        dfs(i+1,j-1);
    if(maps[i-1][j+1]=='W')//右上角 
        dfs(i-1,j+1);
    if(maps[i][j+1]=='W')//右方 
        dfs(i,j+1);
}
int main()
{
    scanf("%d%d",&n,&m);//输入地的大小 
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>maps[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) {
            if(maps[i][j]=='W') {
                ans++;//一块加1 
                dfs(i,j);//进入dfs，消除周围所有的水，以便下次寻找。
            }
        }
    printf("%d",ans);
    return 0;
}