代码参考<<java软件结构：设计和使用数据结构第二版>>，该书采用java实现，我自己用c写了一遍。
另外提醒一下：个人觉得该书翻译一般，排版较差，代码错误超多^_^，看得郁闷，不推荐。
不过总算是显示了递归的魅力，偶觉得递归实在太漂亮了^_^
/**//********************************************************************
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