时间戳

首页 > 解决方案 > 在有障碍物的二维矩阵中找到到达给定目标单元的最短路径

java - 在有障碍物的二维矩阵中找到到达给定目标单元的最短路径

问题描述

我正在处理下面的面试问题，我对如何在这里使用 BFS 搜索感到困惑。我对如何处理这里的封锁感到困惑？

给定一个 MxN 矩阵，找到到达给定目标单元的最短路径。机器人可以上下左右移动。该矩阵还在机器人无法通过的少数几个单元中设置了一组封锁。输出机器人到达目的地所需的最小移动次数。如果目的地不可到达，则输出 -1。假设封锁永远不会在起始单元格。

输入格式：第一行包含 M 和 N 矩阵的值。第二行包含机器人起始位置的单元格位置。第三行包含目的地的单元格位置。第四行和随后的行将包含封锁的位置。下面的示例仅包含机器人无法通过的 (2,2) 处的一个封锁。下面是输入：

3 3
1 1
3 3
2 2

上述输入的输出应为 4。

以下是我开始的内容，但在进行 BFS 搜索时对如何处理此处的封锁感到困惑：

  public static void main(String args[] ) throws Exception {
    Scanner sc = new Scanner(System.in);
    int M = sc.nextInt();
    int N = sc.nextInt();

    int startX = sc.nextInt();
    int startY = sc.nextInt();

    int destinationX = sc.nextInt();
    int destinationY = sc.nextInt();

    while (sc.hasNext()) {
        int blockedX = sc.nextInt();
        int blockedY = sc.nextInt();
    }
}

标签： javaalgorithmdata-structuresdepth-first-searchbreadth-first-search

解决方案

您可以简单地将网格视为图形：每个单元都连接到它的四个邻居（如果它在边缘上则更少），不包括任何封锁。使用您的示例：

  1 2 3
1 • • •
2 • x •
3 • • •

我们有图表（使用 (row, col) 符号）：

(1,1) <-> (1,2)
(2,1) <-> (3,1)
(3,1) <-> (2,3)
(2,3) <-> (3,3)
(3,3) <-> (3,2)
(3,2) <-> (3,1)
(3,1) <-> (2,1)
(2,1) <-> (1,1)

其中所有边长均为 1。现在您可以从起始节点应用标准BFS，直到到达目标节点，跟踪您访问的节点。在伪代码中：

  • 将所有单元格距离标记为无限，除了距离为零的机器人起始单元格（您可以使用额外的 2D 数组来执行此操作，或者甚至可以就地执行此操作，具体取决于您存储网格的方式）。
  • 初始化一个空的单元队列 Q
  • 将机器人起始单元格添加到 Q
  • 当 Q 不为空时：
    • 从 Q 中取出下一个单元格 C
    • 对于C的每个非封锁邻居N（容易从网格中确定）：
      • 如果 N 的距离为无穷大，则将 N 的距离标记为（C 的距离）+1，并将 N 添加到 Q。
      • 如果 N 是目标单元格，则返回 N 的距离。
  • 在这一点上，我们知道从起始单元格到目标单元格没有路径。

推荐阅读