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代码
privatestaticvoidbfs(intxs, intys, intxt, intyt) {
queue=newLinkedList<Node>();
dp=newint[n+1][m+1];
queue.add(newNode(xs, ys));//将起点坐标加入队列
dp[xs][ys]=1;//标识此点已经访问过，且是第一步
f=false;//初始状态没有找到终点，所以标记f为false
//队列不为空就继续寻找
while(!queue.isEmpty()) {
//取出队首元素
Nodenow=queue.poll();
//队首元素与终点坐标相同，找到了，修改标记f，并退出循环
if(now.x==xt&&now.y==yt) {f=true;break;}
//扩展队首元素的四周的点
for(inti=1;i<=4;++i) {
intnewx=now.x+dx[i];
intnewy=now.y+dy[i];
//剪枝操作，check()当前点在迷宫范围内且没有被访问即dp[][]==0，并且是可访问的点"."
if(check(newx,newy)&&map[newx].charAt(newy-1)=='.') {
//将此点加入队列中
queue.add(newNode(newx, newy));
//修改此点已被访问，并记录这是第几步
dp[newx][newy]=dp[now.x][now.y]+1;
}
}
}
}
2.2核心代码
importjava.util.LinkedList;
importjava.util.Queue;
importjava.util.Scanner;
//保存顶点坐标
classNode{
intx,y;
publicNode(intx, inty) {
super();
this.x=x;
this.y=y;
}
}
publicclassMain {
staticintdp[][];//用来记录当前点是否访问，以及访问的步数
//方向数组
staticintdx[]= {0,0,1,0,-1};
staticintdy[]= {0,-1,0,1,0};
staticStringmap[];//用来存储迷宫
staticintn,m;//迷宫的规模
staticQueue<Node>queue;//队列，用bfs解题
staticbooleanf;//标识是否找到终点
publicstaticvoidmain(String[] args) {
Scannerscanner=newScanner(System.in);
intxs,ys,xt,yt;//起点、终点坐标
while(scanner.hasNext()) {
n=scanner.nextInt();
m=scanner.nextInt();
map=newString[n+1];
xs=scanner.nextInt();
ys=scanner.nextInt();
xt=scanner.nextInt();
yt=scanner.nextInt();
//获取迷宫输入
for(inti=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();
}
privatestaticvoidbfs(intxs, intys, intxt, intyt) {
queue=newLinkedList<Node>();
dp=newint[n+1][m+1];
queue.add(newNode(xs, ys));//将起点坐标加入队列
dp[xs][ys]=1;//标识此点已经访问过，且是第一步
f=false;//初始状态没有找到终点，所以标记f为false
//队列不为空就继续寻找
while(!queue.isEmpty()) {
//取出队首元素
Nodenow=queue.poll();
//队首元素与终点坐标相同，找到了，修改标记f，并退出循环
if(now.x==xt&&now.y==yt) {f=true;break;}
//扩展队首元素的四周的点
for(inti=1;i<=4;++i) {
intnewx=now.x+dx[i];
intnewy=now.y+dy[i];
//剪枝操作，check()当前点在迷宫范围内且没有被访问即dp[][]==0，并且是可访问的点"."
if(check(newx,newy)&&map[newx].charAt(newy-1)=='.') {
//将此点加入队列中
queue.add(newNode(newx, newy));
//修改此点已被访问，并记录这是第几步
dp[newx][newy]=dp[now.x][now.y]+1;
}
}
}
}
//剪枝操作，check()当前点在迷宫范围内且没有被访问即dp[][]==0
privatestaticbooleancheck(intnewx, intnewy) {
if(newx>=1&&newx<=n&&newy>=1&&newy<=m&&dp[newx][newy]==0)returntrue;
elsereturnfalse;
}
}
📚订阅专栏：『牛客刷题集锦』
如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦
