工控網首頁
>

應用設計

>

迷宮問題討論

迷宮問題討論

2013/12/2 10:38:34
遞歸的本質就是使用Stack，但是，遞歸的可讀性無疑更好
一、迷宮(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.");
  • }
投訴建議

提交

查看更多評論
其他資訊

查看更多

2025中歐綠色建筑工業化論壇9月北京啟幕 全球智慧共推建筑產業“雙碳”轉型

喜訊！華強電子網榮獲“2025年中國產業互聯網創新企業”

深入實施“人工智能+”行動 浪潮軟件集團看好人工智能+工業質檢廣闊前景，持續布局線纜行業智能質檢

海爾新增2家卓越級智能工廠，總數品類行業雙第一

深度剖析格力打破磁懸浮壓縮機國外壟斷，底氣來自對自主創新的堅守！