CC++广度优先搜索模拟迷宫求解问题

问题描述

用一个字符类型的二维数组表示迷宫,数组中的每个元素表示一个小方格,‘0’代表通道,‘1’代表阻塞物。设计一个模拟小动物走迷宫的程序,为小动物寻找一条从迷宫入口到迷宫出口的通路。

功能及界面要求:

  • 用户可以设置迷宫的行数或列数。
  • 随机产生迷宫的状态。
  • 用户设置小动物的入口下标和出口下标
  • 根据迷宫状态和入、出口位置直观显示出从入口到出口的通路或“不存在通路”的信息。

代码

重要的点已经注释了, 就不在多说了, 有什么问题可以下方评论区进行讨论.

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
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
using namespace std;
long map[10000][10000];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; //可走的四个方向
struct node
{
int x,y;
};
struct node queue[5000], record[5000][5000];//queue记录可走的点,广搜;
//record记录改点的前驱
bool bfs(int column, int row, int startx, int starty, int endpx, int endpy)
{
int head, tail, i;
struct node cur, next;//cur为当前位置,next为下一个位置
head = tail = 0;
//head = startx - 1;
//tail = starty - 1;
cur.x = queue[tail].x;
cur.y = queue[tail].y;
tail++;
while(head < tail)
{
cur = queue[head++];
for(i = 0; i < 4; i++)
{
next.x = cur.x+dir[i][0];
next.y = cur.y+dir[i][1];
if(next.x>=0 && next.y>=0 && next.x<column && next.y<row && map[next.x][next.y] == 0)
{
record[next.x][next.y].x = cur.x;
record[next.x][next.y].y = cur.y;//记录next的前驱,即next的坐标(因为next记录的是第一个到达该地点的前驱,随后被标记走过,故不用担心被后来的前驱坐标所覆盖)
if(next.x == endpx && next.y == endpy)
return true;
else
{
map[next.x][next.y] = 1;//标记走过
queue[tail++] = next;
}
}
}
}
return false;
}
int main()
{
int i, j;
int k, m, n, flag = 0;
int save, column, row, startx,starty,endpx, endpy;
struct node cur;
while(!flag)
{
cout<<"请输入行和列"<<endl;
cout<<"行为: ";
cin>>column;
cout<<"列为: ";
cin>>row;
cout<<"起始位置: ";
scanf("%d%d", &startx, &starty);
cout<<"终点: ";
scanf("%d%d", &endpx, &endpy);
srand(time(NULL));
for(i = 0; i < column; i++)
{
for(j = 0; j < row; j++)
{
save = (int)(rand()%10 > 2 ? 0:1);
map[i][j] = save;
printf("%2d", save);
}
cout<<endl;
}
if(map[startx][starty] == 1)
{
printf("无路径!!!\n");
flag = 0;
}
else
{
cur.x = startx;
cur.y = starty;
map[startx][starty] = 1;
queue[0] = cur;//可走的点为当前结点
if(!bfs(column, row, startx, starty, endpx, endpy)) {printf("无路径!!!\n"); flag = 0;}
else
{
k = 0;
queue[k].x = endpx;
queue[k++].y = endpy;
i = endpx;
j = endpy;
while(i!=startx || j!=starty)//根据record的记录,从后往前回溯其路径,并存在queue中
{
m = i;
n = j;
i = record[m][n].x;
j = record[m][n].y;
queue[k].x = i;
queue[k++].y = j;
}
for(i = k-1; i >= 0; i--)//输出路径
printf("(%d, %d)\n",queue[i].x,queue[i].y);
flag = 1;
return 0;
}
}
}
}

越来越多的平台(微信公众平台,新浪微博,简书,百度打赏等)支持打赏功能,付费阅读时代越来越近,特此增加了打赏功能,支持微信打赏和支付宝打赏。坚持原创技术分享,您的支持将鼓励我继续创作!