844. 走迷宫

给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1表示不可通过的墙壁。
最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角 (n,m） 处，至少需要移动多少次。
数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤100
输入样例：

  1. 5 5
  2. 0 1 0 0 0
  3. 0 1 0 1 0
  4. 0 0 0 0 0
  5. 0 1 1 1 0
  6. 0 0 0 1 0

输出样例：

  1. 8

思路：

题目类型：带环的权重一致的最短路问题
最短路径问题：用bfs

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.         int n = sc.nextInt();
  7.         int m = sc.nextInt();
  8.         int[][] g = new int[n][m];
  10.         for (int i = 0; i < n; i++) {
  11.             for (int j = 0; j < m; j++) {
  12.                 g[i][j] = sc.nextInt();
  13.             }
  14.         }
  16.         System.out.println(bfs(g));
  17.     }
  18.     static int bfs(int[][] g) {
  19.         int n = g.length, m = g[0].length;
  20.         int[][] d = new int[n][m];
  22.         for (int i = 0; i < n; i++) {
  23.             Arrays.fill(d[i], -1);
  24.         }
  25.         d[0][0] = 0;
  27.         Queue<int[]> q = new LinkedList<>();
  28.         q.offer(new int[]{0, 0});
  30.         int[] idx = {-1, 0, 1, 0}, idy = {0, 1, 0, -1};
  32.         while (!q.isEmpty()) {
  33.             int[] t = q.poll();
  35.             for (int i = 0; i < idx.length; i++) {
  36.                 int x = t[0] + idx[i];
  37.                 int y = t[1] + idy[i];
  39.                 if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) {
  40.                     d[x][y] = d[t[0]][t[1]] + 1;
  41.                     q.offer(new int[]{x, y});
  42.                 }
  43.             }
  44.         }
  45.         return d[n-1][m-1];
  46.     }
  47. }