代碼參考<<java軟件結構：設計和使用數據結構第二版>>，該書采用java實現，我自己用c寫了一遍。

另外提醒一下：個人覺得該書翻譯一般，排版較差，代碼錯誤超多^_^，看得郁悶，不推薦。

不過總算是顯示了遞歸的魅力，偶覺得遞歸實在太漂亮了^_^



maze.bmp

/********************************************************************
    created:    2005/12/23
    created:    23:12:2005   10:47
    filename:     maze.h
    author:        Liu Qi
    
    purpose:    遞歸走迷宮，如果有bug，請聯系 ngaut#126.com
*********************************************************************/


#ifndef MAZE_H
#define MAZE_H


#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>
#include <assert.h>


#define COLUMN    3
#define ROW        3

#define TRIED    5
#define PASSED  6



/*===========================================================================
* Function name:    CreateMaze
* Parameter:        void
* Precondition:        void
* Description:        創建一個迷宮,該迷宮用二維數組模擬
* Return value:        指向迷宮的指針
* Author:            Liu Qi, //  [12/23/2005]
===========================================================================*/
int** CreateMaze( void )
{
    int i = 0;
    int j = 0;

    //    設置迷宮為：
    //        1 1 1
    //        1 0 1
    //        0 1 1
    //  1:(通道)運行通過，0：(墻)不許通過
    int Maze[COLUMN][ROW] =
    {
        {1, 1, 1},
        {1, 0, 1},
        {0, 1, 1}
    };

    //給二維數組分配空間，有點麻煩哦，我也是今天才明白，
    //對比之下STL的vector真好使^_^
    int** pMaze = (int **) malloc (COLUMN * sizeof(int*));
    assert( NULL != pMaze );
    for ( i = 0; i < COLUMN; i++ )
    {
        pMaze[i] = (int *) malloc ( ROW * sizeof(int) );
    }

    

    for ( i = 0; i < COLUMN; i++ )
    {
        for ( j = 0; j < ROW; j++)
        {
            pMaze[i][j] = Maze[i][j];
        }
    }

    return pMaze;
}


/*===========================================================================
* Function name:    DestoryMaze
* Parameter:        pMaze: 指向迷宮(二維數組)的指針
* Precondition:        NULL != pMaze
* Description:        銷毀迷宮
* Return value:        void
* Author:            Liu Qi, //  [12/23/2005]
===========================================================================*/
void DestoryMaze( int** pMaze )
{
    int i;
    assert( NULL != pMaze ); 

    for ( i = 0; i < COLUMN; i++)
    {
        free( pMaze[i] );
    }

    free(pMaze);
}



/*===========================================================================
* Function name:    DisplayMaze
* Parameter:        Maze:二維數組
* Precondition:        void
* Description:        顯示迷宮(二維數組)
* Return value:        void
* Author:            Liu Qi,  [12/23/2005]
===========================================================================*/
void DisplayMaze(int** pMaze)
{
    int i = 0;
    int j = 0;

    assert( NULL != pMaze ); 

    for ( ; i < COLUMN; i++ )
    {
        for (j = 0; j < ROW; j++)
        {
            printf(" %d ", pMaze[i][j]);
        }

        printf("\n");
    }
}



/*===========================================================================
* Function name:    ValidPosition
* Parameter:        Maze:迷宮(二維數組)， pos：位置
* Precondition:        void
* Description:        檢測指定位置是否合法
* Return value:        true：合法， false：不合法
* Author:            Liu Qi,  [12/23/2005]
===========================================================================*/
bool ValidPosition(int** pMaze, int col, int row)
{
    bool bRet = false;

    assert( NULL != pMaze ); 

    //位置是否越界
    if ((col >= 0 && col < COLUMN) 
        && (row >= 0 && row < ROW))
    {
        //當前位置不會是墻吧^_^, 1表示允許通過
        if ( pMaze[col][row] == 1 )
        {
            bRet = true;
        }
    }

    return bRet;
}




/*===========================================================================
* Function name:    Traverse
* Parameter:        pMaze, col, row
* Precondition:        NULL != pMaze
* Description:        遞歸的遍歷迷宮的每個單元
* Return value:        如果該單元能透過則返回true，否則返回false
* Author:            Liu Qi,  [12/23/2005]
===========================================================================*/
bool Traverse(int **pMaze, int col, int row)
{
    bool bRet = false;

    assert( NULL != pMaze ); 

    if (ValidPosition(pMaze, col, row))
    {
        pMaze[col][row] = TRIED;

        printf("tring[%d][%d]\n", col, row);

        //遞歸出口
        if ((col == COLUMN - 1 ) && ( col == ROW - 1))
        {
            bRet = true;
        }
        else
        {
            bRet = Traverse(pMaze, col + 1, row);    //down
            if ( !bRet )
            {
                bRet = Traverse(pMaze, col, row + 1);    //right
            }
            if ( !bRet )
            {
                bRet = Traverse(pMaze, col - 1, row);    //up
            }
            if ( !bRet )
            {
                bRet = Traverse(pMaze, col, row - 1);    //left
            }
        }

        if ( !bRet )
        {
            pMaze[col][row] = PASSED;
        }
    }

    return bRet;
}


#endif