1091. Shortest Path in Binary Matrix(Medium)——计算在网格中从原点到特定点的最短路径长度

偏执的太偏执、 2023-06-09 14:27 15阅读 0赞

> ### 前言：   ###

刷了一段时间的LeetCode，准备找一些个人觉得比较好的题目分享给大家，同时也方便自己总结。

本题目为广度优先遍历（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：

输入：\[\[0,1\],\[1,0\]\]

输出：2

示例 2：

输入：\[\[0,0,0\],\[1,1,0\],\[1,1,0\]\]

输出：4

提示：

1 <= grid.length == grid\[0\].length <= 100  
grid\[i\]\[j\] 为 0 或 1

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/shortest-path-in-binary-matrix

> ###  解题算法： ###

本示例采用广度优先算法（BFS），算法简介如下，知道的小伙伴可以跳过。

# BFS #

[![format_png][]][format_png 1]

广度优先搜索一层一层地进行遍历，每层遍历都以上一层遍历的结果作为起点，遍历一个距离能访问到的所有节点。需要注意的是，遍历过的节点不能再次被遍历。

第一层：

*  0 -> \{6,2,1,5\}

第二层：

*  6 -> \{4\}
 *  2 -> \{\}
 *  1 -> \{\}
 *  5 -> \{3\}

第三层：

*  4 -> \{\}
 *  3 -> \{\}

每一层遍历的节点都与根节点距离相同。设 di 表示第 i 个节点与根节点的距离，推导出一个结论：对于先遍历的节点 i 与后遍历的节点 j，有 di <= dj。利用这个结论，可以求解最短路径等 **最优解** 问题：第一次遍历到目的节点，其所经过的路径为最短路径。应该注意的是，使用 BFS 只能求解无权图的最短路径，无权图是指从一个节点到另一个节点的代价都记为 1。

> ###  思路： ###

从一个左边位移动到另一个坐标位，在此题的环境中有八种方向可选，左上角、上、右上角等等。

对于坐标系来说，用横纵坐标分别加1、或减1就可以实现八个方向上的移动，我们用一个positions队列，来装每次移动可能涉及的所有坐标，既然是坐标，那也就说明这个队列里边装的是(key, value)形式的键值对，java的Pair对象就可以满足我们的存储需求，创建队列之后，我们往队列中加入初始点（0,0），然后用外层while循环控制每次遍历一层，并且使路径长度+1，用内层while循环来对目前队列中储存的所有的坐标进行八向移动，并把能成功移动到的坐标添加至队列末尾，为下一次的移动（外层循环）做准备。注意要先把移动前的坐标的值改为1，使其不再可达。最终在其到达（m-1,n-1）时，返回当前路径深度。

> ###  代码： ###

package LeetCode.搜索.BFS;
    
    import javafx.util.Pair;
    
    import java.util.LinkedList;
    import java.util.Queue;
    
    public class ShortestPathBinaryMatrix {
        public int shortestPathBinaryMatrix(int[][] grid) {
            if (grid[0][0] == 1) return -1;
            if (grid.length == 1) return 1;
            int m = grid.length, n = grid[0].length;
            int[][] directions = {
       {1, -1,}, {1, 0}, {1, 1}, {0, 1}, {0, -1}, {-1, 1}, {-1, 0}, {-1, -1}};
            Queue<Pair<Integer, Integer>> positions = new LinkedList<>();
            int pathLength = 0;
            positions.add(new Pair<>(0, 0));
    
            while (!positions.isEmpty()) {
                int size = positions.size();
                pathLength++;
                while (size-- > 0) {
                    Pair<Integer, Integer> cur = positions.poll();
                    int cr = cur.getKey(), cc = cur.getValue();
                    grid[cr][cc] = 1;
                    for (int[] direction : directions) {
                        int ncr = cr + direction[0];
                        int ncc = cc + direction[1];
                        if (ncr < 0 || ncr >= m || ncc < 0 || ncc >= n || grid[ncr][ncc] == 1) continue;
                        if (ncr == m - 1 && ncc == n - 1) return pathLength + 1;
                        positions.add(new Pair<>(ncr, ncc));
                    }
                }
            }
            return -1;
        }
    }

[format_png]: /images/20230531/26ece447dbe74f65a1c1beb1e7a98e41.png
[format_png 1]: https://github.com/CyC2018/CS-Notes/blob/master/notes/pics/95903878-725b-4ed9-bded-bc4aae0792a9.jpg