> 文档中心 > 『牛客|每日一题』走迷宫

『牛客|每日一题』走迷宫

活动地址:CSDN21天学习挑战赛
👨‍🎓作者简介:一位喜欢写作,计科专业大二菜鸟

🏡个人主页:starry陆离

🕒首发日期:2022年7月29日星期五

🌌上期文章:『牛客|每日一题』点击消除

📚订阅专栏:『牛客刷题集锦』

🍁每日推荐:基础算法无论在研究生面试还是求职面试都是十分重要的一环,这里推荐一款算法面试神器:牛客网-面试神器;算法题只有多刷勤刷才能保持思路与手感,大家赶紧行动起来吧(温馨提示:常见的面试问答题库也很nice哦)
『牛客|每日一题』走迷宫

如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦

在这里插入图片描述

『牛客|每日一题』走迷宫

  • 1.每日一题
  • 2.解题思路
    • 2.1思路分析
    • 2.2BFS代码
    • 2.3核心代码

1.每日一题

原题链接:传送门-》戳我

『牛客|每日一题』走迷宫

2.解题思路

2.1思路分析

典型的bfs板子题,创建一个队列,首先存入起点坐标,依次取队首元素,然后通过一个方向数组来向四周扩展,在扩展的时候需要剪枝操作,避免越界以及重复访问某一点;遇到可访问且从未被访问的点时,就加入队列中,直到找到目标坐标为止。

  • step 1:bfs部分的核心代码的传参就是起点坐标和终点坐标

  • step 2:用一个dp[]数组来记录此点是否被访问及访问此点时已走的步数

  • step 3:首先将起点坐标加入队列中,并标记此点的dp[][]状态为已访问(非0就是已访问状态)

  • step 4:只要队列不空且没有找到终点就循环的取队首元素,通过方向数组向四周扩展

  • step5:通过check()当前点是否在迷宫范围内且没有被访问即dp[][]==0,并且是可访问的点"."

  • step6:将此点加入队列中,修改此点已被访问(修改dp[][][][]数组的值),并记录这是第几步

  • step7:继续取队首元素,如果是终点坐标就退出循环,输出终点dp[][][][]数组的值就是走过的最少步数(读者可细品这是为什么,关键代码就这一行)

  • //修改此点已被访问,并记录这是第几步dp[newx][newy]=dp[now.x][now.y]+1;

2.2BFS代码

private static void bfs(int xs, int ys, int xt, int yt) {    queue=new LinkedList<Node>();    dp=new int[n+1][m+1];queue.add(new Node(xs, ys));//将起点坐标加入队列dp[xs][ys]=1;//标识此点已经访问过,且是第一步f=false;//初始状态没有找到终点,所以标记f为false//队列不为空就继续寻找while(!queue.isEmpty()) {//取出队首元素Node now=queue.poll();//队首元素与终点坐标相同,找到了,修改标记f,并退出循环if(now.x==xt&&now.y==yt) {f=true;break;}//扩展队首元素的四周的点for(int i=1;i<=4;++i) {int newx=now.x+dx[i];int newy=now.y+dy[i];//剪枝操作,check()当前点在迷宫范围内且没有被访问即dp[][]==0,并且是可访问的点"."if(check(newx,newy)&&map[newx].charAt(newy-1)=='.') {//将此点加入队列中queue.add(new Node(newx, newy));//修改此点已被访问,并记录这是第几步dp[newx][newy]=dp[now.x][now.y]+1;}}}}

2.3核心代码

import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;//保存顶点坐标class Node{int x,y;public Node(int x, int y) {super();this.x = x;this.y = y;}}public class Main {static int dp[][];//用来记录当前点是否访问,以及访问的步数//方向数组static int dx[]= {0,0,1,0,-1};static int dy[]= {0,-1,0,1,0};static String map[];//用来存储迷宫static int n,m;//迷宫的规模static Queue<Node>queue;//队列,用bfs解题static boolean f;//标识是否找到终点public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int xs,ys,xt,yt;//起点、终点坐标while(scanner.hasNext()) {n=scanner.nextInt();m=scanner.nextInt();map=new String[n+1];xs=scanner.nextInt();ys=scanner.nextInt();xt=scanner.nextInt();yt=scanner.nextInt();//获取迷宫输入for(int i=1;i<=n;++i) {map[i]=scanner.next();}//广度优先搜索bfs(xs,ys,xt,yt);//打印输出if(f) {System.out.println(dp[xt][yt]-1);}else {System.out.println("-1");}}scanner.close();}private static void bfs(int xs, int ys, int xt, int yt) {queue=new LinkedList<Node>();dp=new int[n+1][m+1];queue.add(new Node(xs, ys));//将起点坐标加入队列dp[xs][ys]=1;//标识此点已经访问过,且是第一步f=false;//初始状态没有找到终点,所以标记f为false//队列不为空就继续寻找while(!queue.isEmpty()) {//取出队首元素Node now=queue.poll();//队首元素与终点坐标相同,找到了,修改标记f,并退出循环if(now.x==xt&&now.y==yt) {f=true;break;}//扩展队首元素的四周的点for(int i=1;i<=4;++i) {int newx=now.x+dx[i];int newy=now.y+dy[i];//剪枝操作,check()当前点在迷宫范围内且没有被访问即dp[][]==0,并且是可访问的点"."if(check(newx,newy)&&map[newx].charAt(newy-1)=='.') {//将此点加入队列中queue.add(new Node(newx, newy));//修改此点已被访问,并记录这是第几步dp[newx][newy]=dp[now.x][now.y]+1;}}}}//剪枝操作,check()当前点在迷宫范围内且没有被访问即dp[][]==0private static boolean check(int newx, int newy) {if(newx>=1&&newx<=n&&newy>=1&&newy<=m&&dp[newx][newy]==0)return true;else return false;}}

『牛客|每日一题』走迷宫

📚订阅专栏:『牛客刷题集锦』

🍁每日推荐:基础算法无论在研究生面试还是求职面试都是十分重要的一环,这里推荐一款算法面试神器:牛客网-面试神器;算法题只有多刷勤刷才能保持思路与手感,大家赶紧行动起来吧(温馨提示:常见的面试问答题库也很nice哦)
『牛客|每日一题』走迷宫

如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