⭐题目日期：

字节 - 2024/9/29

🌳题目描述：

给定一个二维矩阵，其中包含起点、终点和障碍物。要求找到从起点到终点的最短路径，并打印该路径。

🧗难度系数：

⭐️ ⭐️ ⭐ ⭐

📝思路分析：

表示矩阵： 使用二维数组表示矩阵，矩阵中的元素可以是：

• 0：表示可通行的路径。
• 1：表示障碍物。
• 起点：左上角。
• 终点：右下角。

路径表示： 为了能够打印出路径，我们需要在搜索的过程中记录路径信息。

选择算法：

• 广度优先搜索（BFS）： BFS适合用于寻找无权图中的最短路径，因为它按层次遍历节点，先到达终点的一定是路径最短的。
• 深度优先搜索（DFS）： DFS适合用于遍历所有可能的路径，但不保证找到最短路径。

基于上述分析，我们选择使用 广度优先搜索（BFS） 来求解最短路径问题。

🌟算法步骤

初始化：

1. 创建一个队列 Queue，用于存储待访问的节点。
2. 创建一个二维数组 visited，用于标记已经访问过的节点，防止重复访问。
3. 创建一个二维数组 prev，用于记录每个节点的前驱节点，以便在找到终点后回溯路径。

开始 BFS 搜索：

1. 将起点加入队列，并标记为已访问。
2. 当队列不为空时，重复以下步骤：
   • 从队列中取出一个节点 current。
   • 如果 current 是终点，停止搜索。
   • 遍历 current 的四个方向（上、下、左、右），对于每个相邻的可通行节点：
     • 如果该节点未被访问过且不是障碍物：
       • 将该节点加入队列。
       • 标记为已访问。
       • 在 prev 数组中记录其前驱节点为 current。

回溯路径：

1. 从终点开始，根据 prev 数组回溯到起点，得到从起点到终点的最短路径。

打印路径：

1. 将路径上的节点坐标依次输出，或者在矩阵上标记路径。

💻代码：

Java

import java.util.*;

public class ShortestPathInMatrix {

 // 定义一个坐标类，表示矩阵中的一个位置
 class Point {
     int x;
     int y;
     Point parent; // 用于回溯路径

     public Point(int x, int y, Point parent) {
         this.x = x;
         this.y = y;
         this.parent = parent;
     }
 }

 // 定义方向数组，表示上、下、左、右四个方向
 static final int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

 // 寻找最短路径的函数
 public void findShortestPath(char[][] matrix) {
     int rows = matrix.length;
     int cols = matrix[0].length;

     boolean[][] visited = new boolean[rows][cols];

     Point start = new Point(0, 0, null);
     Point end = new Point(rows - 1, cols - 1, null);

     // 创建队列用于BFS
     Queue<Point> queue = new LinkedList<>();
     queue.offer(start);
     visited[start.x][start.y] = true;

     // 开始BFS搜索
     while (!queue.isEmpty()) {
         Point current = queue.poll();

         // 如果到达终点，停止搜索
         if (current.x == end.x && current.y == end.y) {
             end = current;
             break;
         }

         // 遍历四个方向
         for (int[] dir : directions) {
             int newX = current.x + dir[0];
             int newY = current.y + dir[1];

             // 检查新位置是否在矩阵范围内
             if (newX >= 0 && newX < rows && newY >= 0 && newY < cols) {
                 // 检查是否可通行且未被访问过
                 if (!visited[newX][newY] && matrix[newX][newY] == '0') {
                     queue.offer(new Point(newX, newY, current));
                     visited[newX][newY] = true;
                 }
             }
         }
     }

     // 如果找到路径，回溯并打印
     printPath(end, matrix);
 }

 private void printPath(Point end, char[][] matrix) {
     int rows = matrix.length;
     int cols = matrix[0].length;
     if (end.parent != null) {
         List<Point> path = new ArrayList<>();
         Point current = end;
         while (current != null) {
             path.add(current);
             current = current.parent;
         }
         Collections.reverse(path);
         System.out.println("找到最短路径，长度为：" + (path.size() - 1));
         System.out.println("路径为：");
         for (Point p : path) {
             System.out.println("(" + p.x + ", " + p.y + ")");
             // 在矩阵上标记路径
             if (matrix[p.x][p.y] == '0') {
                 matrix[p.x][p.y] = '*';
             }
         }

         // 打印标记路径后的矩阵
         System.out.println("路径图：");
         for (int i = 0; i < rows; i++) {
             for (int j = 0; j < cols; j++) {
                 System.out.print(matrix[i][j] + " ");
             }
             System.out.println();
         }
     } else {
         System.out.println("不存在从起点到终点的路径！");
     }
 }

 public static void main(String[] args) {
     // 示例矩阵
     char[][] matrix = {
             {'0', '0', '0', '0', '0'},
             {'0', '1', '1', '0', '1'},
             {'0', '1', '0', '0', '0'},
             {'0', '1', '0', '0', '0'},
             {'0', '0', '0', '1', '0'}
     };
     ShortestPathInMatrix test = new ShortestPathInMatrix();
     test.findShortestPath(matrix);
 }
}

🚵🏻复杂度分析：

时间复杂度: O(m * n)

空间复杂度: O(m * n)