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

2024-03-06 21:15:48

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++数据结构之文件压缩(哈夫曼树)实例详解概要: 项目简介:利用哈夫曼编码的方式对文件进行压缩,并且对压缩文件可以解压开发环境:windows vs2013 项目概述: 1.压缩 a.读取文件,将每个字符,该字符出现的次数和权值构成哈夫曼树 b.哈夫曼树是利用小堆构成,字符出现次数少的节点指针存在堆顶,出现次数多的在堆底 c.每次取堆顶的两个数,再将两个数相加进堆,直到堆被取完,这时哈夫曼树也建成 d.从哈夫曼树中获取哈夫曼编码,然后再根据整个字符数组来获取出现了得字符的编
C++语言数据结构串的基本操作实例代码

C语言数据结构串的基本操作实例代码输出结果: 实现代码: #include<iostream> using namespace std; typedef int Status; #define Max 20 #define OK 1 #define ERROR 0 #define OVERLOE -2 typedef struct//堆分配表示串 { char *ch; int length; }HString; //====================================
C++ 数据结构完全二叉树的判断

C++ 数据结构完全二叉树的判断完全二叉树(Complete Binary Tree):若设二叉树的深度为h,除第h层外,其他各层(1~h-1)的节点数都达到最大个数,第h层所有的节点都连续集中在最左边,这就是完全二叉树.完全二叉树由满二叉树而引起来的.对于深度为K的,有n个节点的二叉树,当且仅当每一个节点都与深度为K的满二叉树中编号从1到n的节点一一对应时称之为完全二叉树. 注意:满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树. 完全二叉树的特点:完全二叉树的效率极高,堆是一种完全二
C++ 数据结构之kmp算法中的求Next()函数的算法

C++ 数据结构之kmp算法中的求Next()函数的算法实例代码: #include <iostream> using namespace std; void preKmp(char *c, int m, int Next[]) { int i=1,j=-1; Next[0]=-2; while(i<m) { if(j==-2) { Next[i]=-1; i++; j=-1; } ++j; if(i==m) return; if(c[i]==c[j]) { Next[i]=j; ++
C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）

C++ 数据结构二叉树(前序/中序/后序递归.非递归遍历) 二叉树的性质: 二叉树是一棵特殊的树,二叉树每个节点最多有两个孩子结点,分别称为左孩子和右孩子. 例: 实例代码: #include <iostream> #include <Windows.h> #include <stack> using namespace std; template <class T> struct BinaryTreeNode { int _data; BinaryTree
C++ 数据结构堆排序的实现

堆排序(heapsort)是一种比较快速的排序方式,它的时间复杂度为O(nlgn),并且堆排序具有空间原址性,任何时候只需要有限的空间来存储临时数据.我将用c++实现一个堆来简单分析一下. 堆排序的基本思想为: 1.升序排列,保持大堆:降序排列,保持小堆: 2.建立堆之后,将堆顶数据与堆中最后一个数据交换,堆大小减一,然后向下调整:直到堆中只剩下一个有效值: 下面我将简单分析一下: 第一步建立堆: 1.我用vector顺序表表示数组: 2.用仿函数实现大小堆随时切换,实现代码复用: 3.实现向下
C++数据结构与算法之判断一个链表是否为回文结构的方法

本文实例讲述了C++判断一个链表是否为回文结构的方法.分享给大家供大家参考,具体如下: 题目: 给定一个链表头节点head,请判断是否为回文结构例如: 1->2->1 true 1->2->2->1 true 1->2->3->4->2->1 false 解题思路及代码 1.找到链表中间节点,然后将链表中间节点的右边所有节点放入一个栈中. 2.然后从链表首节点和栈顶元素一一对比,不相等则return false. 算法C++代码: 链表节点结构
C++ 冒泡排序数据结构、算法及改进算法

程序代码如下: 复制代码代码如下: // BubbleSort.cpp : 定义控制台应用程序的入口点.//#include "stdafx.h"#include <cmath>#include <iostream>using namespace std;#define MAXNUM 20template<typename T>void Swap(T& a, T& b){ int t = a; a = b; b
C++ 数据结构之水洼的数量算法

