题解 | #迷宫问题#

迷宫问题

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

#include<stdio.h>

// 思想:逐一遍历所有可能的可行路径,若当前可行路径距离小于小于最小的路径长度,则替换
// 定义结构体
typedef struct loca{
    int x;
    int y;
}LOCA;
// 设置全局变量-这些变量可在每个递推中都可被更新
int n_row,n_colum;
int maze[10][10];
int dist_min;                //记录最短路径长度
LOCA loca[100],loca_min[100];//记录当前路径和最短路径

void search_path(int x,int y,int len);


int main(){
    dist_min = 101;
    int dist = 0;
    scanf("%d %d",&n_row,&n_colum);
    for(int i=0;i<n_row;i++){
        for(int j=0;j<n_colum;j++){
            scanf("%d",&maze[i][j]);
        }
    }
    search_path(0,0,dist);
    for(int i=0;i<dist_min;i++){
        printf("(%d,%d)\n",loca_min[i].x,loca_min[i].y);
    }
}

void search_path(int x,int y,int dist){
    // 更新距离和保存当前位置
    loca[dist].x = x;
    loca[dist].y = y;
    dist = dist + 1; 
    // 判断是否到达终点
    if(x==n_row-1 && y==n_colum-1){
        if(dist<dist_min){    // 若更短则更新
            dist_min = dist;
            for(int i=0;i<dist_min;i++){
                loca_min[i].x = loca[i].x;
                loca_min[i].y = loca[i].y;
            }
        }
    }
    else{
        // 该四条语句即当前节点的四个可能的子节点,他们前面有相同的路径(相同的dist),但在此出现了分叉
        maze[x][y] = -1;  //******* 当前节点已经走过,之后不能在走到此位置,防止绕圈卡死******
        if(maze[x][y+1]==0 && y+1<n_colum){  // yo
            search_path(x,y+1,dist);
        }
        if(maze[x][y-1]==0 && y-1>=0){ //下
            search_path(x,y-1,dist);
        }
        if(maze[x+1][y]==0 && x+1<n_row){ // 右
            search_path(x+1,y,dist);
        }
        if(maze[x-1][y]==0 && x-1>=0){ // 左
            search_path(x-1,y,dist);
        }
        maze[x][y] = 0;  //***** 恢复(运行到此时,以此为出发点的所有路径都已经遍历完毕*******
    }
    
}

全部评论
四个方向 走来时的那个方向也可以吗?
点赞 回复 分享
发布于 2023-07-08 18:36 江苏
最后不恢复maze[x][y]=0也是可以的
点赞 回复 分享
发布于 2022-04-24 19:22

相关推荐

06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
评论
6
1
分享

创作者周榜

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