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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
#include <iostream>
#include <string>
//#include <queue>
#include "QueueBottom.h"
#include <fstream>
using namespace std;
#include <iomanip>
#include <Windows.h>
#include <time.h>
clock_t start,finish;
//改变字体颜色
void setColour(int x){
HANDLE h = GetStdHandle (-11);
SetConsoleTextAttribute(h,x);
}
//四个方向
int maze[100][100], past_footprint[100][100];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
//存储最终的路径的数组
int final_array[100][100];
int printmaze[100][100];
int second_printmaze[100][100];
int whole_step;
struct point
{
int x;
int y;
int step;
};
queue<point> now_footprint;
queue<point> second_footprint;
void printMaze(int& endx, int& endy, int& startx, int& starty, int& length, int& width, string mapname)
{
ifstream first(mapname, ios::in);
if (!first.is_open())
{
cout << "Error: opening file fail" << endl;
system("pause");
exit(1);
}
while (!first.eof())
{
first >> length >> width ;
for (int i = 0; i < length; i++)
for (int j = 0; j < width; j++)
first >> maze[i][j];
first
>> endx >> endy >> startx >> starty;
}
// //之后可以改成从txt文件中读取
// //输入竖向长度x
// cout << "Please Enter the length of maze:" << endl;
// cin >> length ;
// //输入横向长度y
// cout << "Please Enter the width of maze:" << endl;
// cin >> width ;
// //输入迷宫的形状，1为通路，2为障碍，没有边框
// cout << "Enter the whole maze:" << endl;
// for (int i = 0; i < length; i++)
//
for (int j = 0; j < width; j++)
//
cin >> maze[i][j];
// //输入迷宫的起点	
// cout << "Please Enter the start of maze" << endl;
// cin >> endx >> endy ;
// //输入迷宫的终点
// cout << "Please Enter the end of maze" << endl;
// cin >> startx >> starty ;
}
void findRoad(int startx, int starty, int endx, int endy, int length, int width)
{
//BFS
//队首元素初始化
point start;
start.x = startx;
start.y = starty;
start.step = 0;
int tag = 1;
now_footprint.push(start);
past_footprint[startx][starty] = 1;
cout << "The Map before function :" << endl;
cout << " 1 for road; 2 for wall " << endl << endl;
for(int m = 0; m < length;m++)
{
for(int n = 0; n < width;n++)
{
cout << maze[m][n] << "
";
}
cout << endl;
}
cout << endl;
//终点标志
int flag = 0;
while(!now_footprint.empty())
{
//将该队列的首元素的 x y 分别赋予临时的 x y
int x = now_footprint.front().x;
int y = now_footprint.front().y;
//判断该队列的元素是否与终点匹配
printmaze[x][y] = now_footprint.front().step;
whole_step = now_footprint.front().step;
if(x==endx && y==endy)
{
flag = 1;
cout << "The shortest road from start to end is : "<< now_footprint.front().step << endl ;
cout << "It start at "<< startx << " " << starty << endl;
cout << "It end at " << endx << " " << endy << endl;
cout << "It start with number 0 and end with number " <<now_footprint.front().step << endl;
break;
}
//探路拓展循环
for(int k = 0; k <= 3; k++)
{
//创建临时变量tx ty
int tx,ty;
//按下 右 上 左的顺序去探路
tx = x + dx[k];
ty = y + dy[k];
if(maze[tx][ty] == 1 && past_footprint[tx][ty] == 0)
{
//若地点为未探索的点，则创建一个临时变量temp，将它入队
point temp;
temp.x = tx;
temp.y = ty;
temp.step = now_footprint.front().step + 1;
now_footprint.push(temp);
//并设置为已访问
past_footprint[tx][ty] = 1;
}
}
//将已经拓展完的首节点出队
now_footprint.pop();
}
//若找不到终点，则返回no answer
if (flag == 0)
cout << "No answer" << endl;
//将出口置为特殊符号
//因为我的vscode会乱码所以只能暂时改成颜色标识符 :D
setColour(12);
cout << setw(4) <<"#";
setColour(15);
cout << endl;
for(int m = 0; m < length;m++)
{
for(int n = 0; n < width;n++)
{
//需要包含头文件iomanip
//让每一个输出的宽度都为4
cout<<setw(4)<<printmaze[m][n];
//下面这行代码可以使得输出的字符左对齐
//<<setiosflags(ios::left)
//cout << printmaze[m][n] << "
";
}
cout << endl;
}
cout << endl;
}
void again_findRoad(int startx, int starty, int endx, int endy, int length, int width)
{
for(int i = 0; i <= length; i++)
for(int j = 0; j <= width; j++)
past_footprint[i][j] = 0;
point start;
start.x = endx;
start.y = endy;
start.step = 0;
int printmaze[100][100];
int tag = 1;
second_footprint.push(start);
past_footprint[endx][endy] = 1;
int flag = 0;
while(!second_footprint.empty())
{
int x = second_footprint.front().x;
int y = second_footprint.front().y;
second_printmaze[x][y] = second_footprint.front().step;
if(x==startx && y==starty)
{
flag = 1;
cout << "The shortest road from start to end is : "<< second_footprint.front().step << endl ;
cout << "It start at "<< endx << " " << endy << endl;
cout << "It end at " << startx << " " << starty << endl;
cout << "It start with number 0 and end with number " <<second_footprint.front().step << endl;
break;
}
for(int k = 0; k <= 3; k++)
{
int tx,ty;
tx = x + dx[k];
ty = y + dy[k];
if(maze[tx][ty] == 1 && past_footprint[tx][ty] == 0)
{
point temp;
temp.x = tx;
temp.y = ty;
temp.step = second_footprint.front().step + 1;
second_footprint.push(temp);
past_footprint[tx][ty] = 1;
}
}
second_footprint.pop();
}
cout << endl;
for(int m = 0; m < length;m++)
{
for(int n = 0; n < width;n++)
{
cout<<setw(4)<<second_printmaze[m][n];
}
cout << endl;
}
cout << endl;
}
void print_final_road(int length, int width, int step)
{
//step = whole_step;
for(int m = 0; m < length;m++ )
for(int n = 0; n < width;n++ )
{
if(printmaze[m][n] + second_printmaze[m][n] == step)
{
final_array[m][n] = 1;
}
}
for(int m = 0; m < length; m++ )
{
for(int n = 0; n < width; n++ )
{
// final_array[m][n] = printmaze[m][n] + second_printmaze[m][n] ;
cout << setw(4) << final_array[m][n];
}
cout << endl;
}
}
int main()
{
//定义变量
string mapname;
int endx, endy, startx, starty, width, length, afterendx, afterendy, aftertag;
//选择地图的号码
int tag;
while(1)
{
cout << "Please Choose the Map of CityPark : "<< endl;
cout << "Press 0 to exit"
<< endl;
cout << "-1:ClearScreen
0:Exit"
<< endl;
cout << "1:Shenzhen
2:GuangZhou " << endl;
cout << "3:BeiJing
4:ShangHai	" << endl;
cin >> tag;
cout << endl;
switch (tag)
{
case 1:
{
/*要计算时间的代码*/
mapname = "ShenZhenMap.txt";
printMaze(endx, endy, startx, starty, length, width, mapname);
start=clock();
findRoad(endx, endy, startx, starty, length, width);
again_findRoad(endx, endy, startx, starty, length, width);
finish=clock();
print_final_road(length,width,whole_step);
double totaltime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<"ntime cost: "<<totaltime<<"seconds!"<<endl;
break;
}
case 2:
{
mapname = "GuangZhouMap.txt";
printMaze(endx, endy, startx, starty, length, width, mapname);
findRoad(endx, endy, startx, starty, length, width);
again_findRoad(endx, endy, startx, starty, length, width);
print_final_road(length,width,whole_step);
break;
}
case 3:
{
mapname = "BeiJingMap.txt";
printMaze(endx, endy, startx, starty, length, width, mapname);
findRoad(endx, endy, startx, starty, length, width);
again_findRoad(endx, endy, startx, starty, length, width);
print_final_road(length,width,whole_step);
break;
}
case 4:
{
mapname = "ShangHaiMap.txt";
printMaze(endx, endy, startx, starty, length, width, mapname);
findRoad(endx, endy, startx, starty, length, width);
again_findRoad(endx, endy, startx, starty, length, width);
print_final_road(length,width,whole_step);
break;
}
case 0:
{
cout << "Exit" << endl;
system("pause");
exit(1);
}
case -1:
{
system("cls");
break;
}
default:
break;
}
}
// printMaze(endx, endy, startx, starty, length, width);
// findRoad(endx,endy,startx,starty,length,width);
system("pause");
return 0;
}

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
#include<iostream>
using namespace std;
#include <time.h>
//地图数组，用来存储迷宫
int map[50][50];
bool visit[50][50];
int ans[250];
int res[250];
int tmp[250];
int k,Min,len;
//以下为增加内容
#include <fstream>
int length, width, startx, starty, endx, endy;
string mapname;
//判断方向的数组
int X[4]={-1,1,0,0};
int Y[4]={0,0,-1,1};
clock_t start,finish;
void readTxt(string mapname)
{
ifstream first(mapname, ios::in);
if (!first.is_open())
{
cout << "Error: opening file fail" << endl;
system("pause");
exit(1);
}
while (!first.eof())
{
first >> length >> width ;
for (int i = 0; i < length; i++)
for (int j = 0; j < width; j++)
{
first >> map[i][j];
visit[i][j]=false;
}
first >> startx >> starty >> endx >> endy ;
}
}
void dfs(int startx,int starty,int step,int k){
int x = startx;
int y = starty;
//判断当前格子的xy是否在0~5范围内
//若否则直接返回
//这个判断条件可以防止边界越界的情况 如x = -1, y = 0
if(x>=length||x<0||y>=width||y<0)return;
//当该点走过，则退出该层递归
if(visit[x][y])return;
//当该点为墙，则退出该层递归
if(map[x][y]==1)return;
//当xy为终点坐标时执行
if(x==endx&&y==endy){
if(step<Min){
ans[k]=x*10+y;
//将步数用Min存储，用于下次第二次通路的长度比较
Min=step;
for(int i=0;i<=k;i++){
res[i]=ans[i];
}
//全局变量，用于打印路径
len=k;
}
return;
}
//将走过的地方置为true
visit[x][y]=true;
ans[k]=x*10+y;
//使用递归来判断某一方向是否能走
for(int i=0;i<4;i++){
dfs(x+X[i],y+Y[i],step+1,k+1);
}
//注意此语句非常关键，既然找最短，则就需要不断
回溯，因此需要将原来访问过的标记清除
visit[x][y]=false;
//回溯的时候置空，还原
//当回溯到有分叉路的地方的时候，会走for循环中没有走过的路，同时不会影响这次的寻路
//添加该语句后就能从两条路线中选出相对较短的一条
}
int main(){
//cin >> length >> width >>startx >> starty >> endy >> endx;
//设定一个极大的值，使得第一次必然进入if循环
Min = 9999;
//存入输入的地图
// for(int i=0;i<length;i++){
//
for(int j=0;j<width;j++){
//
cin>>map[i][j];
//
visit[i][j]=false;
//
}
// }
readTxt("BeiJingMap.txt");
//dfs执行
start=clock();
dfs(startx,starty,1,0);
finish=clock();
//打印地图
for (int i = 0; i < length; i++)
{
for (int j = 0; j < width; j++)
{
cout << map[i][j] << " ";
}
cout << endl;
}
cout << endl;
//输出res中存储的坐标
for(int i=0;i<=len;i++){
cout<<"("<<res[i]%10<<", "<<res[i]/10<<")"<< "->" ;
if(i % 5 == 0)
cout << endl;
}
double totaltime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<"ntime cost: "<<totaltime<<"seconds!"<<endl;
system("pause");
return 0;
}
/*
10 10
0 1 0 0 0 0 0 0 0 0
0 1 0 1 1 1 0 1 1 0
0 1 0 1 0 1 0 1 0 0
0 1 0 1 0 1 0 1 0 0
0 1 0 0 0 1 0 1 1 1
0 1 1 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 1 0 1 1 1 0 1 1 0
0 1 0 0 0 1 0 0 1 0
0 1 1 1 1 1 0 1 1 0
0 0
9 9
*/

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

