qazwsxedc1267834 2022-06-04 15:21 采纳率: 100%
浏览 83
已结题

用栈存储路径,深度搜索算法解决迷宫问题,递归搜索上下左右四个方向

问题遇到的现象和发生背景

用栈来解决迷宫问题
给定迷宫起点和终点,寻找一条从起点到终点的路径。

要求搜寻策略是从起点开始按照“上、下、左、右”四个方向寻找终点,到下一个点继续按照“上、下、左、右”四个方面寻找,当该结点四个方向都搜寻完,但还没到终点时,退回到上一个点,直到找到终点或者没有路径。

比如上图从(1,1)开始,向上(0,1)不通,向下到(2,1);到了(2,1)后继续按“上、下、左、右”四个方面寻找,上已经走过,向下到(3,1);到(3,1)后上已经走过,下和左不通,向右到(3,2);到(3,2)四个方面都不通,回到(3,1)四个方向都不通,再回到(2,1),(1,1);到达(1,1)后下已经走过,左不通,继续向右走,重复这个过程最后到达(3,4)。

Input
第一行两个数m和n表示迷宫的行数和列数。迷宫大小不超过100×100

第二行四个数x1,y1,x2,y2分别表示起点和终点的坐标。
接下来是m行n列的数,用来表示迷宫,1表示墙,0表示通路。
Output
从起点到终点所经过的路径的坐标。如果不存在这样的路径则输出“No Path!”。

问题相关代码,请勿粘贴截图
运行结果及报错内容
我的解答思路和尝试过的方法

我不会用递归,要求是递归。

我想要达到的结果

希望得到不同于网上查到的源代码,用于读懂代码。
只希望得到源代码和清晰的注释。(不要百度查到的代码)
必须用栈解决,深度搜索解决

  • 写回答

4条回答 默认 最新

  • 关注

    不同于网上查到的源代码,

    img

    #include<stdio.h>
    #include<stdlib.h>
    
    #define maxsize 1000
    typedef struct data
    {
        int x;
        int y;
    }DATA;
    
    int ds[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
    int m,n,len=0;
    int a[100][100];
    DATA p[maxsize];
    
    int dfs(int x, int y,int x2, int y2) {
        p[len].x = x;
        p[len].y = y;
        len++;
        a[x][y] = 2;
        if (x == x2 && y == y2) {
            return 1;
        }
        for (int i = 0; i < 4; i++) {
            int tx = x + ds[i][0];
            int ty = y + ds[i][1];
            if (a[tx][ty]==0 && tx >= 0 && tx < m && ty >= 0 && ty < n) {
                if (dfs(tx, ty, x2, y2))
                    return 1;
            }
        }
        a[x][y] = 0;
        len--;
        return 0;
    }
    int main()
    {
        int x1,y1,x2,y2;
        int i,j;
        scanf("%d %d",&m,&n);
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        for(i=0;i<m;i++)
        {
            for(j=0;j<n;j++)
                scanf("%d",&a[i][j]);
        }
        if (dfs(x1,y1,x2,y2))
        {
            for(i=0;i<len;i++)
            {
                printf("(%d,%d) ", p[i].x, p[i].y);
            }
        }
        else
        {
            printf("No Path!");
        }
        for(i=0;i<m;i++)
        {
            for(j=0;j<n;j++)
                printf("%d ",a[i][j]);
            printf("\n");
        }
    
        return 0;
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
查看更多回答(3条)

报告相同问题?

问题事件

  • 已结题 (查看结题原因) 6月7日
  • 已采纳回答 6月5日
  • 创建了问题 6月4日

悬赏问题

  • ¥15 maccms影视模板 制作影视网站失败 求
  • ¥15 stm32按键设置闹钟数进退位不正常
  • ¥15 三电平逆变器中点电位平衡问题
  • ¥20 这怎么写啊 java课设
  • ¥15 用C语言完成一个复杂的游戏
  • ¥15 如何批量更改很多个文件夹里的文件名中包含文件夹名?
  • ¥50 MTK手机模拟HID鼠标出现卡顿
  • ¥20 求下下面这个数据结构代码
  • ¥20 前端 二进制文件流图片转化异常
  • ¥15 github上的这个C语言项目如何跑起来