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

本文将介绍如何使用Java代码，在一个n x n的二进制矩阵中找到最短畅通路径。

问题描述：

给定一个n x n的二进制矩阵grid，其中：

'0'表示畅通单元格
'1'表示障碍物单元格

找到从左上角单元格(0, 0)到右下角单元格(n - 1, n - 1)的最短畅通路径长度。路径只能经过值为'0'的单元格，且只能在八个方向上移动（上、下、左、右、左上、左下、右上、右下）。如果不存在这样的路径，则返回-1。

解题思路：

这个问题可以使用广度优先搜索（BFS）算法有效地解决。BFS算法从起点开始，逐层探索其所有可到达的相邻节点，直到找到目标节点。

算法步骤：

创建一个队列queue，并将起点(0, 0)加入队列。
创建一个二维数组visited，用于标记矩阵中每个单元格是否已被访问过。将起点(0, 0)标记为已访问。
初始化步数steps为0。
当队列不为空时，执行以下步骤：
- 获取队列的大小size，表示当前层级节点的数量。
- 遍历当前层级的size个节点：
  - 从队列中取出一个节点。
  - 如果该节点是目标节点(n - 1, n - 1)，则返回当前步数steps。
  - 否则，遍历该节点的八个相邻节点：
    - 如果相邻节点在矩阵范围内，且其值为'0'，且未被访问过，则将该节点加入队列，并标记为已访问。
- 步数steps加1。
如果队列为空仍未找到目标节点，则说明不存在可行路径，返回-1。

Java代码实现：

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    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 LinkedList<>();
        queue.offer(new int[]{0, 0});
        boolean[][] visited = new boolean[n][n];
        visited[0][0] = true;
        int[][] dirs = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();
                int row = curr[0];
                int col = curr[1];
                if (row == n - 1 && col == n - 1) {
                    return steps + 1;
                }
                for (int[] dir : dirs) {
                    int newRow = row + dir[0];
                    int newCol = col + dir[1];
                    if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n && grid[newRow][newCol] == 0 && !visited[newRow][newCol]) {
                        queue.offer(new int[]{newRow, newCol});
                        visited[newRow][newCol] = true;
                    }
                }
            }
            steps++;
        }
        return -1;
    }
}

示例：

int[][] grid = {{0, 1, 0, 0, 0}, {0, 1, 0, 1, 0}, {0, 0, 0, 1, 0}, {1, 1, 1, 0, 1}, {0, 0, 0, 0, 0}};
Solution solution = new Solution();
int shortestPathLength = solution.shortestPathBinaryMatrix(grid);
System.out.println("最短路径长度：" + shortestPathLength);
// 输出：最短路径长度：7

总结：

本文介绍了如何使用Java代码实现二进制矩阵最短畅通路径算法，并提供了详细的代码示例和解释。该算法利用广度优先搜索(BFS)高效地找到了从起点到目标节点的最短路径。希望本文能够帮助读者更好地理解和应用该算法。