找到带有障碍物的2D矩阵中到达给定目标单元的最短路径

Question

我正在处理下面的面试问题,我对如何在这里使用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();
    }
}

Answer 1

您可以简单地将网格视为图形：每个单元格都与其四个邻居相连（如果位于边缘则更少），不包括任何封锁。使用你的例子：

\n\n

  1 2 3\n1 \xe2\x80\xa2 \xe2\x80\xa2 \xe2\x80\xa2\n2 \xe2\x80\xa2 x \xe2\x80\xa2\n3 \xe2\x80\xa2 \xe2\x80\xa2 \xe2\x80\xa2\n

\n\n

我们有图表（使用（行，列）表示法）：

\n\n

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

\n\n

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

\n\n

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

\n