递归的本质就是使用Stack，但是，递归的可读性无疑更好 1，迷宫（maze)的表示 使用二维数组。将整个迷宫看作一张地图，这张地图有m*n个小格子个构成。如果，是墙壁则此出对应的坐标为1，反之为0。----这是一个极好的模型！在许多程序中都可以使用。（比如俄罗斯方块) 2，寻路方式 本质上就是从上下左右四个方向寻找0，如果是0则继续，反之推出。 下面这段代码是网上bird网友所作,由于我拿来和堆栈的比较,所以将其列在下面: typedef int STATUS; void InitMaze(int maze[][10])
{
maze[1][1]=1; maze[1][2]=1; maze[1][4]=1;
maze[1][5]=1; maze[1][6]=1; maze[1][8]=1;
maze[2][1]=1; maze[2][2]=1; maze[2][4]=1;
maze[2][5]=1; maze[2][6]=1; maze[2][8]=1;
maze[3][1]=1; maze[3][2]=1; maze[3][3]=1;
maze[3][4]=1; maze[3][7]=1; maze[3][8]=1;
maze[4][1]=1; maze[4][5]=1; maze[4][6]=1;
maze[4][7]=1; maze[4][8]=1;
maze[5][1]=1; maze[5][2]=1; maze[5][3]=1;
maze[5][5]=1; maze[5][6]=1; maze[5][7]=1;
maze[5][8]=1;
maze[6][1]=1; maze[6][3]=1; maze[6][4]=1;
maze[6][5]=1; maze[6][7]=1; maze[6][8]=1;
maze[7][1]=1; maze[7][5]=1; maze[7][8]=1;
maze[8][2]=1; maze[8][3]=1; maze[8][4]=1;
maze[8][5]=1; maze[8][6]=1; maze[8][7]=1;
maze[8][8]=1;
} void PrintMaze(int maze[][10])
{
int i,j;
printf("\n");
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
printf("%d ",maze[i][j]);
}
printf("\n");
}
} void footPrint(int maze[][10], int posX, int posY)
{
maze[posX][posY]=0;
} void printPos(int posX, int posY)
{
printf("(%d, %d) ", posX, posY);
} STATUS Go(int maze[][10], int entranceX, int entranceY, int exitX, int exitY)
{
if(entranceX==exitX && entranceY==exitY)
return 1;
if(maze[entranceX][entranceY]==0)
return 0; footPrint(maze, entranceX, entranceY);
if( Go(maze,entranceX+1,entranceY,exitX,exitY) ){
printPos(entranceX, entranceY);
return 1;
}
if( Go(maze,entranceX,entranceY+1,exitX,exitY) ){
printPos(entranceX, entranceY);
return 1;
}
if( Go(maze,entranceX-1,entranceY,exitX,exitY) ){
printPos(entranceX, entranceY);
return 1;
}
if( Go(maze,entranceX,entranceY-1,exitX,exitY) ){
printPos(entranceX, entranceY);
return 1;
}
return 0;
}
void main()
{
int maze[10][10]={0};
int entranceX=1, entranceY=1;
int exitX=8, exitY=8;
InitMaze(maze);
PrintMaze(maze);
if( !Go(maze,entranceX,entranceY,exitX,exitY) )
printf("Sorry, no solution.");
}
|
本类阅读TOP10