Leetcode1091

• • Leetcode1091题：二进制矩阵中的最短路径（Java+BFS解法）
  • • • 1、题目链接
      • 2、解题思想
      • 3、Java代码

二进制矩阵中的最短路径

1. 使用广度优先搜索（BFS）的基本思想，目标位置 (n-1, n-1) 如果在第 x 层被搜索到，则路径途径的单元格数即为 x+1。
2. 我在这里使用了两个变量 count01 和 count02，分别用于记录正在遍历的层剩余的单元格数和即将要遍历的下一层的单元格数（不断加入新单元格），当 count01=0 时，这一层就遍历结束了，此时如果没有发现目标位置，则需要往下一层继续遍历，并将 count02 的值赋给 count01，count02 的值变为 0。
3. 对于题目给定的 8 个方向，我在这里使用了一种九宫格的形式。
4. 还有一个小技巧是 Java 中有一个 Pair 类，是一个没有严格映射关系的键值对，当然也可以使用 Integer 数组。

class Solution {

    public int shortestPathBinaryMatrix(int[][] grid) {
        //如果出发点的值为1,则直接返回-1
        if (grid[0][0] == 1) {
            return -1;
        }
        int n = grid.length;
        //定义两个变量count01和count02,分别表示BFS现在正在遍历的层和即将遍历的层(count01层的下一层)
        int num = 0, count01 = 1, count02 = 0;
        //借助Java里的Pair类表示键值对(没有对应关系),建立队列
        Queue> queue = new linkedList<>();
        queue.offer(new Pair<>(0, 0));
        grid[0][0] = 1;
        while (!queue.isEmpty()) {
            //count01=0表示该层已经遍历完了,需要遍历下一层了,同时num+1
            if (count01 == 0) {
                num++;
                count01 = count02;
                count02 = 0;
            }
            Pair temp = queue.poll();
            int i = temp.getKey(), j = temp.getValue();
            //到达终点返回结果
            if (i == n - 1 && j == n - 1) {
                return num + 1;
            }
            //可以理解为以(i,j)为中心的九宫格,代表了可以走的8个方向
            for (int m = i - 1 ; m <= i + 1 ; m++) {
                for (int k = j - 1; k <= j + 1; k++) {
                    //isValid()判断坐标值是否合法
                    if (isValid(m, k, n) && grid[m][k] == 0) {
                        queue.offer(new Pair<>(m, k));
                        grid[m][k] = 1;
                        count02++;
                    }
                }
            }
            count01--;
        }
        return -1;
    }

    private boolean isValid(int i, int j, int n) {
        return (i >= 0 && i <= n - 1) && (j >= 0 && j <= n - 1);
    }
 
}