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

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

本文将介绍如何使用 Java 实现二进制矩阵中最短畅通路径算法。给定一个 n x n 的二进制矩阵 grid，目标是找到从左上角单元格 (0, 0) 到右下角单元格 (n - 1, n - 1) 的最短畅通路径长度。如果不存在这样的路径，则返回 -1。

定义

二进制矩阵中的畅通路径是指一条满足以下条件的路径：

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

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

思路：广度优先搜索

从起点 (0, 0) 开始，进行广度优先搜索。每次遍历到一个格子时，将其标记为已访问，并将其相邻的、未访问过的格子加入队列中。遍历到终点 (n-1, n-1) 时，返回当前步数即可。

需要注意的是，题目中要求路径中所有相邻的单元格应当在 8 个方向之一上连通，因此在遍历相邻格子时，需要遍历所有 8 个方向。

代码

public class ShortestPathInBinaryMatrix {

    private static final int[][] DIRECTIONS = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};

    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0 || grid[0][0] == 1 || grid[grid.length - 1][grid[0].length - 1] == 1) {
            return -1;
        }

        int n = grid.length;
        boolean[][] visited = new boolean[n][n];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        visited[0][0] = true;
        int steps = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] current = queue.poll();
                int row = current[0];
                int col = current[1];

                if (row == n - 1 && col == n - 1) {
                    return steps;
                }

                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});
                        visited[nextRow][nextCol] = true;
                    }
                }
            }
            steps++;
        }

        return -1;
    }

    public static void main(String[] args) {
        int[][] grid = {{0, 0, 0}, {1, 1, 0}, {1, 1, 0}};
        ShortestPathInBinaryMatrix solution = new ShortestPathInBinaryMatrix();
        int shortestPath = solution.shortestPathBinaryMatrix(grid);
        System.out.println("最短畅通路径长度: " + shortestPath);
    }
}

代码解释

1. DIRECTIONS 数组存储了 8 个方向的偏移量。
2. shortestPathBinaryMatrix 方法接受二进制矩阵 grid 作为参数，并返回最短畅通路径长度。
3. 首先判断输入矩阵是否有效，如果无效则直接返回 -1。
4. 初始化一个 visited 数组，用于记录已经访问过的格子。
5. 初始化一个队列 queue，并将起点 (0, 0) 加入队列中。
6. 设置 steps 为 1，表示初始步数。
7. 循环遍历队列，直到队列为空。
8. 每次循环中，取出队列首部的元素，并将其标记为已访问。
9. 遍历当前格子的 8 个方向，如果相邻格子满足条件（未访问过、值为 0），则将其加入队列中。
10. 如果当前格子是终点，则返回当前步数。
11. 循环结束后，如果队列为空，则说明不存在畅通路径，返回 -1。

示例

int[][] grid = {{0, 0, 0}, {1, 1, 0}, {1, 1, 0}};

对于这个例子，最短畅通路径长度为 4。

总结

本文介绍了如何使用 Java 实现二进制矩阵中最短畅通路径算法。该算法利用广度优先搜索，可以有效地找到最短的畅通路径。该算法可以应用于许多实际问题，例如寻路、网络流量分析等。