C++ 数据结构之水洼的数量算法
题目: 有一个大小为N*M的园子, 雨后起了积水. 八连通的积水被认为是连接在一起的. 请求出园子里总共有多少水洼.
使用深度优先搜索(DFS), 在某一处水洼, 从8个方向查找, 直到找到所有连通的积水. 再次指定下一个水洼, 直到没有水洼为止.
则所有的深度优先搜索的次数, 就是水洼数. 时间复杂度O(8*M*N)=O(M*N).
代码:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
/*
* main.cpp
*
* Created on: 2014.7.12
*本栏目更多精彩内容：http://www.bianceng.cn/Programming/sjjg/
* Author: spike
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
class Program {
static const int MAX_N=20, MAX_M=20;
int N = 10, M = 12;
char field[MAX_N][MAX_M+1] = {
"W........WW.",
".WWW.....WWW",
"....WW...WW.",
".........WW.",
".........W..",
"..W......W..",
".W.W.....WW.",
"W.W.W.....W.",
".W.W......W.",
"..W.......W."};
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 = x+dx, ny = y+dy;
if (0<=dx&&nx<N&&0<=ny&&ny<=M&&field[nx][ny]=='W') dfs(nx, ny);
}
}
return;
}
public:
void solve() {
int res=0;
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
if (field[i][j] == 'W') {
dfs(i,j);
res++;
}
}
}
printf("result = %d\n", res);
}
};
int main(void)
{
Program P;
P.solve();
return 0;
}
|
输出:
|
1
|
result = 3
|
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
原文链接：http://www.bianceng.cn/Programming/sjjg/201510/49243.htm