二进制矩阵中的最短路径

问题陈述

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

思路分析

最短路通常考虑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
34
35
36
37
38
39
40
41
42
43
44
45
46
public class ShortestPathBinaryMatrix {
    public int shortestPath(int[][] grid){
        int n=grid.length;
        //当起始位和终点位为1，即阻塞。
        if(grid[0][0]==1||grid[n-1][n-1]==1){
            return -1;
        }
        //初始化队列存储当前层元素，boolean数组判断该元素是否为0（即路径可走）。
        Queue<int[]> queue=new ArrayDeque<>();
        boolean[][] vis=new boolean[n][n];
        //加入初始位
        queue.offer(new int[]{0,0});
        vis[0][0]=true;
        //八邻域方向
        int[][] direction=new int[][]{{0,1},{0,-1},{1,0},{-1,0},{-1,1},{-1,-1},{1,1},{1,-1}};
        //res记录可作为路径的当前点
        int res=1;
        //层序遍历
        while (!queue.isEmpty()){
            int size= queue.size();
            while (size--!=0){
                int[] cur= queue.poll();
                //到达终点则返回res
                if(cur[0]==n-1&&cur[1]==n-1){
                    return res;
                }
                //判断该位置元素和它的八邻域元素是否构成路径
                for(int[] dir:direction){
                    int x=cur[0]+dir[0];
                    int y=cur[1]+dir[1];
                    if(x>=0&&x<n&&y>=0&&y<n&&grid[x][y]==0){
                        vis[x][y]=true;
                        queue.offer(new int[]{x,y});
                    }
                }
            }
            res++;
        }
        return -1;
    }
    public static void main(String[] args){
        int[][] grid={{0,1},{1,0}};
        ShortestPathBinaryMatrix shortestPathBinaryMatrix=new ShortestPathBinaryMatrix();
        System.out.println(shortestPathBinaryMatrix.shortestPath(grid));
    }
}