世界快看：数据结构与算法大作业：走迷宫程序（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 #include #include  #define MAXN 20struct 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=0&&newy

完整代码:

所有路径版本:

#include #include #include   #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=0&&newx=0&&newynext;    int i=0,j=0;    printf("第%d条路径为：\n",flag);    for(i=0;inext){                          //将栈中的元素输出为直观路径        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

测试样例: