[轉錄][課業] 地圖參考

看板NTUE-CS102作者game0416 (鳳狼)時間13年前 (2010/10/22 20:59)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串1/3 (看更多)

※ [本文轉錄自 NTUE-CS101 看板 #1Azh6txS ] 作者: yantchen (球童Yanting) 看板: NTUE-CS101 標題: [課業] 地圖參考時間: Sun Nov 8 19:55:33 2009 懶得寫新的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

噓

jyc180

11/01 00:48,

11/01 00:48

推

jyc180

11/01 00:51,

11/01 00:51

推

miyuika

11/01 08:05,

11/01 08:05