生成迷宫的程序

// 算法简介
// 把N行M列的迷宫认为是N行M-1列的水平墙和N-1行M列的竖直墙组成的图
// N*M的迷宫中一共有(N-1)*(M-1)个通路节点，节点和墙分开存储
// 每个节点都有上下左右四个方向上的邻点
// 从入口节点开始执行深度递归遍例，遇到外墙或出口节点则返回
// 以随机的方式选择邻点，然后再以邻点进行遍例，直到所有节点都被遍例
// 遍例过程中，每通过一个点就将其标记为已过
// 向四个方向中的某个方向移动时就把在那个方向上穿过的墙标记为已过
// 递归过程完成后就得到水平墙和竖直墙的二维数组，1为可过，0为有墙
// 输出过程不具普适性，不做详解。

##CONTINUE##

#include
#include

struct SPOINT
{
    int nX;
    int nY;
};

struct SMAZEINFO
{
    char *pWallHor;
    char *pWallVer;
    int nWidth;
    int nHeight;
    char *pPoints;
};

void _GenMaze( SMAZEINFO *pMazeInfo, SPOINT *pCurPos )
{    // 此函数为递归函数，执行图的深度遍例
    const float c_f2PI = 3.1415927f / 2.0f;
    const int c_nNeiCnt = 4;
    SPOINT aNeighbors[c_nNeiCnt] = {    // 邻点数组，初始值为偏移量
        { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
        int nPtCntX = pMazeInfo->nWidth - 1;
        int nPtCntY = pMazeInfo->nHeight - 1;
        int nX = pCurPos->nX;
        int nY = pCurPos->nY;
        // 标记当前点已遍例
        pMazeInfo->pPoints[ nY * nPtCntX + nX ] = true;
        if ( nX != nPtCntX - 1 || nY != nPtCntY - 1 )
        {    // 最后一个点不遍例邻点
            for ( int i = 0; i < c_nNeiCnt; ++ i )
            {    // 循环生成邻点
                aNeighbors[i].nX += pCurPos->nX;
                aNeighbors[i].nY += pCurPos->nY;
            }
            for ( int i = 0; i < c_nNeiCnt; ++ i )
            {    // 乱序邻点，标准shuffle算法
                int nRandId = rand() % c_nNeiCnt;
                if ( nRandId != i )
                {
                    SPOINT ptTemp = aNeighbors[i];
                    aNeighbors[i] = aNeighbors[nRandId];
                    aNeighbors[nRandId] = ptTemp;
                }
            }
            for ( int i = 0; i < 4; i++ )
            {    // 遍例相邻点
                nX = aNeighbors[i].nX;
                nY = aNeighbors[i].nY;
                if ( nX >= 0 && nY >= 0 && nX < nPtCntX && nY < nPtCntY &&
                    !pMazeInfo->pPoints[ nY * nPtCntX + nX ] )
                {    //去除超过边界的点和已遍例的点
                    if ( nX != pCurPos->nX )
                    {    // 横向通过，打通竖直墙
                        int nOffset = nX > pCurPos->nX;
                        pMazeInfo->pWallVer[ pCurPos->nY * pMazeInfo->nWidth +
                            pCurPos->nX + nOffset ] = 1;
                    }
                    else
                    {    // 纵向通过，打通水平墙
                        int nOffset = nY > pCurPos->nY;
                        pMazeInfo->pWallHor[ ( pCurPos->nY + nOffset ) *
                            nPtCntX + pCurPos->nX ] = 1;
                    }
                    _GenMaze( pMazeInfo, &aNeighbors[i] );
                }
            }
        }
}

void GenMaze( char *pWallHor, char *pWallVer, int nWidth, int nHeight )
{
    int nPtCntX = nWidth - 1;
    int nPtCntY = nHeight - 1;
    char *pPoints = new char[ nPtCntX * nPtCntY ];
    memset( pPoints, 0, nPtCntX * nPtCntY );
    memset( pWallHor, 0, ( nWidth - 1 ) * nHeight );
    memset( pWallVer, 0, nWidth * ( nHeight - 1 ) );
    pWallHor[0] = 1;    //    打通入口
    SMAZEINFO MazeInfo;
    MazeInfo.pWallVer = pWallVer;
    MazeInfo.pWallHor = pWallHor;
    MazeInfo.pPoints = pPoints;
    MazeInfo.nWidth = nWidth;
    MazeInfo.nHeight = nHeight;
    SPOINT ptFirst = { 0 };
    _GenMaze( &MazeInfo, &ptFirst );
    pWallHor[ ( nWidth - 1 ) * nHeight - 1 ] = 1; // 打通出口
}


void main()
{
    srand( (unsigned int)time(0) );
    const int nWidth = 15;   // 在这里输入迷宫的宽度
    const int nHeight = 15;  // 在这里输入迷宫的高度
    char aWallHor[ ( nWidth - 1 ) * nHeight ];
    char aWallVer[ nWidth * ( nHeight - 1 ) ];
    GenMaze( aWallHor, aWallVer, nWidth, nHeight );
    for ( int i = 0; i < nHeight - 1; ++i )
    {
        printf( "@@" );
        for ( int j = 0; j < nWidth - 1; ++j )
        {
            printf( aWallHor[ i * ( nWidth - 1 ) + j ] ? "  @@" : "@@@@" );
        }
        printf( "\n@@" );
        for ( int j = 1; j < nWidth; ++j )
        {
            printf( aWallVer[ i * nWidth + j ] ? "    " : "  @@" );
        }
        printf( "\n" );
    }
    printf( "@@" );
    for ( int j = 0; j < nWidth - 1; ++j )
    {
        printf( aWallHor[ ( nHeight - 1 ) * ( nWidth - 1 ) + j ] ?
            "  @@" : "@@@@" );
    }
    getch();
    return;
}