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

—-想了解C++ 数据结构之水洼的数量算法分享的全部内容且更多的C语言教程关注<计算机技术网(www.ctvol.com)!!>

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

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

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

代码:

  /*    * main.cpp    *    * Created on: 2014.7.12    *本栏目更多精彩内容：https://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 = %dn", res);     }   };             int main(void)   {     Program P;     P.solve();     return 0;   }  

输出:

  result = 3

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