题解报告:poj 2386 Lake Counting(dfs求最大连通块的个数)
2024-08-22 19:33:02
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.
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.
* 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.
There are three ponds: one in the upper left, one in the lower left,and one along the right side.
解题思路:从任意的'W'开始,不停地把邻接的部分用'.'代替。一次DFS后与初始的这个'W'连接的所有'W'就被替换成了'.',因此直到图中不再存在'W'为止,总共进行的DFS的次数就是最终答案。
AC代码:
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=;
int n,m,res;char mp[maxn][maxn];
void dfs(int x,int y){
mp[x][y]='.';
for(int dx=-;dx<=;++dx){
for(int dy=-;dy<=;++dy){
int nx=x+dx,ny=y+dy;
if(<=nx && nx<n && <=ny && ny<m && mp[nx][ny]=='W')dfs(nx,ny);//往8个方向寻找'W'的点
}
}
return;
}
int main(){
while(~scanf("%d%d",&n,&m)){
for(int i=;i<n;++i)scanf("%s",mp[i]);
res=;
for(int i=;i<n;++i)
for(int j=;j<m;++j)
if(mp[i][j]=='W'){dfs(i,j);res++;}
printf("%d\n",res);
}
return ;
}
最新文章
- flume使用示例
- Ubuntu杂记——Ubuntu自带拼音输入发杂乱不堪
- ProcessBuilder 、Runtime和Process 的区别
- putty+xming远程登录Ubuntu16.04图形界面
- 更加简洁易用——wangEditor富文本编辑器新版本发布
- Sublime Text 3常用快捷键 以及package control 安装
- hdu 3853 LOOPS(基础DP求期望)
- 怎样在loop中处理异常
- [POJ] 3461 Oulipo [KMP算法]
- 16个值得个人站长做的广告联盟[转自cnzz]
- SSIS 延迟验证(DelayValidation)
- 论文笔记(9):Multiscale Combinatorial Grouping
- .NET Core protobuf-net、MessagePack、Json.NET序列化/反序列化性能测试
- 2018.12.1 Test
- 25个SSH命令
- 【转载】一个小时学会MySQL数据库
- FarBox的建站过程
- 24款最好的jQuery日期时间选择器插件
- ZOJ 3963 Heap Partition(multiset + stl自带二分 + 贪心)题解
- C# 调用Windows图片查看器
热门文章
- android listVIew实现button按钮监听程序
- Codeforces 631B Print Check【模拟】
- POJ 2785_4 Values whose Sum is 0
- Network-POJ3694(最小公共祖先LCA+Tarjin)
- 在 Oracle Linux 上使用 DTrace
- 得到java异常printStackTrace的详细信息
- WebLogic(12C)——简单公布和JDBC
- JDK和TOMCAT的安装与配置环境变量
- Cocos2d-x3.1下 Android,APK自己主动升级
- 使用Hibernate防止SQL注入的方法