懶得寫新的XD 直接轉錄兩年前寫的教學文 期中考期間 大家應該還有很多科要念吧 偷懶的可以把程式抓下來 把地圖size(陣列大小根判斷的地方) 從25改成15 (我會閉一隻眼改程式的XD) 想試試看但沒頭緒的 可以看說明的部份 然後自己寫看看 期中考加油耶 ps: 我們那屆沒有交 fstream 所以下面的檔案輸入輸出是 fopen 作者 yantchen (球童Yanting) 看板 NTUE-CS99 標題 [課業] 走迷宮程式參考 時間 Wed Oct 31 23:59:29 2007 ─────────────────────────────────────── 抱歉，今天早上臨時寫出來的有一些bug，已經修正 http://stu.ntue.edu.tw/~s9516009/maze.rar 裡面有 6 個檔案 mapmaker.exe 會亂數產生25x25地圖檔 map.txt (起點終點一定是0；其他格亂數產生0或1，不一定有路可以走) map.txt 這個rar附贈的地圖檔 經過測試有路可以走 map_method1.cpp 順時鐘走法迷宮程式檔 (下面會詳細講解這個程式) map_method1.exe 順時鐘走法迷宮執行檔 map_method2.cpp 填數字走法迷宮程式檔 (我自己的解法，另外一種演算法，僅供參考) map_method2.exe 填數字走法迷宮執行檔 ============================================================================= map_method1.cpp 順時鐘走法的演算法： 1.順時針檢查八個方向 有路就走(不管是不是死路) 沒路(牆壁或走過)就轉下一個方向 把走到的那一個 x、y、方向 三個東西放到堆疊 2.如果某一格八個方向都試過沒有路可以走 從堆疊彈出上一步的 x、y、方向 並回到步驟1嘗試下一個方向 3.重複步驟1、2，如果 x、y = 終點 就跳出迴圈 輸出路徑 如果堆疊沒有東西可以彈出了 就是無解 ( 一開始記得把起點放到堆疊裡面 如果起點被彈出來後還是死路 還要再談出堆疊找上一步 就知道是無解 ) 宣告堆疊： step是用陣列作成的堆疊 有1000個空間(其實25x25就夠了) 每個空間可以放3樣資訊 x、y、方向 s是記錄堆疊頂端的變數 push是把x、y、方向放入堆疊的函數 pop是把x、y、方向取出堆疊的函數 show是把堆疊從0到top輸出(show出路徑)的函數 class stack{ int step[1000][3]; int s; public: stack(){ s=0; } void push(int x,int y,int d){ step[s][0]=x; step[s][1]=y; step[s][2]=d; s++; } int pop(int &x,int &y,int &d){ s--; if(s==0) return -1; x=step[s-1][0]; y=step[s-1][1]; d=step[s-1][2]; } void show(){ for(int i=0;i<s;i++) cout<<"第"<<i+1<<"步"<<"("<<step[i][0]<<","<<step[i][1]<<")\n"; } }; 主程式部份 int main(){ 宣告二維陣列map存放地圖 為了避免判斷有沒有超出地圖範圍的麻煩 把陣列設成27x27 並把多的四邊設成牆壁 所以地圖實際存放在陣列的區域是(1,1)~(25,25) int map[27][27]; 讀檔，請參考一下程設投影片 for(int j=0;j<27;j++) for(int i=0;i<27;i++) map[i][j]=1; FILE* f=fopen("map.txt","r"); char buf[25]; for(int j=1;j<=25;j++){ fgets(buf,30,f); for(int i=0;i<25;i++) map[i+1][j]=buf[i]-'0'; } fclose(f); 宣告變數： stk存放路徑堆疊；x,y目前所在位置；d目前嘗試方向；xt,yt下一步預計要往那裡走 stack stk; int x=1,y=1,d=0,xt,yt; 起點設定： 把起點放進堆疊(方便之後判斷是否無解) 地圖上0是路；1是牆壁；2是走過的路；3是死路 stk.push(x,y,d); map[x][y]=2; do{ 方向設定： d=0~7 分別代表一個方向 用switch算出這個方向的下一步 存在xt、yt裡面 switch(d){ case 0: xt=x+1; yt=y-1; break; // 右上 case 1: xt=x+1; yt=y; break; // 右 case 2: xt=x+1; yt=y+1; break; // 右下 case 3: xt=x; yt=y+1; break; // 下 case 4: xt=x-1; yt=y+1; break; // 左下 case 5: xt=x-1; yt=y; break; // 左 case 6: xt=x-1; yt=y-1; break; // 左上 case 7: xt=x; yt=y-1; break; // 上 } 如果可以走 (地圖=0) x,y,d丟入堆疊 地圖設2 走到下一格d歸零 if(map[xt][yt]==0){ x=xt; y=yt; stk.push(x,y,d); map[x][y]=2; d=0; } else { 不能走就轉下一個方向(d++) d++; } 若d加到超過8 想必是遇到了轉了一圈都找不到路的死路 彈出上一步 轉下一個方向 並把死路這格設成3 k用來存pop的傳回值 上面的pop函數設定沒有東西可以彈出得時候傳回-1 判斷k=-1的時候 輸出無解 並結束程式 if(d>=8){ map[x][y]=3; int k=stk.pop(x,y,d); if(k==-1){ cout<<"沒有路可以走喔\n"; system("pause"); return 0; } d++; } 走到終點才跳出迴圈 走完後先用座標顯示走過路徑 再用地圖顯示走過路徑 }while(x!=25||y!=25); stk.show(); for(int j=1;j<=25;j++){ for(int i=1;i<=25;i++){ if(map[i][j]==1) cout<<"█"; else if(map[i][j]==2) cout<<"‧"; else cout<<"　"; } cout<<endl; } system("pause"); } --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 203.68.15.99 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 120.127.36.183 ※ 編輯: yantchen 來自: 120.127.36.183 (11/08 20:29) ※ 編輯: yantchen 來自: 120.127.36.183 (11/08 20:33)