迷宫问题讨论---(递归)

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

递归的本质就是使用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.");

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航