CODE:

//グリッド状の迷路の作成．
//[Args]
//  nVtxX, nVtxY :
//      迷路の規模を，X,Y方向の頂点の個数で指定．どちらも3以上の値を指定する必要がある．
//      （両者の値が3のとき，グリッドサイズは2*2[マス]）
//  Rnd :
//      乱数生成器．
//      （この型に限定する必要は無いのだが，乱数生成器を引数に受けるのをどう書けばいいのかわからん）
//  Is4PointMaze :
//      迷路の形式．
//      trueを指定すると，迷路の出入口が四隅４カ所に作られる．
//      falseを指定すると，迷路の出入口は左上と右下の２か所．
//[Ret]
//  迷路の壁を表すデータ．各要素が１つの「壁」を表し，「壁」は連結する２頂点のindexで表される．
//  頂点indexの範囲は[0, nVtxX*nVtxY-1]
std::vector< std::pair<unsigned int,unsigned int> > CreateGridMaze(
    unsigned int nVtxX, unsigned int nVtxY,
    std::mt19937 &Rnd,
    bool Is4PointMaze
    );

CODE:

//頂点の２次元平面上の座標(X,Y)を取得
//[Args]
//  VtxIndex : 頂点のindex
//  nVtxX : 迷路のX方向の頂点個数．CreateGridMaze()に指定したものと同じ値を指定すること．
//[Ret]
//  (X,Y)座標：
//      一番左上の頂点の座標は(0,0)．
//      そこから右に１個進む毎にXが，下に一個進む毎にYが1ずつ増加する．
inline
std::pair<unsigned int, unsigned int> VtxPos( unsigned int VtxIndex, unsigned int nVtxX )
{   return std::pair<unsigned int,unsigned int>( VtxIndex%nVtxX, VtxIndex/nVtxX );  }

CODE:

//頂点(X,Y)に対応する頂点index
inline
unsigned int VtxIndex( unsigned int X, unsigned int Y, unsigned int nVtxX )
{   return ( Y*nVtxX + X ); }

//非常にシンプルなアルゴリズムによる迷路生成．
//グリッドの外周矩形をNか所の（スタートやゴールみたいな）出入口で切ってできる，N個の外壁グループを考えたとき，
//グリッドの内側の壁を作っていく際に，異なるグループが壁で連結されないようにすれば，各出入口間の経路が失われないよね，っていう方法．
std::vector< std::pair<unsigned int,unsigned int> > CreateGridMaze(
    unsigned int nVtxX, unsigned int nVtxY,
    std::mt19937 &Rnd,
    bool Is4PointMaze
    )
{
    if( nVtxX<3 || nVtxY<3 ){   throw std::invalid_argument( "nVtx must be Greater or Equal 3" );   }

    std::vector< std::pair<unsigned int,unsigned int> > Ret;    //結果用
    std::vector< unsigned int > Labels( nVtxX * nVtxY );    //ラベリング処理用
    std::vector< std::pair<unsigned int, unsigned int> > WallConds; //内壁候補

    //初期状態の準備．
    //・外壁グループ群を構成する壁をRetに追加
    //・全ての頂点にラベリング用のラベルを付与．外壁グループのラベル値には{0,1,2,3}を使用．グリッド内側の頂点には4以上の初期ラベル値を付与．
    //  （MEMO：グリッドの｛左上，右上，左下，右下｝の４頂点のラベル値は以降の処理で参照されないから，ここで特に設定しとかなくてもＯＫ）
    //・WallCondsを，全ての取り得る内壁候補の集合にする
    for( unsigned int x=1; x+1<nVtxX; ++x )
    {
        unsigned int i = VtxIndex( x,0, nVtxX );
        Ret.emplace_back( i, i+1 );
        Labels[i] = 0;

        i = VtxIndex( x,nVtxY-1, nVtxX );
        Ret.emplace_back( i, i-1 );
        Labels[i] = 1;

        WallConds.emplace_back( VtxIndex(x,nVtxY-1,nVtxX), VtxIndex(x,nVtxY-2,nVtxX) );
    }
    for( unsigned int y=1; y+1<nVtxY; ++y )
    {
        unsigned int iu = VtxIndex( 0,y-1, nVtxX );
        unsigned int id = VtxIndex( 0,y, nVtxX );
        Ret.emplace_back( iu, id );
        Labels[id] = ( Is4PointMaze ? 3 : 1 );

        iu = VtxIndex( nVtxX-1,y, nVtxX );
        id = VtxIndex( nVtxX-1,y+1, nVtxX );
        Ret.emplace_back( iu, id );
        Labels[iu] = ( Is4PointMaze ? 2 : 0 );
    }
    if( !Is4PointMaze )
    {
        unsigned int iu = VtxIndex( 0,nVtxY-2, nVtxX );
        unsigned int id = VtxIndex( 0,nVtxY-1, nVtxX );
        Ret.emplace_back( iu, id );

        iu = VtxIndex( nVtxX-1,0, nVtxX );
        id = VtxIndex( nVtxX-1,1, nVtxX );
        Ret.emplace_back( iu, id );
    }
    {
        unsigned int LabelNo = 4;
        for( unsigned int y=1; y+1<nVtxY; ++y )
        {
            for( unsigned int x=1; x+1<nVtxX; ++x )
            {
                unsigned int i = VtxIndex(x,y,nVtxX);
                WallConds.emplace_back( i, i-1 );
                WallConds.emplace_back( i, VtxIndex(x,y-1,nVtxX) );
                Labels[ i ] = LabelNo++;
            }

            unsigned int i = VtxIndex(nVtxX-1,y,nVtxX);
            WallConds.emplace_back( i, i-1 );
        }
    }

    //迷路生成
    std::shuffle( WallConds.begin(), WallConds.end(), Rnd );
    for( auto &WC : WallConds )
    {
        unsigned int i1 = Labels[ WC.first ];
        unsigned int i2 = Labels[ WC.second ];
        //閉所を作らず，且つ，外周グループを連結しないなら，壁として採用
        if( !(   i1==i2  ||  (i1<4 && i2<4)   ) )
        {
            Ret.push_back( WC );

            //ラベル更新．若い方のラベル番号を残す
            unsigned int Before = i1;
            unsigned int After = i2;
            if( Before<After )std::swap( Before,After );
            for( unsigned int &v : Labels ){    if( v==Before ){    v=After;    }   }
        }
    }
    return Ret;
}