『牛客|每日一题』走迷宫
活动地址: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哦)
如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