LeetCode1091-二进制矩阵中的最短路径

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/shortest-path-in-binary-matrix/

中文链接：https://leetcode-cn.com/problems/shortest-path-in-binary-matrix/

题目详述

在一个 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
2
3
输入：[[0,1],[1,0]]

输出：2

示例 2：

1
2
3
输入：[[0,0,0],[1,1,0],[1,1,0]]

输出：4

提示：

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

题目详解

  • 典型的 BFS。
  • 需要注意的两点：是八连通不是四连通，最长路径指的是点的个数而不是边的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class LeetCode_01091 {

    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) {
            return -1;
        }
        Queue<int[]> queue = new ArrayDeque<>();
        boolean[][] vis = new boolean[n][n];
        queue.offer(new int[]{0, 0});
        vis[0][0] = true;
        int[][] dirs = new int[][]{{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};
        int res = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- != 0) {
                int[] cur = queue.poll();
                if (cur[0] == n - 1 && cur[1] == n - 1) {
                    return res;
                }
                for (int[] dir : dirs) {
                    int x = cur[0] + dir[0], y = cur[1] + dir[1];
                    if (x >= 0 && x < n && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 0) {
                        vis[x][y] = true;
                        queue.offer(new int[]{x, y});
                    }
                }
            }
            ++res;
        }
        return -1;
    }
}