Java实现二进制矩阵中的最短路径

Java实现二进制矩阵中的最短路径

给定一个 n x n 的二进制矩阵 grid，你需要找到从左上角单元格 (0, 0) 到右下角单元格 (n - 1, n - 1) 的最短畅通路径的长度。

畅通路径定义为：

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

如果不存在这样的路径，返回 -1 。

解题思路：

这道题目可以使用广度优先搜索（BFS）来解决。

1. 定义一个队列来存储节点，并将起始节点 (0, 0) 加入队列，并标记为已访问。2. 循环遍历队列，直到队列为空： * 取出队列中的第一个节点。 * 如果该节点是目标节点 (n-1, n-1)，则返回当前路径长度。 * 遍历该节点的 8 个相邻节点： * 如果相邻节点在矩阵范围内，且值为 0，且未被访问过，则将其加入队列，并标记为已访问。3. 如果遍历完队列还没有找到目标节点，则说明不存在畅通路径，返回 -1。

Java代码实现：javaclass Solution { public int shortestPathBinaryMatrix(int[][] grid) { int n = grid.length; // 如果起点或终点是1，直接返回-1 if (grid[0][0] == 1 || grid[n-1][n-1] == 1) { return -1; } // 定义8个方向 int[][] dirs = {{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1}}; // 创建队列，并将起点加入队列 Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[]{0,0}); // 创建访问标记数组 boolean[][] visited = new boolean[n][n]; visited[0][0] = true; // 初始化路径长度 int level = 1; // 开始BFS遍历 while (!queue.isEmpty()) { int size = queue.size(); // 遍历当前层级的所有节点 for (int i = 0; i < size; i++) { int[] curr = queue.poll(); // 如果当前节点是终点，返回路径长度 if (curr[0] == n-1 && curr[1] == n-1) { return level; } // 遍历当前节点的8个相邻节点 for (int[] dir : dirs) { int x = curr[0] + dir[0]; int y = curr[1] + dir[1]; // 判断相邻节点是否合法，并加入队列 if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 0 && !visited[x][y]) { queue.offer(new int[]{x,y}); visited[x][y] = true; } } } // 层级加一 level++; } // 遍历完队列还没有找到目标节点，说明不存在畅通路径 return -1; }}