迷宫问题讨论
2013/12/2 10:38:34
递归的本质就是使用Stack，但是，递归的可读性无疑更好
一、迷宫(maze)的表示使用二维数组。将整个迷宫看作一张地图，这张地图有m*n个小格子个构成。如果，是墙壁则此出对应的坐标为0，反之为1。----这是一个极好的模型！在许多程序中都可以使用。（比如俄罗斯方块)
二、寻路方式本质上就是从上下左右四个方向寻找，如果是1则继续，反之退出。
下面这段代码是网上bird网友所作,由于我拿来和堆栈的比较,所以将其列在下面:
一、迷宫(maze)的表示使用二维数组。将整个迷宫看作一张地图，这张地图有m*n个小格子个构成。如果，是墙壁则此出对应的坐标为0，反之为1。----这是一个极好的模型！在许多程序中都可以使用。（比如俄罗斯方块)
二、寻路方式本质上就是从上下左右四个方向寻找，如果是1则继续，反之退出。
下面这段代码是网上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[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.");
- }
投诉建议
提交
查看更多评论
其他资讯
助力企业恢复“战斗状态”：MyMRO我的万物集·固安捷升级开工场景方案
车规MOSFET技术确保功率开关管的可靠性和强电流处理能力
未来十年, 化工企业应如何提高资源效率及减少运营中的碳足迹?
2023年制造业“开门红”，抢滩大湾区市场锁定DMP工博会
2023钢铁展洽会4月全新起航 将在日照触发更多商机