P1596 【[USACO10OCT]湖计数Lake Counting】

可爱的题面君~~

个人感觉这题还是很简单的,就是一个完全不加工的找联通块个数

个人解题思路是先读入,然后循环一遍,遇到水就dfs,并把这个w所在的联通块“删除”,并在答案上加一

最后输出答案

具体注释看程序:::

 1 #include<cmath>
 2 #include<cstdio>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<algorithm>
 6 using namespace std;
 7 int n,m,ans;
 8 bool a[105][105];//我用布尔数组,反正就两种情况
 9 void dfs(int x,int y){//dfs
10     a[x][y]=false;//删除连通块
11     if(x+1<=n&&a[x+1][y])dfs(x+1,y);//如果下面是水(。。。),往下搜
12     if(y+1<=m&&a[x][y+1])dfs(x,y+1);//如果左边是水,往左搜,注意y是与m比较,千万不要把m,n弄混
13     if(x-1>=1&&a[x-1][y])dfs(x-1,y);//往上搜
14     if(y-1>=1&&a[x][y-1])dfs(x,y-1);//往右搜
15     if(x+1<=n&&y+1<=m&&a[x+1][y+1])dfs(x+1,y+1);//往左上搜
16     if(x+1<=n&&y-1>=1&&a[x+1][y-1])dfs(x+1,y-1);//往右上搜
17     if(x-1>=1&&y+1<=m&&a[x-1][y+1])dfs(x-1,y+1);//往左下搜
18     if(x-1>=1&&y-1>=1&&a[x-1][y-1])dfs(x-1,y-1);//往右下搜
19 }
20 void sc(){//这是我个人调试时用的程序,看被删除的连通块是哪一个,有兴趣的同学可以看看~~~
21     for(int i=1;i<=n;i++){
22         for(int j=1;j<=m;j++){
23             if(a[i][j])cout<<"w";
24             else cout<<".";
25         }
26         cout<<endl;
27     }
28 }
29 int main(){//主函数
30     cin>>n>>m;//读入
31     for(int i=1;i<=n;i++){
32             string x;//定义字符串,字符串虽然是单独的一个变量,但可以直接用下标访问
33             cin>>x;//读入连续一段char型的字符串,比较方便
34         for(int j=1;j<=m;j++){
35             if(x[j-1]=='.')a[i][j]=false;//注意,x是从下标为0的地方开始读的,如果不是水块,就赋值否
36             else a[i][j]=true;//否则为是
37         }
38     }
39     for(int i=1;i<=n;i++){//模拟
40         for(int j=1;j<=m;j++){
41             if(a[i][j]){//如果是水
42                 //cout<<i<<' '<<j<<endl;个人调试所用
43                 dfs(i,j);//删除连通块
44                 //sc();个人调试所用
45                 ans++;//答案数加一
46             }
47         }
48     }
49     cout<<ans<<endl;//输出答案
50     return 0;
51 }//完美结束 最后,祝大家天天开心,编程顺利(。。。)

新人开博鼓励一下吧~~~

原文地址:https://www.cnblogs.com/hahaha2124652975/p/11123150.html