文档章节

深度优先搜索的用法——lake counting

自由的角马
 自由的角马
发布于 2015/01/10 13:57
字数 433
阅读 20
收藏 0

深度优先搜索的用法——lake counting

问题主题:Lake Counting

问题描述:

有一个大小为N*M的园子,雨后积了很多水。八连通的积水被认为是在一起的。请求出园子里共有多少个水洼?(八连通是指下图中相对+*部分)

+++

+*+

+++

限制条件:

N,M <= 100

样例:

输入

N=10, M=12

园子如下图(‘+’表示积水,’*’表示没有积水)

+********++*

*+++*****+++

****++***++*

*********++*

*********+**

**+******+**

*+*+*****++*

+*+*+*****+*

*+*+******+*

**+*******+*

输出

3

 

 

【解法一】

解题分析:

    从任意的’+’开始,不停地把邻接的部分用’*’代替,一次dfs(深度优先遍历)遍历后,与初始的这个+所连接的所有+都会被替换成*,因此直到图中没有+为止,总共进行dfs的次数即为积水的次数。

程序实现:

 

C++

 

#include "iostream"

 

using namespace std;

 

const int N = 10;

const int M = 12;

 

char garden[N][M+1] = {

"+********++*",

"*+++*****+++",

"****++***++*",

"*********++*",

"*********+**",

"**+******+**",

"*+*+*****++*",

"+*+*+*****+*",

"*+*+******+*",

"**+*******+*"

};

 

void dfs(int x, int y);

 

void solve() {

int count = 0;

for(int j=0; j<N; j++) {

for(int i=0; i<M; i++){

if(garden[j][i] == '+') {

dfs(j, i);

count ++;

}

}

}

cout << count << endl;

}

 

void dfs(int y, int x) {

garden[y][x] = '*';

for(int dy=y-1; dy<=y+1; dy++) {

for(int dx=x-1; dx<=x+1; dx++) {

if(dx >=0 && dy >= 0 && dx < M && dy < N && garden[dy][dx] == '+') {

dfs(dy, dx);

}

}

}

}

 

int main() {

solve();

return 0;

}

 

Java

/**
 * User: luoweifu
 * Date: 14-1-7
 * Time: 下午4:53
 */
public class LakeCounting {
public static final int N = 10;
public static final int M = 12;
private String garden[] = {
"+********++*",
"*+++*****+++",
"****++***++*",
"*********++*",
"*********+**",
"**+******+**",
"*+*+*****++*",
"+*+*+*****+*",
"*+*+******+*",
"**+*******+*"
};
 
public void solve() {
int count = 0;
for(int j=0; j<N; j++) {
for(int i=0; i<M; i++){
if(garden[j].charAt(i) == '+') {
dfs(j, i);
count ++;
}
}
}
System.out.println(count);
}
 
public void dfs(int y, int x) {
StringBuilder stringY = new StringBuilder(garden[y]);
stringY.setCharAt(x, '*');
garden[y] = stringY.toString();
for(int dy=y-1; dy<=y+1; dy++) {
for(int dx=x-1; dx<=x+1; dx++) {
if(dx >=0 && dy >= 0 && dx < M && dy < N && garden[dy].charAt(dx) == '+') {
dfs(dy, dx);
}
}
}
}
 
public static void main(String args[]) {
LakeCounting lakeCounting = new LakeCounting();
lakeCounting.solve();
}
}

 

 

本文转载自:http://blog.csdn.net/luoweifu/article/details/17886463

自由的角马
粉丝 1
博文 269
码字总数 0
作品 0
文山
私信 提问
【递归】【DSF】POJ No.2386 Lake Counting

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. ......

一字马胡
2017/12/03
0
0
Node中的两种遍历方式-深度优先和广度优先(附Node删除文件例子进行详解)

树的基本概念 树(Tree)是 个结点的有限集, 为 时,称为空树,在任意一棵非空树中有且仅有一个特定的被称为根(Root)的结点,当 大于 时,其余结点可分为 个互不相交的有限集 、、、,其中...

2018/09/14
0
0
图的遍历——深度优先搜索(Depth First Search)

1.深度优先搜索(Depth First Search)遍历类似于树的先根遍历,是树的先根遍历的推广。 假设初始状态是图中所有的顶点未曾被访问,则深度优先搜索可从图中某个顶点V出发,访问此顶点,然后依...

啊哈关关
2018/01/20
1K
0
图的连通性——无向图的连通分量和生成树

1.首先举个实例来说明连通性,看下图: 图G1 上图为非连通图,对上图的连接表进行深度优先搜索遍历,3次调用DFS过程,分别从顶点A,D,G出发,得到的顶点访问序列为: A L M J B F C D E G I ...

啊哈关关
2018/01/20
658
0
基本算法——深度优先搜索(DFS)和广度优先搜索(BFS)

深度优先搜索和广度优先搜索,都是图形搜索算法,它两相似,又却不同,在应用上也被用到不同的地方。这里拿一起讨论,方便比较。 一、深度优先搜索 深度优先搜索属于图算法的一种,是一个针对...

安然若知
2018/07/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

JMM内存模型(一)&volatile关键字的可见性

在说这个之前,我想先说一下计算机的内存模型: CPU在执行的时候,肯定要有数据,而数据在内存中放着呢,这里的内存就是计算机的物理内存,刚开始还好,但是随着技术的发展,CPU处理的速度越...

走向人生巅峰的大路
22分钟前
45
0
你对AJAX认知有多少(2)?

接着昨日内容,我们几天继续探讨ajax的相关知识点 提到ajax下面几个问题又是必须要了解的啦~~~ 8、在浏览器端如何得到服务器端响应的XML数据。 通过XMLHttpRequest对象的responseXMl属性 9、 ...

理性思考
32分钟前
4
0
正则表达式基础(一)

1.转义 转义的作用: 当某个字符在表达式中具有特殊含义,例如字符串引号中出现了引号,为了可以使用这些字符本身,而不是使用其在表达式中的特殊含义,则需要通过转义符“\”来构建该字符转...

清自以敬
34分钟前
4
0
idea中@Data标签getset不起作用

背景:换电脑以后在idea中有@data注解都不生效 解决办法:idea装个插件 https://blog.csdn.net/seapeak007/article/details/72911529...

栾小糖
40分钟前
5
0
Apache Kudu 不能删除不存在的数据

使用Apache Kudu客户端,对KafkaConnect Sink 进行扩展。 使用的Apache Kudu 的Java 客户端。突然有天发现作业无法提交,一直报错。 后来才发现这是Kudu自身的一种校验机制。为了忽略这种校验...

吐槽的达达仔
50分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部