/* * @Author: lsyy * @Date: 2020-02-28 11:37:49 * @LastEditTime: 2020-02-29 19:59:58 * @LastEditors: Please set LastEditors * @Description: 迷宫 * @FilePath: \DisjSets\Src\main.cpp */#include 
     
        #include 
      
         #include "DisjSets.h"#include "UniformRandom.h"#define N 15bool wallrow[ N + 1 ][ N ] = { 0 };       // 行 _bool wallcol[ N ][ N + 1 ] = { 0 };       // 列 |  /** * @description: 获得二维坐标 * @param {type} Pos 一维坐标 PosX PosY 二维坐标 * @return: null */inline void GetPos( int Pos, int & PosX, int & PosY ){    PosX = Pos / N;    PosY = Pos % N;}/** * @description: 打印迷宫 * @param {type} null * @return: null */void print( ){    for( int i = 0; i < N + 1 ; i++ )    {        if( i == 0 )                    // 打印第一行        {            std::cout << " " << " ";            for (size_t i = 1; i < N; i++)            {                std::cout << " " << "_";            }        }        else        {            for( int j = 0; j < N + 1; j++ )            {                if( ( ( i - 1 ) == 0 && j == 0 ) ||                     ( ( i - 1 ) == ( N - 1 ) && j == N ) )                    std::cout << " ";               // 出入口部分                else                    wallcol[ i - 1 ][ j ] ? std::cout << " " : std::cout << "|";                if( j < N )                    if( i == N && j == ( N - 1 ) )                        std::cout << " ";           // 出入口部分                    else                        wallrow[ i ][ j ] ? std::cout << " " : std::cout << "_";            }        }        std::cout << std::endl;    }}int main( ){    UniformRandom random;    DisjSets ds( N * N );        while ( !ds.connect( 0, N * N - 1 ) )    {        int PosX, PosY = 0;        int element = random.nextInt( 0, N * N - 1 );        GetPos( element, PosX, PosY );               // 0为列 1为行        if( random.nextInt( 2 ) )               // 行 _        {                     if( element < ( N * ( N - 1 ) ) && ! ( ds.connect( element, element + N ) ) )            {                ds.unionSets( element, element + N );                wallrow[ PosX + 1 ][ PosY ] = true;            }           }        else                                    // 列 |        {            if( element % N != ( N - 1 ) && ( ! ds.connect( element, element + 1 ) ) )            {                ds.unionSets( element, element + 1 );                wallcol[ PosX ][ PosY + 1 ] = true;            }        }        }    print( );    return 0;}
      
     

/* * @Author: lsyy * @Date: 2020-02-28 11:42:01 * @LastEditTime: 2020-02-29 16:28:29 * @LastEditors: Please set LastEditors * @Description: 不相交集类 * @FilePath: \DisjSets\Inc\DisjSets.h */#pragma #include 
     
      #include 
      
       class DisjSets{public:    explicit DisjSets( int numElements ) : s ( numElements )    {        for( int & elem : s )            elem = -1;    }    // 任意合并两个不相交集合    void unionSets( int root1, int root2 )    {        s[ root2 ] = root1;    }    // 判断两个根是否在同一集合    bool connect( int root1, int root2 )    {        return find( root1 ) == find( root2 );    }    // 按根深合并    void unionSetsByHight( int root1, int root2 )    {        if( s[ root2 ] < s[ root1 ] )           // 如果 root2 比 root1深            s[ root1 ] = root2;                 // 使 root2 为新的根        else        {            if( s[ root1 ] == s[ root2 ] )      // 如果相同 , 则更新高度                 --s[ root1 ];            s[ root2 ] = root1;                 // 使 root1 为新根        }    }    // 按树大小合并    void unionSetsBySzie( int root1, int root2 )    {        if( s[ root2 ] < s[ root1 ] )           // 如果 root2 比 root1大        {            s[ root2 ] += s[ root1 ];            s[ root1 ] = root2;                 // 使 root2 为新的根        }                   else        {            s[ root1 ] += s[ root2 ];            s[ root2 ] = root1;                 // 使 root1 为新根              }    }    // 寻找 x 所在集合    int find( int x )   const    {        if( s[ x ] < 0 )            return x;        else            return find( s[ x ] );    }    // 寻找 x 所在集合 压缩路径    int PathCompressionfind( int x )       {        if( s[ x ] < 0 )            return x;        else            return s[ x ] = PathCompressionfind( s[ x ] );    }private:    std::vector
       
         s;};
       
      
     

/* * @Author: your name * @Date: 2020-02-15 16:28:55 * @LastEditTime: 2020-02-29 16:50:48 * @LastEditors: Please set LastEditors * @Description: 产生随机数 * @FilePath: \CuckooHash Table\Inc\UniformRandom.h */#ifndef __UNIFORMRANDOM_H#define __UNIFORMRANDOM_H#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;// 获得当前时间static int currentTimeSeconds( ){   auto now = chrono::high_resolution_clock::now( ).time_since_epoch( );           return chrono::duration_cast
          
           ( now ).count( );}class UniformRandom{public: UniformRandom( int seed = currentTimeSeconds( ) ) : generator( seed ) { } // 产生一个伪随机整数 int nextInt( ) { static uniform_int_distribution
           
             distribution; return distribution( generator ); } // Return a pseudorandom int in range [0..high). int nextInt( int high ) { return nextInt( 0, high - 1 ); } // Return a pseudorandom double in the range [0..1). double nextDouble( ) { static uniform_real_distribution
            
              distribution( 0, 1 ); return distribution( generator ); } // Return an int in the closed range [low,high]. int nextInt( int low, int high ) { uniform_int_distribution
             
               distribution( low, high ); return distribution( generator ); } private: mt19937 generator;};#endif