本文共 2550 字，大约阅读时间需要 8 分钟。
在计算机科学中，广度优先搜索（BFS）是一种常用的算法，广泛应用于树和图的遍历问题中。本文将探讨如何利用BFS解决二进制矩阵中的最短路径问题。
广度优先搜索是一种层序遍历算法，能够有效地在图中找到最短路径。其核心思想是从起点出发，逐层扩展搜索，每一层遍历完毕后再向下一层进行扩展。这样，每次处理一层节点时，路径长度加1，这样第一次到达终点时，路径长度即为最短路径。
在本题中，二进制矩阵中的每个单元格代表一个节点，相邻单元格则代表节点之间的边。由于矩阵中的路径要求所有经过的单元格值为0，且路径可以在8个方向移动，因此我们需要对每个可移动的方向进行检查。
以下是实现该算法的Java代码：
import java.util.*;public class Solution { public int shortestPathBinaryMatrix(int[][] grid) { // 检查输入是否有效 if (grid == null || grid.length == 0 || grid[0].length == 0) { return -1; } int m = grid.length; int n = grid[0].length; // 定义八个方向 int[][] directions = { {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1} }; // 使用队列实现BFS Queue > queue = new LinkedList<>(); queue.add(new Pair<>(0, 0)); // 记录路径长度 int pathlength = 0; while (!queue.isEmpty()) { int size = queue.size(); pathlength++; // 处理当前层的所有节点 while (size > 0) { Pair current = queue.poll(); int currentRow = current.getKey(); int currentCol = current.getValue(); // 如果当前节点是终点，返回路径长度 if (currentRow == m - 1 && currentCol == n - 1) { return pathlength; } // 标记已访问的节点 grid[currentRow][currentCol] = 1; // 遍历八个方向，检查邻居是否在矩阵范围内 for (int[] direction : directions) { int newRow = currentRow + direction[0]; int newCol = currentCol + direction[1]; // 检查新坐标是否有效 if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) { queue.add(new Pair<>(newRow, newCol)); } } } } // 如果未找到终点，返回-1 return -1; }}// 辅助类，用于存储坐标对private static class Pair extends AbstractMap.Entry { Pair(T1 t1, T2 t2) { put(t1, t2); }} 输入检查：首先检查输入的二进制矩阵是否为空或任何维度为空，若为空则返回-1。
方向定义：定义了八个方向的数组direction，表示从当前节点可以移动到的八个相邻节点。
队列初始化：使用一个队列来存储当前层次的节点，起点(0,0)被加入队列。
BFS循环：队列不为空时，逐层处理节点。每次循环开始时，记录当前层次的节点数size，并增加路径长度。
处理每个节点：逐个提取队列中的节点，检查是否为终点。如果是终点，返回当前路径长度。否则，将该节点标记为已访问，并将其邻居节点加入队列。
邻居检查：遍历八个方向，检查新坐标是否在矩阵范围内。如果在，邻居节点被加入队列。
终点检查：如果终点未被访问到，返回-1。
通过上述方法，我们可以高效地找到二进制矩阵中的最短路径。BFS算法的层序遍历特性使其在求解最短路径问题上非常有效。代码实现详细地处理了每个节点的扩展，确保了路径的最短性和正确性。
转载地址：http://lpwc.baihongyu.com/