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

川长思鸟来 2023-10-05 14:53 33阅读 0赞

#### 1091. 二进制矩阵中的最短路径 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

在一个 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 。  
![在这里插入图片描述][20201202220753861.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]

**提示：**  
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\]

![思路][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]

## 代码 ##

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;
        }
    }

[20201202220753861.png]: https://img-blog.csdnimg.cn/20201202220753861.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201202220801448.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201202223429540.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70