本文以實例形式描述了C++實現迷宮算法。本例中的迷宮是一個矩形區域，它有一個入口和一個出口。在迷宮的內部包含不能穿越的墻或障礙。障礙物沿著行和列放置，它們與迷宮的矩形邊界平行。迷宮的入口在左上角，出口在右下角
本實例迷宮算法的功能主要有：
1.自動生成10*10迷宮圖
2.判斷是否有迷宮出口，并且畫出路線圖
具體實現代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
|
# include <iostream># include <list># include <sys/timeb.h># include <time.h># include <windows.h>using namespace std;bool Makework(int Sam[10][10]);//判斷迷宮是否有出口void main(){struct _timeb timebuffer;_ftime(&timebuffer);unsigned short int tem=timebuffer.millitm;unsigned short int a=0;srand(tem);int quit=1;int Mou[10][10];while(quit==1){for(int i=0;i<10;i++){for(int c=0;c<10;c++){Sleep(3);//延時達到完全隨機數的效果_ftime(&timebuffer);tem=timebuffer.millitm;srand(tem);a=rand()%2;if(rand()%6==1)//再次增加一個隨機，增加空格。{a=0;}Mou[i][c]=a;}cout<<endl;}Mou[0][0]=0;Mou[9][9]=0;for(int e=0;e<10;e++){for(int d=0;d<10;d++){if(0==Mou[e][d]){cout<<"O"<<" ";}else{cout<<Mou[e][d]<<" ";}}cout<<endl;}cout<<endl;if(Makework(Mou)){cout<<"迷宮有出口，迷宮路線圖如下"<<endl;}else{cout<<"迷宮無出口"<<endl;}for(int o=0;o<10;o++){for(int p=0;p<10;p++){if(4==Mou[o][p]){cout<<"*"<<" ";}else if(0==Mou[o][p]){cout<<"O"<<" ";}else{cout<<Mou[o][p]<<" ";}}cout<<endl;}cout<<"選擇1繼續，其它退出"<<endl;cin>>quit;}}bool Makework(int Sam[10][10]){int x=0,y=0;//x橫y縱坐標Sam[y][x]int U=-1,D=1,L=-1,R=1;//上下左右list<int> val;list<int>::iterator vben=val.begin();list<int>::iterator vend=val.end();bool back=false;//是否是在后退，當前后左右都不能移動時。while((9!=x)||(9!=y))//是否到達終點{if((y+D)<10)//下移動{if(Sam[y+D][x]==0){Sam[y][x]=4;if(back)//后退時有新的路線{Sam[y+D][x]=4;//新路線設置為新起點back=false;}val.push_back(x);//坐標添加進容器val.push_back(y);y=y+D;//移動坐標continue;}}if((x+R)<10)//右移動{if(Sam[y][x+R]==0){Sam[y][x]=4;if(back){Sam[y][x+R]=4;back=false;}val.push_back(x);val.push_back(y);x=x+R;continue;}}if(y+U>=0)//上移動{if(Sam[y+U][x]==0){Sam[y][x]=4;if(back){Sam[y+U][x]=4;back=false;}val.push_back(x);val.push_back(y);y=y+U;continue;}}if((x+L>=0))//左移動{if(Sam[y][x+L]==0){Sam[y][x]=4;if(back){Sam[y][x+L]=4;back=false;}val.push_back(x);val.push_back(y);x=x+L;continue;}}if(!val.empty())//前后左右不能移動或者移動后都有阻擋，那么后退。{back=true;list<int>::iterator vend=val.end();--vend;y=*vend;--vend;x=*vend;//修改坐標val.pop_back();val.pop_back();continue;}else{return false;}}return true;} |
