题解 | #迷宫问题#

迷宫问题

https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc

递归遍历
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);
    }
}


全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 12:04
毕业生招你惹你了,问一个发薪日来一句别看网上乱七八糟的你看哪个工作没有固定发薪日扭头就取消了面试就问了一句公司都是这个态度吗还搞上人身攻击了...
程序员小白条:呃呃呃,都还没面试,我都不会问这么细,何况通不通过,去不去都另说,你没实力和学历的话,在外面就这样,说实话没直接已读不回就不错了,浪费时间基本上
点赞 评论 收藏
分享
05-26 10:24
门头沟学院 Java
qq乃乃好喝到咩噗茶:其实是对的,线上面试容易被人当野怪刷了
找工作时遇到的神仙HR
点赞 评论 收藏
分享
Gaynes:查看图片
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务