1216走迷宫
1216走迷宫
⭐️难度:简单
🌟考点:bfs
📖
📚
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int [][] a = new int [n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
a[i][j] = sc.nextInt();
}
}
int x1 = sc.nextInt();
int y1 = sc.nextInt();
int x2 = sc.nextInt();
int y2 = sc.nextInt();
boolean [][] v = new boolean[n+2][m+2];// 是否被访问
int [][] d = new int[n+1][m+1]; // 起点到各个点的距离
for (int i = 1; i <= n; i++) {
Arrays.fill(d[i],(int)1e9); // 先全部设为无限大,不可到达
}
Queue<int[]> q = new LinkedList<>(); // 队列记录即将遍历的结点
// bfs
d[x1][y1] = 0;
q.add(new int[]{x1,y1});
int[] dx = {0,0,1,-1}; // 分别对应:右左上下 四个操作
int[] dy = {1,-1,0,0};
while(!q.isEmpty()){
int []xy = q.poll();
int x = xy[0];
int y = xy[1];
if(v[x][y]) continue; // 已经被访问过了
v[x][y] = true;
for(int i = 0;i < 4;i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx > n || nx < 1 || ny > m || ny < 1 || a[nx][ny] == 0 || v[nx][ny]) continue; // 该点不合法:超出范围或不可访问或已被访问
q.add(new int[]{nx,ny});
d[nx][ny] = d[x][y] + 1; // 在原来的步数上+1,就走到了当前这个结点
}
}
if(!v[x2][y2]){ // 没有被访问,不可到达
System.out.println("-1");
}else{
System.out.println(d[x2][y2]);
}
}
}
细节:Boolean和boolean不一样,Boolean不会初始化为false,会报空指针异常。