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<>(); // 队列记录即将遍历的结点// bfsd[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,会报空指针异常。