|
|
|
发新文章 |
|
|
代码参考<<java软件结构:设计和使用数据结构第二版>>,该书采用java实现,我自己用c写了一遍。
另外提醒一下:个人觉得该书翻译一般,排版较差,代码错误超多^_^,看得郁闷,不推荐。
不过总算是显示了递归的魅力,偶觉得递归实在太漂亮了^_^
![maze.bmp](/images/cppblog_com/ngaut/maze.bmp)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//********************************************************************
created: 2005/12/23
created: 23:12:2005 10:47
filename: maze.h
author: Liu Qi
purpose: 递归走迷宫,如果有bug,请联系 ngaut#126.com
*********************************************************************/
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
#ifndef MAZE_H
#define MAZE_H
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>
#include <assert.h>
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
#define COLUMN 3
#define ROW 3
![](/Images/OutliningIndicators/None.gif)
#define TRIED 5
#define PASSED 6
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*===========================================================================
* Function name: CreateMaze
* Parameter: void
* Precondition: void
* Description: 创建一个迷宫,该迷宫用二维数组模拟
* Return value: 指向迷宫的指针
* Author: Liu Qi, // [12/23/2005]
===========================================================================*/
int** CreateMaze( void )
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](/Images/OutliningIndicators/ContractedBlock.gif) {
int i = 0;
int j = 0;
![](/Images/OutliningIndicators/InBlock.gif)
// 设置迷宫为:
// 1 1 1
// 1 0 1
// 0 1 1
// 1:(通道)运行通过,0:(墙)不许通过
int Maze[COLUMN][ROW] =
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {1, 1, 1},
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {1, 0, 1},
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {0, 1, 1}
};
![](/Images/OutliningIndicators/InBlock.gif)
//给二维数组分配空间,有点麻烦哦,我也是今天才明白,
//对比之下STL的vector真好使^_^
int** pMaze = (int **) malloc (COLUMN * sizeof(int*));
assert( NULL != pMaze );
for ( i = 0; i < COLUMN; i++ )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
pMaze[i] = (int *) malloc ( ROW * sizeof(int) );
}
![](/Images/OutliningIndicators/InBlock.gif)
![](/Images/OutliningIndicators/InBlock.gif)
for ( i = 0; i < COLUMN; i++ )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for ( j = 0; j < ROW; j++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
pMaze[i][j] = Maze[i][j];
}
}
![](/Images/OutliningIndicators/InBlock.gif)
return pMaze;
}
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*===========================================================================
* Function name: DestoryMaze
* Parameter: pMaze: 指向迷宫(二维数组)的指针
* Precondition: NULL != pMaze
* Description: 销毁迷宫
* Return value: void
* Author: Liu Qi, // [12/23/2005]
===========================================================================*/
void DestoryMaze( int** pMaze )
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](/Images/OutliningIndicators/ContractedBlock.gif) {
int i;
assert( NULL != pMaze );
![](/Images/OutliningIndicators/InBlock.gif)
for ( i = 0; i < COLUMN; i++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
free( pMaze[i] );
}
![](/Images/OutliningIndicators/InBlock.gif)
free(pMaze);
}
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*===========================================================================
* Function name: DisplayMaze
* Parameter: Maze:二维数组
* Precondition: void
* Description: 显示迷宫(二维数组)
* Return value: void
* Author: Liu Qi, [12/23/2005]
===========================================================================*/
void DisplayMaze(int** pMaze)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](/Images/OutliningIndicators/ContractedBlock.gif) {
int i = 0;
int j = 0;
![](/Images/OutliningIndicators/InBlock.gif)
assert( NULL != pMaze );
![](/Images/OutliningIndicators/InBlock.gif)
for ( ; i < COLUMN; i++ )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for (j = 0; j < ROW; j++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
printf(" %d ", pMaze[i][j]);
}
![](/Images/OutliningIndicators/InBlock.gif)
printf("\n");
}
}
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*===========================================================================
* 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)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](/Images/OutliningIndicators/ContractedBlock.gif) {
bool bRet = false;
![](/Images/OutliningIndicators/InBlock.gif)
assert( NULL != pMaze );
![](/Images/OutliningIndicators/InBlock.gif)
//位置是否越界
if ((col >= 0 && col < COLUMN)
&& (row >= 0 && row < ROW))
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
//当前位置不会是墙吧^_^, 1表示允许通过
if ( pMaze[col][row] == 1 )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
bRet = true;
}
}
![](/Images/OutliningIndicators/InBlock.gif)
return bRet;
}
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*===========================================================================
* 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)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](/Images/OutliningIndicators/ContractedBlock.gif) {
bool bRet = false;
![](/Images/OutliningIndicators/InBlock.gif)
assert( NULL != pMaze );
![](/Images/OutliningIndicators/InBlock.gif)
if (ValidPosition(pMaze, col, row))
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
pMaze[col][row] = TRIED;
![](/Images/OutliningIndicators/InBlock.gif)
printf("tring [%d][%d]\n", col, row);
![](/Images/OutliningIndicators/InBlock.gif)
//递归出口
if ((col == COLUMN - 1 ) && ( col == ROW - 1))
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
bRet = true;
}
else
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
bRet = Traverse(pMaze, col + 1, row); //down
if ( !bRet )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
bRet = Traverse(pMaze, col, row + 1); //right
}
if ( !bRet )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
bRet = Traverse(pMaze, col - 1, row); //up
}
if ( !bRet )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
bRet = Traverse(pMaze, col, row - 1); //left
}
}
![](/Images/OutliningIndicators/InBlock.gif)
if ( !bRet )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
pMaze[col][row] = PASSED;
}
}
![](/Images/OutliningIndicators/InBlock.gif)
return bRet;
}
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
#endif
![](/Images/OutliningIndicators/None.gif)
|