C++ 数据结构之水洼的数量算法

概述C++数据结构之水洼的数量算法题目:有一个大小为N*M的园子,雨后起了积水.八连通的积水被认为是连接在一起的.请求出园子里总共有多少水洼.

C++ 数据结构之水洼的数量算法

题目: 有一个大小为N*M的园子,雨后起了积水. 八连通的积水被认为是连接在一起的. 请求出园子里总共有多少水洼.

使用深度优先搜索(DFS),在某一处水洼,从8个方向查找,直到找到所有连通的积水. 再次指定下一个水洼,直到没有水洼为止.
则所有的深度优先搜索的次数,就是水洼数. 时间复杂度O(8*M*N)=O(M*N).

代码:

/*  * 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; }

输出:

result = 3

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

总结

以上是内存溢出为你收集整理的C++ 数据结构之水洼的数量算法全部内容，希望文章能够帮你解决C++ 数据结构之水洼的数量算法所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。