题解 | #迷宫问题#

struct xy
{
    int x;
    int y;
};
typedef struct xy XY;
enum direction{UP,DOWN,LEFT,RIGHT};

int findPath(int **road, int curx, int cury, int endx, int endy, XY *paths, int *pathpos, int lastDirection)
{
    int ret;
    int value;
        
    if(curx>endx || curx<0 || cury>endy || cury<0)//越界了且不是右下角
        return 0;
    if(curx==endx && cury==endy)//到达右下角
    {
        paths[*pathpos].x = endx;//加入最后一个坐标
        paths[*pathpos].y = endy;
        (*pathpos)++;
        return 1;//递归返回1
    }
        
    value = *((int* )road+curx*(endy+1)+cury);
    if(value == 0)//查看是不是路“0”
    {
        paths[*pathpos].x = curx;//是路则加入路径栈
        paths[*pathpos].y = cury;
        //printf("+(%d, %d)\n", curx, cury);
        *((int* )road+curx*(endy+1)+cury) = -1;
        (*pathpos)++;
        
        //除原行进相反方向外的其他3个方向都尝试
        if(lastDirection != UP)
        {
            ret = findPath(road, curx+1, cury, endx, endy, paths, pathpos, DOWN);
            if(ret == 1)
                return 1;
        }
        if(lastDirection != LEFT)
        {
            ret = findPath(road, curx, cury+1, endx, endy, paths, pathpos, RIGHT);
            if(ret == 1)
                return 1;
        }
        if(lastDirection != DOWN)
        {
            ret = findPath(road, curx-1, cury, endx, endy, paths, pathpos, UP);
            if(ret == 1)
                return 1;
        }
        if(lastDirection != RIGHT)
        {
            ret = findPath(road, curx, cury-1, endx, endy, paths, pathpos, LEFT);
            if(ret == 1)
                return 1;
        }
        //printf("-(%d, %d)\n", curx, cury);
        (*pathpos)--;//都不通，回退一步，当前坐标出栈
        return 0;//此路不通
    }
    else //不是路撞墙了“1”，或是走过的路“-1”
        return 0;//此路不通
    
}

int main()
{
    int x,y;
    scanf("%d %d", &x, &y);
    int road[x][y];
    XY paths[x+y];
    int pathpos = 0;
    for(int i=0; i<x; i++)
        for(int j=0; j<y; j++)
            scanf("%d", &road[i][j]);
    
    findPath(road, 0,0, x-1,y-1, paths, &pathpos, DOWN);
    for(int i=0; i<pathpos; i++)
    {
        printf("(%d,%d)\n", paths[i].x, paths[i].y);
    }
}