数据结构与算法大作业:走迷宫程序(C语言,DFS)(代码以及思路)

数据结构,算法,作业,迷宫,程序,c语言,dfs,代码,以及,思路 · 浏览次数 : 683

小编点评

```c #include #include #include // 定义结构体用来存储栈元素 typedef struct Stack { int top; int size; Node *elements; } Stack; // 定义结构体用来存储节点 typedef struct Node { int x; int y; int visited; } Node; // 定义迷宫大小 #define MAX_SIZE 20 // 定义方向数组 const int direction[][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} }; // 创建空栈 Stack *creakEmptyStack() { Stack *s = malloc(sizeof(Stack)); s->top = -1; s->size = 10; s->elements = malloc(sizeof(Node) * s->size); return s; } // 将元素压入栈 void push(int x, int y, Stack *s) { Node *p = malloc(sizeof(Node)); p->x = x; p->y = y; p->visited = false; s->elements[++s->top] = p; } // 从栈中取出元素 Node *pop(Stack *s) { Node *p = s->elements[s->top--]; free(p); return p; } // 遍历迷宫并寻找路径 void mazePath(int x, int y, int endx, int endy, int n, int m, Stack *s) { Node *t; for (int 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 = 1; 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; while (s->top > 0) { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (maze[i][j] == 2) { printf("* \"); } else { printf("%d ", maze[i][j]); } } } printf("\n"); s = s->elements[s->top--]; cont++; } } // 主函数 int main() { int n, m, i, j, xa, xb, endx, endy; // 初始化迷宫 n = MAX_SIZE; m = MAX_SIZE; maze = malloc(n * m * sizeof(Node)); // 设置结束位置 endy = n - 1; edx = n - 1; // 初始化栈 s = creakEmptyStack(); // 遍历迷宫并寻找路径 for (i = 0; i < n; i++) { for (j = 0; j < m; j++) { if (maze[i][j] == 0) { x = i; y = j; } } } // 从栈中取出元素并打印路径 while (x != endx && y != endy) { printf("%d,%d-%gt;\n", x, y, endx, endy); x = s->elements[s->top--]->x; y = s->elements[s->top--]->y; } printf("%d,%d)\n", x, y); // 释放资源 free(maze); free(s->elements); free(s); return 0; } ``` **测试样例:** ``` 第1条路径为: * * * * * * * * * * * * 路径长度为:10 ```

正文

好家伙,写大作业,本篇为代码的思路讲解

 

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)(代码以及思路)相似的内容:

数据结构与算法大作业:走迷宫程序(C语言,DFS)(代码以及思路)

好家伙,写大作业,本篇为代码的思路讲解 1.大作业要求 走迷宫程序 问题描述: 以一个 m * n 的长方阵表示迷宫, 0和1分别表示迷宫的通路和障碍。 设计一个程序, 对任意设定的迷宫, 求出一条从入口到出口的通路, 或得出没有通路的结论。 基本要求: (1) 实现一个以链表做存储的栈类型, 然后

数据结构与算法大作业:走迷宫程序(实验报告)

好家伙,本篇为应付老师的实验报告,有需要的拿去抄吧 思路讲解在上一篇: 数据结构与算法大作业:走迷宫程序(C,代码以及思路) 一、作业目的 1、 掌握用数据结构的知识进行程序设计。 2、 应用所学的数据结构完成一个具有一定实际意义的应用程序的设计、编码、调试,锻炼实践动手能力,提高编程水平。 二、作

数据结构(四):(顺序表)设计算法删除所有数字字符

好家伙,写作业 什么是顺序表: 顺序表是在计算机内存中以数组的形式保存的线性表,线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、 使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中,即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系, 采用顺序存

架构与思维:4大主流分布式算法介绍(图文并茂、算法拆解)

0 导读 之前的文章中,我们介绍过分布式事务的基础知识,也了解了分布式场景下常见一致性问题和解决方案,对分布式锁和CAS模式有一定的了解,有兴趣的同学可以通过下面链接到作者的两篇相关文章。 五种分布式事务解决方案(图文总结) 高并发下的数据一致性保障(图文全面总结) 1 介绍 本文聚焦高并发场景下分

C#数据结构与算法入门教程,值得收藏学习!

前言 最近看到DotNetGuide技术社区交流群有不少小伙伴提问:想要系统化的学习数据结构和算法,不知道该怎么入门,有无好的教程推荐的?,今天大姚给大家推荐2个开源、免费的C#数据结构与算法入门教程,值得收藏学习! 数据结构与算法的作用 数据结构与算法在计算机科学中具有不可替代的地位和作用。通过学

跳跃表数据结构与算法分析

目前市面上充斥着大量关于跳跃表结构与Redis的源码解析,但是经过长期观察后发现大都只是在停留在代码的表面,而没有系统性地介绍跳跃表的由来以及各种常量的由来。作为一种概率数据结构,理解各种常量的由来可以更好地进行变化并应用到高性能功能开发中。本文没有重复地以对现有优秀实现进行代码分析,而是通过对跳跃表进行了系统性地介绍与形式化分析,并给出了在特定场景下的跳跃表扩展方式,方便读者更好地理解跳跃表数据

Java 断言 Assert 使用教程与最佳实践

本文收录于 Github.com/niumoo/JavaNotes,Java 系列文档,数据结构与算法! 本文收录于网站:https://www.wdbyte.com/,我的公众号:程序猿阿朗 作为一个 Java 开发者,如果要问你 Java 中有哪些关键字,你可能会随口说出一串,如果问你 Java

LFU 的设计与实现

LFU 的设计与实现 作者:Grey 原文地址: 博客园:LFU 的设计与实现 CSDN:LFU 的设计与实现 题目描述 LFU(least frequently used)。即最不经常使用页置换算法。 题目链接:LeetCode 460. LFU Cache 主要思路 首先,定义一个辅助数据结构

基于深度学习的入侵检测系统综述文献概述——AI科研之路

1、研究方向的背景是什么? (1)互联网发展迅速,网络安全态势严重 (2)现在的入侵检测准确率不够高,不能适应现在的需求 2、前人做了哪方面的工作获得了什么成果? 近代: 将网络作为入侵来源之后发展(基于异常网络的检测技术): (1)基于数据挖掘与机器学习的入侵检测算法 (2)基于深度学习的入侵检测

OCR -- 文本检测 - 训练DB文字检测模型

PaddleOCR提供DB文本检测算法,支持MobileNetV3、ResNet50_vd两种骨干网络,可以根据需要选择相应的配置文件,启动训练。 本节以icdar15数据集、MobileNetV3作为骨干网络的DB检测模型(即超轻量模型使用的配置)为例,介绍如何完成PaddleOCR中文字检测模型的训练、评估与测试。