找到两点之间的最小步数？

Question

我有一个网格,网格有两个"材料" -

• 地板
• 壁

例如 :

在这个网格中,我们有对象具有大小和位置(对象的位置是左上角).

在每个对象上我们可以做一些动作,如 -

• 提升
• 下移
• 向左移动
• 向右移
• 转动物体(相对于左上角)

我需要创建一个函数来返回我需要对对象执行的最小操作量,以便将它从一个点移动到另一个点(我只需要操作量).

我使用dijkstra的算法解决了这个问题,但没有转弯动作.

所以任何人都可以帮我构建这个功能.

问题的例子 -

• 起点 -

• 终点

我需要返回我需要对对象执行的最少量操作.

Answer 1

将问题视为在3D网格中找到最短路径,深度为2(每种可能的状态:水平和垂直).你必须编码不允许一个人从一个深度移动到另一个深度的约束,例如,如果它不适合那样,就不能垂直.

现在,您只需使用常规BFS即可找到网格中的最短路径(即未加权图形).

Answer 2

对于你的问题，我认为BFS仍然有效。

使用BFS解决传统的迷宫问题，从起点开始，你必须：

1. Enqueue every point that is accessible (not a piece of wall, and not visited) and connected to the current point.
2. Dequeue current point and mark it as VISITED.

从上面可以看出，BFS 不会让任何点被访问两次，从而避免了循环。

你的问题

至于你的问题，BFS仍然有效，但我们将稍微改变“可访问”的定义：

首先，我来介绍一下“迷宫”矩阵是什么样子的。以下是下图中数字的含义。

（假设物体大小为1*2，移动时物体左上角停留在每个点）。

00: The point can't be accessed, neither the object is horizontal nor vertical. 
10: The point can be accessed if the object is horizontal
01: The point can be accessed if the object is vertical
11: The point can be accessed if the object is either horizontal or vertical

你的图可以转换成矩阵，如下所示：

将那些无法到达的点填入00，你会得到

这更像是一个迷宫问题，但有点不同。

最后，让我们看看如何“访问”这些点：

的定义connected与传统的迷宫问题类似。这里有些例子：

---------
| 01| 10|
|---|---|
| 10|   |
---------    (Not Connected from top-left to either top-right or bottom-left)


---------
| 11| 10|
|---|---|
| 01|   |
---------    (Connected from top-left to both top-right and bottom-left)


---------
| 10| 10|
|---|---|
| 01|   |
---------    (Connected from top-left to top-right, but not connected to bottom-left)

所以剩下的可能很简单。遵循传统的BFS方法，创建一个二维数组来存储每个点的最短路径的长度。出队获取当前点，将connected当前点的邻居添加到队列中，并将该点标记为已访问，然后一切都将与 BFS 相同。

得到最短路径后，重新运行程序，保持物体在当前点是垂直还是水平的状态，并在图像上模拟您的移动。仅在必要时添加匝数，您将得到添加匝数的结果。