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

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

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

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

比如上图从(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!”。

问题相关代码，请勿粘贴截图

运行结果及报错内容

我的解答思路和尝试过的方法

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

我想要达到的结果

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

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

#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;
}

maze=[
[1,1,1,1,1,1,1,1,1,1],
[1,0,1,0,1,1,1,1,1,1],
[1,0,0,0,1,1,1,1,1,1],
[1,0,1,0,1,1,1,1,1,1],
[1,0,1,0,1,1,1,1,1,1],
[1,0,1,0,0,0,0,1,1,1],
[1,0,0,0,1,1,0,0,1,1],
[1,0,1,1,0,0,1,0,1,1],
[1,0,0,0,0,0,0,0,0,1],
[1,1,1,1,1,1,1,1,1,1],
] //迷宫转换成二维列表
dirs=[
lambda x,y:(x-1,y)
lambda x,y:(x+1,y)
lambda x,y:(x,y-1)
lambda x,y:(x,y+1)
]
def maze_path(x1,y1,x2,y2):
    path=[]
    path.append((x1,y1))
    while len(path)>0 :
        curnode=path[-1]
        if curnode[0]==x2 and cuenode[1]==y2:
            for p in path:
                print(p)
            return True
        for dir in dirs:
            nextnode=dir(curnode[0],cuenode[1])
            if maze[nextnode[0]][nextnode[1]]==0:
                path.append(nextnode)
                maze[nextnode[0]][nextnode[1]]=1
                break
        else:
            path.pop()
    else:
        print('没有路')
        return False
maze_path(1,1,8,8)

#include <stdio.h>
   #include <stdlib.h>
  #include <string.h>
   #include <math.h>
   
   typedef struct {
       int x;
       int y;
       int pre; //记录该结点的父结点（来源）
  }position;
  
  typedef struct my_queue {
      position *que;
     int front;
      int last;
  }Queue;
 
  Queue* create_emptyqueue();
  int isempty(Queue *q);
  void push_queue(Queue *q, position x);
  void pop_queue(Queue *q);
  
  int a[100][100];
  Queue *bfs(position st);
  void print(Queue *q, position ans);
  
  position begin, end;
  int m, n, flag = 0;

  int main() {
      int i, j;
      Queue *q;
      scanf("%d%d", &m, &n);
      scanf("%d%d%d%d", &begin.x, &begin.y, &end.x, &end.y);
     begin.pre = -1;
      for(i = 0; i < m; i++) {
          for(j = 0; j < n; j++)
              scanf("%d", &a[i][j]);
      }
      q = bfs(begin);
      if(!flag) printf("No Path!");
    else {
         print(q, q->que[q->front - 1]);
          printf("(%d,%d)", end.x, end.y);
      }
      return 0;
  }
 
  Queue *create_emptyqueue() {
      Queue *p;
      p = (Queue*)malloc(sizeof(Queue));
      if(p != NULL) {
          p->que = (position*)malloc(10000*sizeof(position));
          if(p->que != NULL) {
              p->front = 0;
              p->last = 0;
              return p;
          }
          else free(p);
      }
     return NULL;
  }
  
  int isempty(Queue *q) {
      return q->front == q->last;
  }
  
  void push_queue(Queue *q, position x) {
      if(q->last + 1 == q->front)
          printf("full\n");
      else {
          q->que[q->last] = x;
          q->last = q->last + 1;
      }
 }
  
  void pop_queue(Queue *q) {
     if(q->front == q->last)
          printf("empty\n");
     else
          q->front = q->front + 1;
 }
  
  Queue *bfs(position st) {
      int pr, i;
     int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
      position former, latter;
      position t;
      Queue *q = create_emptyqueue();
      former = st;
     push_queue(q, former);
      a[former.x][former.y] = 1;
      while(!isempty(q)) { //队列不为空，说明可能还有可走的路
         latter = q->que[q->front];
         pr = q->front;
          pop_queue(q);
          for(i = 0; i < 4; i++) {
             t.x = latter.x + dir[i][0];
            t.y = latter.y + dir[i][1];
             t.pre = pr; //记录该结点的来源
             if(t.x == end.x && t.y == end.y) {
                flag = 1;
                 return q;
             }
             if(!a[t.x][t.y] && t.x >= 0 && t.x < m && t.y >= 0 && t.y < n) {
                 push_queue(q, t);
                 a[t.x][t.y] = 1;
             }
        }
     }
     return q;
 }

 void print(Queue *q, position ans) { //递归输出
     if(ans.pre == -1) {
         printf("(%d,%d)", ans.x, ans.y);
         return ;
     }
     else {
      print(q, q->que[ans.pre]);
         printf("(%d,%d)", ans.x, ans.y);
     }
 }

您好，我是有问必答小助手，您的问题已经有小伙伴帮您解答，感谢您对有问必答的支持与关注！
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632