抱歉，今天早上臨時寫出來的有一些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