好家伙，写大作业,本篇为代码的思路讲解
1.大作业要求
走迷宫程序
问题描述：
以一个 m * n 的长方阵表示迷宫， 0和1分别表示迷宫的通路和障碍。 设计一个程序， 对任意设定的迷宫， 求出一条从入口到出口的通路， 或得出没有通路的结论。
基本要求：
（1） 实现一个以链表做存储的栈类型， 然后编写一个求解迷宫的非递归程序。 求的通路以三元组（i， j， d） 的形式输出， 其中：（i， j） 指示迷宫中的一个坐标， d 表示走到下一坐标的方向。 如： 对于下列数据的迷宫， 输出一条通路：
（1， 1， 1），（1， 2， 2），
（2， 2， 2），（3， 2， 3），（3， 1， 2） ……。
（2） 编写递归形式的算法， 求得迷宫中所有可能的道路；
扩展功能要求：
以方阵形式输出迷宫及其到道路
测试数据： 迷宫的测试数据如下： 左上角（1， 1） 为入口， 右下角（8， 9） 为出口。
作业要求
1、 选题：从4个题目中任选其一，独立完成。程序至少采用所学过的一种数据结构（链表、栈、队列、树等）实现。学生可以根据自己的需求分析适当地调整程序的合理性，使得程序能够更加贴近实际。每个题目选题人员不得超过15人，向学委报名选题情况，先报先得，每个题目满15人后必须另选其他题目。
2、 程序代码要求：程序要求能够正常运行，基本功能必须全部实现。完成可选做的扩展功能将得到较高的分数。容错性强和功能细节考虑更完全也将得到较高的分数。
3、 开发语言:软件工程和数据科学与大数据技术专业用Java语言，计算机科学与技术专业用C或C++语言。
2.分析
来概括一下
这是个迷宫程序，手动输入迷宫，找出所有解，输出所有解
数据结构要用栈
解法：
我们用一个二维度数组保存这个"迷宫"
1.随后,我们确定起点和终点,
2.先站在起点上,将起点入栈
3.我们开始寻路,按照东南西北(即右下左上)的方向顺序寻找下一坐标
3.1.如果该方向上有路,将下一坐标入栈,"走到"这个坐标上
3.2.如果下一坐标上是墙,则返回
3.3.如果下一个点是出口,则打印线路
3.单路径版本
大概是这样了
代码如下:
单路径版本
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXN 20 struct mark // 定义迷宫内点的坐标类型 { int x; int y; }; struct Element // 链栈元素结点 { int x, y; // x行,y列 int d; // d下一步的方向 }; typedef struct LStack // 链栈 { Element elem; struct LStack *next; // 指针变量 }; typedef LStack *PLStack; /*……………………………栈函数……………………………*/ int InitStack(PLStack &S) // 构造空栈 { S = NULL; return 1; } int StackEmpty(PLStack S) // 判断栈是否为空 { if (S == NULL) return 1; else return 0; } int Push(PLStack &S, Element e) // 压入新数据元素 { PLStack p; p = (PLStack)malloc(sizeof(LStack)); p->elem = e; p->next = S; S = p; return 1; } int Pop(PLStack &S, Element &e) // 栈顶元素出栈 { PLStack p; if (!StackEmpty(S)) { e = S->elem; p = S; S = S->next; free(p); return 1; } else return 0; } /*……………………求迷宫路径函数……………………………*/ void MazePath(struct mark start, struct mark end, int maze[MAXN][MAXN], int diradd[4][2]) { int i, j, d; int a, b; Element elem, e; PLStack S1, S2; InitStack(S1); InitStack(S2); maze[start.x][start.y] = 2; // 入口点作上标记 elem.x = start.x; elem.y = start.y; elem.d = -1; // 开始为-1 Push(S1, elem); while (!StackEmpty(S1)) // 栈不为空 有路径可走 { Pop(S1, elem); i = elem.x; j = elem.y; d = elem.d + 1; // 下一个方向 while (d < 4) // 试探东南西北各个方向 { a = i + diradd[d][0]; b = j + diradd[d][1]; if (a == end.x && b == end.y && maze[a][b] == 0) // 如果到了出口 { elem.x = a; elem.y = b; elem.d = 886; // 方向输出为-1 判断是否到了出口 Push(S1, elem); printf("\n0=东 1=南 2=西 3=北 886为则走出迷宫\n\n通路为:(行坐标,列坐标,方向)\n"); while (S1) // 逆置序列 并输出迷宫路径序列 { Pop(S1, e); Push(S2, e); } while (S2) { Pop(S2, e); printf("-->(%d,%d,%d)", e.x, e.y, e.d); } return; // 跳出两层循环，本来用break,但发现出错，exit又会结束程序，选用return } if (maze[a][b] == 0) // 找到可以前进的非出口的点 { maze[a][b] = 2; // 标记走过此点 elem.x = i; elem.y = j; elem.d = d; Push(S1, elem); // 当前位置入栈 i = a; // 下一点转化为当前点 j = b; d = -1; } d++; } } printf("没有找到可以走出此迷宫的路径\n"); } /*……………………………建立迷宫……………………………*/ void initmaze(int maze[MAXN][MAXN]) { int i, j; int m, n; // 迷宫行,列 printf("请输入迷宫的行数 m="); // 输入迷宫 scanf("%d", &m); printf("请输入迷宫的列数 n="); scanf("%d", &n); printf("\n请输入迷宫的各行各列:\n用空格隔开,0代表路,1代表墙\n", m, n); for (i = 1; i <= m; i++) { for (j = 1; j <= n; j++) scanf("%d", &maze[i][j]); } printf("你建立的迷宫为\n"); for (i = 0; i <= m + 1; i++) // 加一圈围墙 { maze[i][0] = 1; maze[i][n + 1] = 1; } for (j = 1; j <= n; j++) { maze[0][j] = 1; maze[m + 1][j] = 1; } for (i = 0; i <= m + 1; i++) // 输出迷宫 { for (j = 0; j <= n + 1; j++) printf("%d ", maze[i][j]); printf("\n"); } } int main() { int sto[MAXN][MAXN]; struct mark start, end; // start,end入口和出口的坐标 int add[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 行增量和列增量 方向依次为东西南北 initmaze(sto); // 建立迷宫 printf("输入入口的横坐标,纵坐标[空格隔开]\n"); scanf("%d %d", &start.x, &start.y); printf("输入出口的横坐标,纵坐标[空格隔开]\n"); scanf("%d %d", &end.x, &end.y); MazePath(start, end, sto, add); // find path printf("\n"); }
效果如下:
看上去没什么问题了,
但是,这种方法无法实现多条路径的打印
所以还是要使用搜索算法
下面,我们使用深度优先搜索来解决这个问题
此处我们使用递归的思想
4.最终版本
解法由:
用一个二维度数组保存这个"迷宫"
1.随后,我们确定起点和终点,
2.先站在起点上,将起点入栈
3.我们开始寻路,按照东南西北(即右下左上)的方向顺序寻找下一坐标
3.1.如果该方向上有路,将下一坐标入栈,"走到"这个坐标上
3.2.如果下一坐标是墙,则进行下一次循环
3.3.如果下一个点是出口,则打印线路
改为
用一个二维度数组保存这个"迷宫"
1.随后,我们确定起点和终点,
2.先站在起点上,将起点入栈
3.寻路方法(){
"走到下一点上"(第一次调用时不做这步)
3.1.开始寻路,按照东南西北(即右下左上)的方向顺序确定下一坐标,
| 3.1.1如果该方向上有路,下一坐标入栈,并标记为2(标记为走过)
| | 3.1.1.1如果下一个点是出口,则打印线路,将下一坐标标记为0,栈顶出栈
| | 3.1.1.2.调用寻路方法
| 3.1.2.开始下一次循环,回到3.1
3.2.出栈,当前点赋值为0
}
核心算法部分实现:
//-----------遍历迷宫寻找路径(dfs)------------ void mazePath(int x,int y,int endx,int endy,int n,int m,Stack s){ int newx,newy,i; Node t; for(i=0;i<4;i++){ newx=x+direction[i][0]; newy=y+direction[i][1]; if(newx>=0&&newx<n&&newy>=0&&newy<m&&maze[newx][newy]==0){ //下一个路能走 push(newx,newy,s); maze[newx][newy]=2; if(newx==endx&&newy==endy){//走到出口 flag++; printPath(s,n,m); maze[newx][newy]=0; pop(s); } else{ mazePath(newx,newy,endx,endy,n,m,s); //开始递归 } } } maze[x][y]=0; //遍历完四个方向之后回溯前将自己赋为空 pop(s); }
完整代码:
所有路径版本:
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXN 20 /* *建立一个二维数组存迷宫 *要是四个方向能有位置则压入栈，要是下一步没有则弹出栈回溯 *直到找到终点为止 */ int direction[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; //定义一个数组存四个方向操作数 int MIN=100;//用于记录最小路径 int maze[MAXN][MAXN]; int flag=0; //栈中存位置以及遍历时所走的方向，打印时可以显示出来 //栈的元素节点 typedef struct Node{ int x; int y; struct Node *next; }Node; typedef Node* Stack; //定义数据结构栈 Stack /*……………………………栈函数……………………………*/ //-----------创建一个空栈-------------- Stack creakEmptyStack(){ Stack p; p=(Stack)malloc(sizeof(Node)); //申请一个空间 if(p){ p->next=NULL; return p; } } //------------将元素压入栈---------------- void push(int x,int y,Stack s){ Stack p; p=(Stack)malloc(sizeof(Node)); if(p){ //如果申请空间成功则用头插法将元素压入 p->x=x; p->y=y; if(!s->next) p->next=NULL; //如果此时栈里还没有任何元素，则p此时为第一个结点 else p->next=s->next; //否则将p插入头结点之后 s->next=p; } else{ printf("No space!\n"); } } //-------------检测栈是否为空-------------- int isEmpty(Stack s){ //为空则返回1，不为空返回0 if(s->next==NULL) return 1; else return 0; } //--------------将元素弹出栈---------------- void pop(Stack s){ Stack p; p=s->next; if(p->next){ s->next=p->next; free(p); } else return; } //------------取栈顶元素------------------ Node top(Stack s){ Node t; //判断是否为空，若不为空则返回 t=*(s->next); return t; } void mazePath(int x,int y,int endx,int endy,int n,int m,Stack s); void printPath(Stack s,int n,int m); int main() { int n,m,i,j,xa,xb,ya,yb,ox; //--------------建立迷宫-------------- printf("请输入迷宫大小：（长、宽）\n"); scanf("%d%d",&n,&m); if(n<=20&&m<=20){ printf("请选择构建迷宫的方式：\n0.随机生成迷宫\n1.手动输入迷宫\n"); //实际上不是0就可以手动输入 scanf("%d",&ox); for(i=0;i<n;i++){ for(j=0;j<m;j++){ if(!ox)maze[i][j]=rand()%2; //这里为伪随机数 else scanf("%d",&maze[i][j]); } } printf("\n"); //----------输出构建迷宫------------- printf("生成的迷宫如下：\n"); for(i=0;i<n;i++){ for(j=0;j<m;j++){ printf("%d ",maze[i][j]); } printf("\n"); } printf("请输入起点及终点：\n"); scanf("%d%d%d%d",&xa,&ya,&xb,&yb); //标记起点 maze[xa-1][ya-1]=2; //创建一个空栈 Stack s=creakEmptyStack(); mazePath(xa-1,ya-1,xb-1,yb-1,n,m,s); printf("最短路径长度为:%d",MIN); if(!flag) printf("没有成功找到路径\n"); } else printf("输入数据超出迷宫范围\n"); } //-----------遍历迷宫寻找路径(dfs)------------ void mazePath(int x,int y,int endx,int endy,int n,int m,Stack s){ int newx,newy,i; Node t; for(i=0;i<4;i++){ newx=x+direction[i][0]; newy=y+direction[i][1]; if(newx>=0&&newx<n&&newy>=0&&newy<m&&maze[newx][newy]==0){ //下一个路能走 push(newx,newy,s); maze[newx][newy]=2; if(newx==endx&&newy==endy){//走到出口 flag++; printPath(s,n,m); maze[newx][newy]=0; pop(s); } else{ mazePath(newx,newy,endx,endy,n,m,s); //开始递归 } } } maze[x][y]=0; //遍历完四个方向之后回溯前将自己赋为空 pop(s); } //-------------打印迷宫路径----------------- void printPath(Stack s,int n,int m){ int cont =0; //计算路径长度 s=s->next; int i=0,j=0; printf("第%d条路径为：\n",flag); for(i=0;i<n;i++){ //按图形输出 for(j=0;j<m;j++){ if(maze[i][j]==2) printf("* "); else printf("%d ",maze[i][j]); } printf("\n"); } while(s->next){ //将栈中的元素输出为直观路径 printf("(%d,%d)->",s->x+1,s->y+1); s=s->next; cont++; } printf("(%d,%d)",s->x+1,s->y+1); cont++; if(cont<MIN) MIN=cont; printf("\n"); printf("路径长度为：%d\n\n",cont); }
测试样例:
