Java 实现二进制矩阵最短畅通路径算法

本文将使用 Java 代码实现寻找二进制矩阵中最短畅通路径的算法。

问题描述:

给定一个 n x n 的二进制矩阵 grid，返回矩阵中最短畅通路径的长度。如果不存在这样的路径，返回 -1。

畅通路径 定义为从左上角单元格 (0, 0) 到右下角单元格 (n - 1, n - 1) 的路径，该路径同时满足下述要求：

路径途经的所有单元格的值都是 0。
路径中所有相邻的单元格应当在 8 个方向之一上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。

畅通路径的长度是该路径途经的单元格总数。

解题思路:

本题可以使用广度优先搜索 (BFS) 来解决。从起点开始搜索，每次搜索到一个节点时，将该节点标记为已访问，并将其所有未访问过的相邻节点加入队列中，直到搜索到终点或者队列为空为止。

具体实现:

使用一个二维数组 visited 来记录每个节点是否已经访问过，初始时所有节点都未被访问过。
每次访问一个节点时，将其标记为已访问，并将其坐标和当前路径长度加入队列中。
在搜索过程中，如果遇到终点，则返回当前路径长度；如果队列为空，则说明没有找到可行路径，返回 -1。
需要注意的是，在搜索过程中，需要判断每个相邻节点是否越界，以及是否已经被访问过。如果一个节点已经被访问过，则说明已经找到了更短的路径，不需要再次访问。

Java 代码实现:

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) {
            return -1;
        }
        boolean[][] visited = new boolean[n][n];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, 1}); // 起点坐标和路径长度
        visited[0][0] = true;
        int[][] directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int row = current[0];
            int col = current[1];
            int pathLength = current[2];
            if (row == n - 1 && col == n - 1) {
                return pathLength;
            }
            for (int[] direction : directions) {
                int nextRow = row + direction[0];
                int nextCol = col + direction[1];
                if (nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < n && grid[nextRow][nextCol] == 0 && !visited[nextRow][nextCol]) {
                    queue.offer(new int[]{nextRow, nextCol, pathLength + 1});
                    visited[nextRow][nextCol] = true;
                }
            }
        }
        return -1;
    }
}

代码解释:

首先判断起点和终点是否为 1，如果是则直接返回 -1。
初始化 visited 数组和队列，并将起点加入队列。
定义 directions 数组，存储 8 个方向的偏移量。
循环遍历队列，取出当前节点的信息。
判断当前节点是否为终点，如果是则返回路径长度。
遍历当前节点的 8 个方向的相邻节点。
判断相邻节点是否越界、是否为 0 以及是否已经被访问过。如果满足条件则将该节点加入队列并标记为已访问。
如果循环结束队列为空，则说明没有找到可行路径，返回 -1。