#include <iostream>
using namespace std;
//模板结构体，可以适用于任何类型
template <typename T>
struct node{
T data;
node *next;
//构造函数初始化next和data值
node(){
next=NULL;
}
//new创建node结点的时候可以选择是否有初值
node(T x){
data=x;
next=NULL;
}
};
//模板类，可以适用于任何类型
template <typename T>
class queue{
private :
node<T> *head,*tail;
int len=0;
public :
queue(){
node<T> *temp=new node<T>();
head=tail=temp;
len=0;
}
//Q.size(); 返回该队列的长度
int size(){
return len;
}
//Q.empty(); 返回该队列是否为空
bool empty(){
if(len==0) return true;
return false;
}
//头元素
T& front(){
if(len) return head->next->data;
}
//尾元素
T& back(){
if(len) return tail->data;
}
void pop(){
if(len) {
head=head->next;
len--;
}
}
void push(const T a){
node<T> *temp=new node<T>(a);
tail->next=temp;
//？
tail = temp;
temp = NULL;
len++;
}
};
// int main(){
//
// Queue<string> Q;
//
// Q.push(string("abc1"));
//
// Q.push(string("abc2"));
//
// Q.push(string("abc3"));
//
// cout<<Q.front()<<endl;
//
// cout<<Q.back()<<endl;
//
// Q.pop();
//
// cout<<Q.front()<<endl;
//
// cout<<Q.back()<<endl;
//
system("pause");
//
return 0;
// }