在带有障碍物的二维矩阵中找到到达给定目标像元的最短路径 [英] Find the shortest path to reach a given destination cell in 2D matrix with obstacles

问题描述

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

I am working on below interview question and I am confuse on how to use BFS search here. I am confuse on how to deal with the blockades here?

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

Given a MxN matrix find the shortest path to reach a given destination cell. The robot can move up, down, left or right. The matrix also comes with set of blockades in few of the cells where the robot can't pass through. Output the minimum number of moves the robot needs to make to reach the destination. Output -1 if the destination is not reachable. Assume that the blockade will never be at the starting cell.

输入格式:第一行包含M和N矩阵的值.第二 行包含机器人开始位置的单元格位置.第三 行包含目标的单元格位置.第四行和 接下来的几行将包含封锁的位置. 以下示例仅在(2,2)处进行了一次封锁，其中机器人 不能通过.输入如下:

Input Format: First line contains the values of M and N matrix. Second line contains the cell location of the robots starting position. Third line contains the cell location of the destination. Fourth line and the lines following that will contain the locations of the blockades. The example below contains only one blockade at (2,2) where the robot can't pass through. Below is the input:

3 3
1 1
3 3
2 2

上述输入的输出应为4.

Output should be 4 for above input.

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

Below is what I have started but confuse on how to deal with blockades here while doing BFS search:

  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();
    }
}

推荐答案

您可以简单地将网格查看为图形:每个单元都与其四个邻居(如果位于边缘则更少)相连，不包括任何障碍.以您的示例为例:

You can simply view the grid as a graph: each cell is connected to its four neighbors (or fewer if it's on an edge), excluding any blockades. Using your example:

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

我们有图(使用(行，列)表示法):

we have the graph (using (row, col) notation):

(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 开始节点，直到到达目标节点为止，并跟踪您访问了哪些节点.用伪代码:

where all edge lengths are 1. Now you can apply a standard BFS from the start node until you reach the target node, keeping track of which nodes you visit. In pseudocode:

• 将所有单元格距离标记为无穷大，除了机器人起始单元格的距离为零(您可以使用额外的2D数组，或者根据存储网格的方式甚至就地执行此操作).
• 初始化一个空的单元格队列Q
• 将机器人启动单元添加到Q
• 尽管Q不为空:
  • 从Q中取出下一个单元格C
  • 对于C的每个非阻塞邻居N(易于从网格中确定):
    • 如果N的距离为无穷大，则将N的距离标记为(C的距离)+1，然后将N加到Q.
    • 如果N是目标单元格，则返回N的距离.
    • Mark all cell distances as infinite except for the robot starting cell, which has distance zero (you can do this using an extra 2D array, or maybe even in-place depending on how you store the grid).
    • Initialize an empty queue of cells Q
    • Add the robot starting cell to Q
    • While Q is not empty:
      • Dequeue the next cell C from Q
      • For each non-blockade neighbor N of C (easy to determine from grid):
        • If N's distance is infinity, mark N's distance to be (C's distance) + 1, and add N to Q.
        • If N is the destination cell, return N's distance.

        这篇关于在带有障碍物的二维矩阵中找到到达给定目标像元的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！