热门标签 | HotTags
当前位置:  开发笔记 > 人工智能 > 正文

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

这篇文章主要介绍了C++数据结构之水洼的数量算法的相关资料,需要的朋友可以参考下

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  
#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

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


推荐阅读
  • 本题要求实现一个名为fun的函数,该函数的功能是从给定的字符串s中移除所有ASCII码为偶数值的字符,并将剩下的字符组成的新字符串存储在由t指向的数组中。 ... [详细]
  • 知识图谱与图神经网络在金融科技中的应用探讨
    本文详细介绍了融慧金科AI Lab负责人张凯博士在2020爱分析·中国人工智能高峰论坛上的演讲,探讨了知识图谱与图神经网络模型如何在金融科技领域发挥重要作用。 ... [详细]
  • 在OpenCV 3.1.0中实现SIFT与SURF特征检测
    本文介绍如何在OpenCV 3.1.0版本中通过Python 2.7环境使用SIFT和SURF算法进行图像特征点检测。由于这些高级功能在OpenCV 3.0.0及更高版本中被移至额外的contrib模块,因此需要特别处理才能正常使用。 ... [详细]
  • 张正友相机标定算法解析:无需棋盘格
    本文深入探讨了张正友教授于1998年提出的单平面标定技术,该方法结合了传统标定与自标定的优势,通过简易的棋盘格实现了高效准确的相机标定。 ... [详细]
  • 使用 MATLAB 将高光谱数据集转换为伪彩色 CIE 图像
    本文介绍了一种方法,通过 MATLAB 将高光谱数据集的每个维度的图像转换为伪彩色 CIE 图像。用户只需指定波段即可完成转换。 ... [详细]
  • 本文总结了一次针对大厂Java研发岗位的面试经历,探讨了面试中常见的问题及其背后的原因,并分享了一些实用的面试准备资料。 ... [详细]
  • Windows操作系统提供了Encrypting File System (EFS)作为内置的数据加密工具,特别适用于对NTFS分区上的文件和文件夹进行加密处理。本文将详细介绍如何使用EFS加密文件夹,以及加密过程中的注意事项。 ... [详细]
  • 深入解析WebP图片格式及其应用
    随着互联网技术的发展,无论是PC端还是移动端,图片数据流量占据了很大比重。尤其在高分辨率屏幕普及的背景下,如何在保证图片质量的同时减少文件大小,成为了亟待解决的问题。本文将详细介绍Google推出的WebP图片格式,探讨其在实际项目中的应用及优化策略。 ... [详细]
  • 菜鸟物流用户增长部现正大规模招聘P6及以上级别的JAVA工程师,提供年后入职选项。 ... [详细]
  • 深入解析层次聚类算法
    本文详细介绍了层次聚类算法的基本原理,包括其通过构建层次结构来分类样本的特点,以及自底向上(凝聚)和自顶向下(分裂)两种主要的聚类策略。文章还探讨了不同距离度量方法对聚类效果的影响,并提供了具体的参数设置指导。 ... [详细]
  • QQ推出新功能:个性化QID身份卡
    您是否还记得曾经风靡一时的即时通讯工具QQ?近日,QQ悄然上线了一项新功能——QID身份卡。这项功能将如何改变用户的社交体验?本文为您详细解读。 ... [详细]
  • 本文详细介绍了如何在ARM架构的目标设备上部署SSH服务端,包括必要的软件包下载、交叉编译过程以及最终的服务配置与测试。适合嵌入式开发人员和系统集成工程师参考。 ... [详细]
  • Bootstrap Paginator 分页插件详解与应用
    本文深入探讨了Bootstrap Paginator这款流行的JavaScript分页插件,提供了详细的使用指南和示例代码,旨在帮助开发者更好地理解和利用该工具进行高效的数据展示。 ... [详细]
  • 深入理解云计算与大数据技术
    本文详细探讨了云计算与大数据技术的关键知识点,包括大数据处理平台、社会网络大数据、城市大数据、工业大数据、教育大数据、数据开放与共享的应用,以及搜索引擎与Web挖掘、推荐技术的研究及应用。文章还涵盖了云计算的基础概念、特点和服务类型分类。 ... [详细]
  • 八段代码完全控制Promise
    1.Promise的马上实行性varpnewPromise(function(resolve,reject){console.log(createapromise);resolve ... [详细]
author-avatar
10651s
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有