AcWing 5978. 走迷宫JavaBFS
原题链接
简单
作者:
husheng
,
2024-11-27 17:35:30
,
所有人可见
,
阅读 14
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static class node{
int x,y;
node(int x,int y){
this.x=x;
this.y=y;
}
}
static int r,c;
static char[][] arr;
static int[][] dis;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
public static int bfs(int x,int y) {
Queue<node> que = new LinkedList<node>();
que.offer(new node(x,y));//将起点入队
dis[x][y]=0;
while(!que.isEmpty()) {
node t = que.poll();//移除并返回队列头部的元素
if(t.x==r-1&&t.y==c-1) {//找到出口
return dis[t.x][t.y];
}
for(int a=0;a<4;a++) {
int newx = t.x+dx[a];
int newy = t.y+dy[a];
if(newx>=0&&newx<r&&newy>=0&&newy<c&&arr[newx][newy]=='.'&&dis[newx][newy]==0) {
dis[newx][newy] = dis[t.x][t.y]+1;//dis是表示的是当前元素的层数,下一层的层数是当前的层数加1;
que.offer(new node(newx,newy));//将当前元素入队;
//BFS不用回溯
}
}
}
return -1;
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
r=input.nextInt();
c=input.nextInt();
arr = new char[r][c];
dis = new int[r][c];
for(int i=0;i<r;i++) {
arr[i] = input.next().toCharArray();
}
System.out.println(bfs(0,0)+1);
}
}