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

Question

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

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

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

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

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

运行结果及报错内容

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

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

我想要达到的结果

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

Answer 1

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

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