189 8069 5689

C++数据结构之如何实现水洼数量算法

这篇文章给大家分享的是有关C++数据结构之如何实现水洼数量算法的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。

创新互联专注为客户提供全方位的互联网综合服务，包含不限于网站建设、成都做网站、抚远网络推广、成都小程序开发、抚远网络营销、抚远企业策划、抚远品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们最大的嘉奖；创新互联为所有大学生创业者提供抚远建站搭建服务，24小时服务热线：13518219792，官方网址：www.cdcxhl.com

题目: 有一个大小为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  
#include  
#include  
#include  
   
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
输出:
result = 3
感谢各位的阅读！关于“C++数据结构之如何实现水洼数量算法”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！
            
            
                        

            网页标题：C++数据结构之如何实现水洼数量算法            

            分享地址：http://cdxtjz.cn/article/jehjdg.html

其他资讯