数据结构与算法大作业：走迷宫程序（C语言,DFS)(代码以及思路）
好家伙，写大作业,本篇为代码的思路讲解
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);
}
测试样例:
查看更多关于数据结构与算法大作业：走迷宫程序（C语言,DFS)(代码以及思路）的详细内容...