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

​

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

个人主页：starry陆离

首发日期：2022年7月29日星期五

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

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

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

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

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[][]==0
	private 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哦）

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