更新一下以往的课程设计，希望能给相同课程设计的同学提供一个不一样的思路。
问题解决的实现
-
问题描述：
迷宫问题一般使用地方方式求解，当然也可以使用非递归回溯求解。
本次课程设计的目的就是通过非递归的方式求解迷宫问题，并完成过程的详细解释。 -
设计步骤：
-
算法设计
-
主要变量
int: x[4]={0,-1,0,1},y[4]={-1,0,1,0}; //记录方向左上右下
Maxsize 101 ; //定义最大值
a[Maxsize][Maxsize]; //定义迷宫的模型
rows,cols,n,summ=0,minn=10001,want=-1;
//定义行列,障碍点个数,路径个数,最短路径的初始长度和显示的路径
every; //是否每次按键显示整条路径
top=-1; //初始化栈顶
bool :had[Maxsize][Maxsize]; //地图各点是否走过
Struct：
struct
{
int a; //坐标点 是否是可行性路径中的点
int d; //方向
}ans[Maxsize][Maxsize];
typedef struct
{
int x;
int y;
int k;
}point; //定义点的结构体
point path[10005],sp[10005]; //路径和最短路径
- 函数清单
void input(); //输入迷宫的行列和障碍点数
void solve(int xx,int yy); //非递归求解函数（xx,yy）为起点
void pic(point te[],int nu); //打印出路径的图形,te为要打印的点的数组，nu为te中的元素个数
void check(); //检查有无通路及最短路径的输出
void bande(); //输入起点，终点并打印迷宫
void shortpath(); //求出最短路径
- 主函数代码
int main()
{
input(); //输入
solve(bx,by); //求解
check(); //检查
return 0;
}
- 求解函数
void solve(int xx,int yy) //非递归求解函数
{
int k; //定义方向变量
top++;
path[top].x=xx;
path[top].y=yy;
path[top].k=-1; //起点入栈
had[xx][yy]=true; //改变起点可走的状态
while(top>-1) //栈不空循环
{
...
}
- 可视化打印
void pic(point te[],int nu)
{
for(int i=0;i<nu;i++)
{ ans[te[i].x][te[i].y].a=1;
ans[te[i].x][te[i].y].d=te[i].k; //将路径中各点在ans中赋值
}
ans[ex][ey].a=1; //由于终点不在te中，需独立赋值
for(int i=0;i<=rows+1;i++)
{ printf(" ");
for(int j=0;j<=cols+1;j++)
if(a[i][j]&&ans[i][j].a){
if(i==bx&&j==by||i==ex&&j==ey) {
printf("●"); continue; //起点和终点用●打印
}
switch(ans[i][j].d){
case 0: printf("←");break;
case 1: printf("↑");break;
case 2: printf("→");break;
case 3: printf("↓");break;
} //根据ans[i][j].d的值来确定方向
}
else if(!a[i][j]) printf("▇") ; //障碍点用▇打印
else printf(" ");
printf("\n");
}
for(int i=0;i<nu;i++)
{
ans[te[i].x][te[i].y].a=0;
ans[te[i].x][te[i].y].d=-1;
} //一条路径打印完后进行初始化
if(every) system("pause") ; //如果选择按键显示每条路径，暂停
cout<<endl;
}
运行环境说明：
由于调用函数default_random_engine ，所以我们的编译环境选项应调整为 ISO C++ 11 。
Dev-c++中调整如下：打开工具（tools），选择编译选项（Compiler Options）,选择代码生成/优化（setting），点击代码生成（Code Generation）,将语言标准（Language standard）改为ISO C++ 11。
n/20201219180350237.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FhdHJveQ==,size_16,color_FFFFFF,t_70)
正常数据测试
有疑问看这里
如果有疑问，请在评论区留言或私信笔者。
源码及课程设计报告
内容含源码一份，课程设计详细报告一份。
咸鱼扫码即可：
若链接失效，请邮件笔者：lzzy604@126.com