当前位置：首页 > 编程日记 > 正文

不相交集类以及应用迷宫生成

编程日记 2024-01-31 18:00:01

简单介绍：

考虑一个迷宫的生成，一个简单算法就是从各处的墙壁开始（除入口和出口之外）。此时，不断地随机选择一面墙，如果被该墙分割的单元彼此不联通，那么就把这面墙拆掉。重复这个过程直到开始单元和终止单元联通，那么就得到一个迷宫。实际上不断的拆掉墙壁直到每个单元都可以从其他单元到达更好（这会使迷宫产生更多误导的路径）。

因此主要是两个问题：

1. 拆掉墙如果两个单元不连通。

2. 保留墙如果两个单元已经联通。

这里用于判断不同单元是否在同一集合的数据结构即为不相交集类。

基本知识：

即我们要建立多个等价类，联通的元素放在同一个等价类里面。

对应的，需要两个操作：

1. 将两个元素放到一个等价类里的话，采用union操作。

2. 查找某个元素在哪个等价类里，采用find操作。根据find的返回值可以判断两个元素是否在一个等价类里。

可以用数组来记录，程序里我使用的是vector（仿照书里的）。

举个例子看可能比较清楚：

假设元素ID刚开始为 0 1 2 3 4 5 6 7 8 9

建立相同大小的数组s，数组初始化值均为-1。

最直观的处理，比如union(4,5)即使s[5] = 4。（约定union(x,y)使得s[y]=x，效果是相同的）。

find(4)会直接返回4本身，因为s[4]<0。

而find(5)则递归调用，实际上为:find(5) = find(s[5]) = 4，因此判断出4，5属于同一个等价类（我觉得可以理解为4这个结点即为等价类的代表）。

find最坏情形运行时间为O（N），因为对N个元素，有可能建立一个深度为N-1的树。

因此对union和find操作都进行了改进。

为了控制树的深度，可以重写union的方式，比如unionBySize,unionByHeight，书上都介绍，这里就不说了。此时find运行时间为O(N)。

另外对于find巧妙的改进是路径压缩，即当find（x）调用时，修改递归找到的结点直接指向等价类的代表结点，使得路径上的结点移近根结点，这样下次调用时就很快了。

正如书上所说：

这种数据结构实现起来很简单，每个例程只需要几行代码，而且可以使用一个简单的数组。

clip_image002

clip_image004

可以看到迷宫差别很大，我只是使得入口出口两个单元连通起来即结束循环。

效率什么的没有考虑。

所有的代码：数据集合类，迷宫生成类

/********************************************************************************
 **
 **       Filename:  DisjSets.h
 **
 **    Description:  
 **
 **        Version:  1.0
 **        Created:  2011年12月06日 11时43分46秒
 **       Revision:  none
 **       Compiler:  gcc
 **
 **         Author:  zhy (), izualzhy@163.com
 **        Company:  
 **
 *********************************************************************************/
#ifndef DISJSETS_H
#define DISJSETS_H
#include <vector>
#include <iostream>
using namespace std;class DisjSets {public:explicit DisjSets(int numElements);int find(int x);void unionSets(int root1, int root2);private:vector<int> s;
};
#endif//DISJSETS_H

/********************************************************************************
 **
 **       Filename:  DisjSets.cpp
 **
 **    Description:  
 **
 **        Version:  1.0
 **        Created:  2011年12月06日 11时45分09秒
 **       Revision:  none
 **       Compiler:  gcc
 **
 **         Author:  zhy (), izualzhy@163.com
 **        Company:  
 **
 *********************************************************************************/
#include "DisjSets.h"DisjSets::DisjSets(int numElements) : s(numElements)
{for ( int i=0; i<s.size(); ++i)s[i] = -1;
}int DisjSets::find(int x)
{//cout << "DisjSets::find x= " << x << "\ts[x] = " << s[x] << endl;if (s[x]<0)return x;else {s[x] = find(s[x]);return s[x];}
}void DisjSets::unionSets(int root1, int root2)
{if (s[root1]>s[root2]) {s[root1] = root2;} else {if (s[root1]==s[root2])s[root1]--;s[root2] = root1;}
}

/********************************************************************************
 **
 **       Filename:  MazeDataGenerator.h
 **
 **    Description:  generator the data of maze
 **
 **        Version:  1.0
 **        Created:  2011年12月06日 14时49分09秒
 **       Revision:  none
 **       Compiler:  gcc
 **
 **         Author:  zhy (), izualzhy@163.com
 **        Company:  
 **
 *********************************************************************************/
