1091. 二进制矩阵中的最短路径（BFS）

题目

在一个 N × N 的方形网格中，每个单元格有两种状态：空（0）或者阻塞（1）。

一条从左上角到右下角、长度为 k 的畅通路径，由满足下述条件的单元格 C_1, C_2, …, C_k 组成：

• 相邻单元格 C_i 和 C_{i+1} 在八个方向之一上连通（此时，C_i 和 C_{i+1} 不同且共享边或角）
• C_1 位于 (0, 0)（即，值为 grid[0][0]）
• C_k 位于 (N-1, N-1)（即，值为 grid[N-1][N-1]）
• 如果 C_i 位于 (r, c)，则 grid[r][c] 为空（即，grid[r][c] == 0）

返回这条从左上角到右下角的最短畅通路径的长度。如果不存在这样的路径，返回 -1 。

提示：
1、1 <= grid.length == grid[0].length <= 100

2、grid[i][j] 为 0 或 1

解题思路

这题要求最短路径。第一时间想到BFS。
我们可以先举一个例子[0,1,1,0][0,0,0,1][0,1,0,0][1,1,0,0]

代码

class Solution {
   public int shortestPathBinaryMatrix(int[][] grid) {
        int[][] direction = new int[][]{{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};//分别代表八个方向，比如{1，0}就是右

        int x = grid.length;//横坐标
        int y = grid[0].length;//纵坐标

        Queue<Pair<Integer, Integer>> queue = new LinkedList<>();

        queue.add(new Pair<>(0, 0));//在队列中放入 第一步：{0,0}
        int step = 0;//步数



        while (!queue.isEmpty()) {//当队列中有东西的话

            step++;

            int size = queue.size();
            while (size-->0){


            Pair<Integer, Integer> poll = queue.poll();//返回队列的第一个元素，并且在队列中将其删除
            int key = poll.getKey();//key和val存放了我们遍历的那个值的下标
            int val = poll.getValue();

            if (grid[key][val] == 1) {//即遍历到的那个值为1.证明此路不通
                continue;
            }
            if (key == x - 1 && val == y - 1) {//该下标等于目标元素了，也就是正方形的最右下角那个元素
                return step;
            }

            grid[key][val] = 1;//如果它既不是1也不是目标元素，我们在遍历过它后就把它置为1，这样就不会二次访问到它了
            //注意 有些题目要求不能改动原数组，这就需要自己新建一个数组来存放是否访问过该元素。该题无此要求，我就直接置1

            for(int i = 0; i < 8; i++){//遍历八个方向找寻新的符合条件的数字
                int newkey = key + direction[i][0];
                int newval = val + direction[i][1];
                if (newkey>=x||newkey<0||newval>=y||newval<0){//查看新的下标是否越界
                    continue;
                }
                queue.add(new Pair<>(newkey,newval));//把新的满足条件的下标放入队列
            }




        }
        }
        return -1;
    }
}