首页 / 软件开发 / 数据结构与算法 / 水洼的数量算法 代码（C）

水洼的数量算法 代码（C）2015-10-28题目: 有一个大小为N*M的园子, 雨后起了积水. 八连通的积水被认为是连接在一起的. 请求出园子里总共有多少水洼.

使用深度优先搜索（DFS）, 在某一处水洼, 从8个方向查找, 直到找到所有连通的积水. 再次指定下一个水洼, 直到没有水洼为止.

则所有的深度优先搜索的次数, 就是水洼数. 时间复杂度O（8*M*N）=O（M*N）.

代码:

/** main.cpp**Created on: 2014.7.12* *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
", res）;}};int main（void）{Program P;P.solve（）;return 0;}

输出:

result = 3

作者：csdn博客 Mystra