#ifndef MAZEDATAGENERATOR_H
#define MAZEDATAGENERATOR_H
#include <vector>
#include "DisjSets.h"
class Room{public:Room(int row, int col) :i(row) ,j(col){for ( int i=0; i<4; ++i)wall[i] = true;}int i;int j;bool wall[4];bool operator==(const Room &room2){return ((this->i)==(room2.i) && (this->j==room2.j));}
};class MazeDataGenerator {public:enum Direction{NORTH,EAST,SOUTH,WEST};MazeDataGenerator(int row, int column);~MazeDataGenerator(){delete mData;mData = NULL;for ( int i=0; i<mRows; ++i)for ( int j=0; j<mColumns; ++j)delete mRoom[i][j];for ( int i=0; i<mRows; ++i)delete [] mRoom[i];delete [] mRoom;}void print();private:bool isConnected(Room *room1, Room *room2) {return (mData->find(room1->i*mColumns+room1->j)==mData->find(room2->i*mColumns+room2->j));}void initRoad();bool connectTworoom(Room *room1, Room *room2, Direction d);private:DisjSets *mData;Room ***mRoom;int mColumns;int mRows;
};
#endif//MAZEDATAGENERATOR_H

/********************************************************************************
 **
 **       Filename:  MazeDataGenerator.cpp
 **
 **    Description:  
 **
 **        Version:  1.0
 **        Created:  2011年12月06日 14时51分42秒
 **       Revision:  none
 **       Compiler:  gcc
 **
 **         Author:  zhy (), izualzhy@163.com
 **        Company:  
 **
 *********************************************************************************/
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include "MazeDataGenerator.h"MazeDataGenerator::MazeDataGenerator(int row, int column) :mRows(row) ,mColumns(column) 
{srand(time(NULL));mData = new DisjSets(row*column);mRoom = new Room**[row];for ( int i=0; i<row; ++i)mRoom[i] = new Room*[column];for ( int i=0; i<row; ++i)for ( int j=0; j<column; ++j)mRoom[i][j] = new Room(i,j);mRoom[0][0]->wall[NORTH] = mRoom[0][0]->wall[EAST] = false;mRoom[mRows-1][mColumns-1]->wall[SOUTH] = mRoom[0][0]->wall[WEST] = false;initRoad();
}void MazeDataGenerator::initRoad()
{printf("%s\n",__FUNCTION__);Room *room = mRoom[0][0];while (!isConnected(mRoom[0][0],mRoom[mRows-1][mColumns-1])) {Direction side = (Direction)(rand()%4);int i = room->i;int j = room->j;switch(side) {case NORTH:i = room->i-1;break;case SOUTH:i = room->i+1;break;case EAST:j = room->j-1;break;case WEST:j = room->j+1;break;}if (i<0 || i>=mRows || j<0 || j>=mColumns)continue;if (!isConnected(mRoom[room->i][room->j],mRoom[i][j]))connectTworoom(mRoom[room->i][room->j],mRoom[i][j],side);room = mRoom[i][j];//print();}
}bool MazeDataGenerator::connectTworoom(Room *room1, Room *room2, Direction d)
{//printf("%s\n",__FUNCTION__);//printf("(%d,%d)-->(%d,%d)\n",room1.i,room1.j,room2.i,room2.j);if (room1==room2)return false;int index1 = room1->i*mColumns+room1->j;int index2 = room2->i*mColumns+room2->j;int root1 = mData->find(index1);int root2 = mData->find(index2);if (root1==root2) return false;mData->unionSets(root1,root2);room1->wall[d] = false;room2->wall[(d+2)%4] = false;return true;
}void MazeDataGenerator::print()
{printf("%s\n",__FUNCTION__);for ( int i=0; i<mRows; ++i) {for ( int j=0; j<mColumns; ++j)printf("%2d ",mData->find(mRows*i+j));printf("\n");}for (int j=0; j<mColumns; ++j)printf("__");printf("\n");for ( int i=0; i<mRows; ++i) {for ( int j=0; j<mColumns; ++j) {char s[3] = "  ";if (((j-1<0) && i!=0) || mRoom[i][j]->wall[1]) s[0]='|';if ((i+1)>=mRows || mRoom[i][j]->wall[2]) s[1]='_';printf("%s",s);if ((j+1)==mColumns && i!=mRows-1) printf("|");}printf("\n");}
}

参考资料：

数据结构与算法分析—C++描述

转载自 http://www.cppblog.com/izualzhy/archive/2011/12/11/161913.html

https://www.dkcj.cn/info/1132.html

Ajax 完整教程

转载：http://www.cnblogs.com/Garden-blog/archive/2011/03/11/1981778.html Ajax 完整教程第 1 页 Ajax 简介Ajax 由 HTML、JavaScript™ 技术、DHTML 和 DOM 组成，这一杰出的方法可以将笨拙的 Web 界面转化成交互性的 Ajax 应用程序。本文的作者是一位…

编程日记2024/01/31 17:30:00

python嵩天课后思考题_Python语言程序设计基础（第二版）嵩天等课后习题答案

第一次博文 Time：2018年04月28日星期六 11:37二次补充 2018年05月02日第一章程序设计基本方法 P29# 1.1字符串的拼接str1 input("请输入一个人的名字：")str2 input("请输入一个地点：")print("世界这么大&#x…

编程日记2024/01/31 17:00:00

mac OneNote恢复历史记录

由于mac OneNote是个废物，因此还是得通过网页版OneNote或者win版OneNote来操作网页端OneNote-对应笔记本页面然后复制过去就可以恢复了

编程日记2024/01/31 16:30:00

【C#公共帮助类】10年代码，最全的系统帮助类

这个帮助类主要包含：对象转换处理、分割字符串、截取字符串、删除最后结尾的一个逗号、删除最后结尾的指定字符后的字符、生成指定长度的字符串、生成日期随机码、生成随机字母或数、字截取字符长度、对象<-->JSON 4.0使用、对象<-->JSON 2.0使…

编程日记2024/01/31 16:00:02

三十之惑–面霸的八月（第一部分）

三十之惑 –面霸的八月题记： 三十几岁了，从sina大学肄业后，在外面漂泊，不好不坏。从好的角度讲，这几年自己的技术没有减退，偶尔也还能够略有深入，同时能够更多的接触到产品、运营、甚至营销&a…

编程日记2024/01/31 15:30:00

python小工具封装_python接口自动化（二）——封装需要用到的工具类

封装需要用的工具类：1、封装读取Excel的工具类，这里选用的是pandas：importpandas as pdpath ‘test.xlsx‘sheet_name ‘test_data‘classwith_excel:#构造函数，调用类时就运行def __init__(self, pathNone, sheet_nameNone):if p…

编程日记2024/01/31 15:00:00

三十之惑–面霸的八月（第二部分）

书接上回，今天叙述小米的面试经历。这里可能有一些技术理解和技术方案，欢迎讨论。另昨天共计收入7笔共95元，够我喝几杯咖啡了，谢谢所有捐钱的朋友。如果你心疼我码字辛苦，有钱朋友钱场，没钱的请拉朋友来捧…

编程日记2024/01/31 14:30:01

Curator Cache

1.Curator Cache 与原生ZooKeeper Wacher区别原生的ZooKeeper Wacher是一次性的：一个Wacher一旦触发就会被移出，如果你想要反复使用Wacher，就要在Wacher被移除后重新注册，使用起来很麻烦。使用Curator Cache 可以反复使用Wacher了…

编程日记2024/01/31 14:00:00

程序可以在硬件之间发送吗_你知道硬件、软件工程师之间，还有一个固件工程师吗？...

软件跟硬件之间的界限已经越来越模糊了，那么处于这个灰色地带的，就是固件了。这就分成三类工作者。1、软件工程师一般指做图形界面的程序员，工作内容就是写C、JAVA、Web等。2、硬件工程师当然是指玩电路板的，工作内容就是画原理图…

编程日记2024/01/31 13:30:00

悲催的跨平台文献管理能力

1.古老的TCP交互邮箱、FTP、硬盘 2.用现成软件Zotero 免费、跨平台、导入后在Win福昕注释可实时同步mac看看人生苦短，我用Zotero。。

编程日记2024/01/31 13:00:00

Mastering Algorithms with C中文版附带源码说明

Mastering Algorithm with C是一本非常经典和独具个性的算法书,主要是从程序员的角度,对算法领域的基本内容,通过C语言进行源码实现,其附带的源码非常详细,对初接触这个领域的程序员很有参考价值.我特地将该书源码的使用方法做了笔记,放在这样,以便日后参考. 下面是该书的封面…

编程日记2024/01/31 12:30:00

仿qq左滑删除listview_Java基于Swing和Netty仿QQ界面聊天小项目

点击上方好好学java ，选择星标公众号重磅资讯、干货，第一时间送达今日推荐：硬刚一周，3W字总结，一年的经验告诉你如何准备校招！个人原创100W访问量博客：点击前往，查看更多来源&…

编程日记2024/01/31 12:00:00

[BZOJ1602] [Usaco2008 Oct] 牧场行走 (LCA)

Description N头牛（2<n<1000）别人被标记为1到n，在同样被标记1到n的n块土地上吃草，第i头牛在第i块牧场吃草。这n块土地被n-1条边连接。奶牛可以在边上行走，第i条边连接第Ai，Bi块牧场，第i…

编程日记2024/01/31 11:30:00

大数据中用到的新的数据类型bigint、decimal、smallint、tinyint

在对比oracle数据库和大数据库的时候，发现了几个用以存放数字的新的类型bigint、decimal、smallint、tinyint，为了对比之间的不同，我进行了统计 bigint 可以精确的表示从-263到263-1(即从-9,223,372,036,854,775,808到 9,223,372,036,854,77…

编程日记2024/01/31 11:00:14

[综合面试] 计算机面试书籍与求职网站推荐

一、推荐书籍计算机的好书挺多的，我买了也有四五十本，也花了不少钱，但是这些投资都是值的，好好看一下这些书，让自己找工作时的薪水涨个几千是没问题的。当然，也有些书是电子版的。我是c方向的，…

编程日记2024/01/31 10:30:00

python在工厂中的运用_Python常见工厂函数用法示例

工厂函数：能够产生类实例的内建函数。工厂函数是指这些内建函数都是类对象， 当调用它们时，实际上是创建了一个类实例。Python中的工厂函数举例如下：1. int(),long(),float(),complex(),bool()>>> aint(9.9)>>> …

编程日记2024/01/31 10:00:01

Java Random()函数生成指定范围的随机数

java中随机生成数字（指定范围） //随机获得0到（i-1）的一个数 int i ThreadLocalRandom.current().nextInt(i)；

编程日记2024/01/31 09:00:01

删除链表中的重复项

方法一：时间优先建立一个hash_set，key为链表中已经遍历的节点内容，开始时为空。从头开始遍历链表中的节点：- 如果节点内容已经在hash_set中存在，则删除此节点，继续向后遍历；- 如果节点内容不在h…

编程日记2024/01/31 08:30:00

python提取文件名数字_在Python中从文件名提取扩展名

是否有从文件名中提取扩展名的功能？#1楼一种选择可能是与点分开：>>> filename "example.jpeg">>> filename.split(".")[-1]jpeg文件没有扩展名时没有错误：>>> "filename".split(&…

编程日记2024/01/31 08:00:00

下面是 imagick API 中文说明 ： imagick 类 imagick::adaptiveblurimage 向图像中添加 adaptive 模糊滤镜 imagick::adaptiveresizeimage 自适应调整图像数据依赖关系 imagick::adaptivesharpenimage自适应锐化图像 imagick::adaptivethresholdimage 基于范围的选择…

编程日记2024/01/31 07:30:00

利用dom4j将实体类转换为对应的xml报文

利用dom4j生成xml报文目标格式： <?xml version"1.0" encoding"GBK"?><Packet type"REQUEST" version"1.0"><Head><RequestType>C03</RequestType><UserCode>BOCIJS</UserCode…

编程日记2024/01/31 07:00:00

JSP--JavaBean

JSP 最强有力的一个方面就是能够使用 JavaBean 组件。按照 Sun 公司的定义， JavaBean是一个可重复使用的软件组件。实际上 JavaBean 是一种 Java 类，通过封装属性和方法成为具有某种功能或者处理某些业务的对象，简称 Bean。一个基本的 JSP …

编程日记2024/01/31 06:00:00

python 速度矢量_最近邻搜索4D空间python快速-矢量化

For each observation in X (there are 20) I want to get the k(3) nearest neighbors.How to make this fast to support up to 3 to 4 million rows?Is it possible to speed up the loop iterating over the elements? Maybe via numpy, numba or some kind of vectoriza…

编程日记2024/01/31 05:30:00