C++ 数据结构之水洼的数量算法题目: 有一个大小为N*M的园子, 雨后起了积水. 八连通的积水被认为是连接在一起的. 请求出园子里总共有多少水洼. 使用深度优先搜索(DFS), 在某一处水洼, 从8个方向查找, 直到找到所有连通的积水. 再次指定下一个水洼, 直到没有水洼为止. 则所有的深度优先搜索的次数, 就是水洼数. 时间复杂度O(8*M*N)=O(M*N). 代码: /* * main.cpp * * Created on: 2014.7.12 *本栏目更多精彩内容:http://ww
JS实现计算小于非负数n的素数的数量算法示例

本文实例讲述了JS实现计算小于非负数n的素数的数量算法.分享给大家供大家参考,具体如下: 计算小于非负数n的素数的数量例: 输入: 10 输出: 4 说明:有4个素数小于10,它们是2,3,5,7. JS算法示例: <script> var countPrimes = function(n) { let flagArray = [], result = 0; for(let i = 2; i < n; i++){ if(flagArray[i] === undefined){ flag
Python 数据结构之十大经典排序算法一文通关

目录 1.冒泡排序算法演示算法步骤算法实现 2.选择排序算法演示算法步骤算法实现 3.简单插入排序算法演示算法步骤算法实现 4.希尔排序算法演示算法步骤算法实现 5.归并排序算法演示算法步骤算法实现 6.快速排序算法演示算法步骤算法实现 7.堆排序算法演示算法步骤算法实现 8.计数排序算法演示算法步骤算法实现 9.桶排序算法演示算法步骤算法实现 10.基数排序算法演示算法步骤算法实现一文搞掂十大经典排序算法今天整理一下十大经典排序算
Java数据结构之图的路径查找算法详解

目录前言算法详解实现 API设计代码实现前言在实际生活中,地图是我们经常使用的一种工具,通常我们会用它进行导航,输入一个出发城市,输入一个目的地城市,就可以把路线规划好,而在规划好的这个路线上,会路过很多中间的城市.这类问题翻译成专业问题就是: 从s顶点到v顶点是否存在一条路径?如果存在,请找出这条路径. 例如在上图上查找顶点0到顶点4的路径用红色标识出来,那么我们可以把该路径表示为 0-2-3-4. 如果对图的前置知识不了解,请查看系列文章: [数据结构与算法]图的基础概念和数据
Java数据结构之基于比较的排序算法基本原理及具体实现

目录 1. 七大基于比较的排序-总览 1.1常见基于比较的排序分类 1.2时间复杂度,空间复杂度以及稳定性. 2.直接插入排序 2.1 直接插入排序的基本思想 2.2 直接插入排序动画演示 2.3 代码示例 2.4 时间复杂度,空间复杂度以及稳定性 3. 希尔排序 3.1 算法思想 3.2 图片演示 3.3 代码示例 3.4 时间复杂度,空间复杂度以及稳定性 4.选择排序 4.1 算法思想 4.2 动画演示 4.3 代码示例 4.4 时间复杂度,空间复杂度以及稳定性 5.堆排序 5.1 算法思想
C语言数据结构之连续存储数组的算法

数据结构之数组定义及基本操作数据结构中最基本的一个结构就是线性结构,而线性结构又分为连续存储结构和离散存储结构.所谓的连续存储结构其实就是数组. 数组本质其实也是数据的一种存储方式,既然有了数据的存储,就会涉及到如何对数据进行寻址的问题.首先,先说一下在数组中数据是如何存储的,在内存中,数组中的数据是以一组连续的数据集合的形式存在于内存中.当我们访问存在于内存中的数组时,我们应该找到其在内存中的地址,当我们找到数据的地址后我们就可以找到对应的数据.了解了以上知识后,我们就可以进行数组的设计了(
java数据结构基础:算法

目录数据结构和算法关系高斯求和算法定义算法的特性算法设计的要求算法效率的度量方法函数的渐进增长总结数据结构和算法关系虽然这个标题起的叫数据结构,但是我却总结算法...我不是没事找抽,只是呢,在学数据结构的时候,算法是你肯定离不开的东西. 你平时在网上看到的那些文章,在你不经意间搜的时候,是不是都是搜的数据结构与算法这七个字.这说明啥,这说明他们俩是离不开的. 给你打个比方,你想看德云社相声(我也想看),有一天你最想看小岳岳专场,想看小白专场.但是呢,走到园子里之后发现,他们今
Python基于Floyd算法求解最短路径距离问题实例详解

本文实例讲述了Python基于Floyd算法求解最短路径距离问题.分享给大家供大家参考,具体如下: Floyd算法和Dijkstra算法,相信大家都不陌生,在最短路径距离的求解中应该算得上是最为基础和经典的两个算法了,今天就用一点时间来重新实现一下,因为本科的时候学习数据结构才开始接触的这个算法,当时唯一会用的就是C语言了,现在的话,C语言几乎已经离我远去了,个人感觉入手机器学习以来python更得我心,因为太通俗易懂了,带给你的体验自然也是非常不错的. 当然网上有很多的算法讲解教程,我不会在
c# 实现位图算法（BitMap）

算法原理 BitMap的基本思想就是用一个bit位来标记某个元素对应的Value,而Key即是该元素.由于采用了Bit为单位来存储数据,因此可以大大节省存储空间. BitMap可以看成一种数据结构. 假设有这样一个需求:在20亿个随机整数中找出某个数m是否存在其中,并假设32位操作系统,4G内存. 在Java中,int占4字节,1字节=8位(1 byte = 8 bit). 如果每个数字用int存储,那就是20亿个int,因而占用的空间约为 (2000000000*4/1024/1024/102
Java 手写LRU缓存淘汰算法

概述 LRU 算法全称为 Least Recently Used 是一种常见的页面缓存淘汰算法,当缓存空间达到达到预设空间的情况下会删除那些最久没有被使用的数据 . 常见的页面缓存淘汰算法主要有一下几种: LRU 最近最久未使用 FIFO 先进先出置换算法类似队列 OPT 最佳置换算法 (理想中存在的) NRU Clock 置换算法 LFU 最少使用置换算法 PBA 页面缓冲算法 LRU 的原理 LRU 算法的设计原理其实就是计算机的局部性原理(这个局部性原理包含了空间局部性和时间

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

相关推荐

随机推荐