寻找两点之间步数最少的方法？

Question

我有一个网格，这个网格有两个“材料”-

-Floor -Wall

例如：

在这个网格中，我们有大小和位置的对象（对象的位置是左上角点）。

我们可以对每个对象执行一些操作，如-

-向上移动 -向下移动 -向左移动 -向右移动 -转动对象（相对于左上角点）

我需要编写一个函数，返回我需要在对象上执行的最小操作次数，以将其从一个点移动到另一个点（我只需要操作次数）。

我使用dijkstra算法解决了这个问题，但没有转动操作。

所以，有人能帮我构建这个函数吗？

问题的示例：

• 起始点 -

• 终点

我需要返回在一个对象上执行的最小操作数量。

- Green Fire

---

无论使用哪种语言（C++、C、VB.NET、Java、C#），都没有太大关系。 - Green Fire

提示：考虑对象在任何时刻的状态。除了通常的（x，y）坐标之外，还需要记录什么？四个方向移动中的每一个都会改变状态的x或y坐标；转弯移动会改变什么？ - j_random_hacker

转向移动将改变对象的大小，如下所示 - 大小=反转（当前大小），高度=宽度，宽度=高度。 - Green Fire

我的意思是：不要把图中的顶点真正地看作迷宫中所有位置的代表；它们代表对象可能处于的所有可能状态。 对象状态的一部分是它的（左上角的）位置，但这并不是全部。 - j_random_hacker

向上移动 - 您将向上移动一个位置（Y + 1）。 向左移动 - 您将向左移动一个位置（X-1）。 向下移动 - 您将向下移动一个位置（Y-1）。 向右移动 - 您将向右移动一个位置（x + 1）。 旋转 - 它将使对象旋转90度，这意味着您需要更改对象的大小，高度=宽度，宽度=高度。 - Green Fire

Answer 1

考虑将问题看作在三维网格中寻找最短路径，其中深度为2（每种可能状态：水平和垂直）。您需要编写约束条件，以防止从一个深度移动到另一个深度，例如，如果无法适配，则不能垂直移动。
现在您可以使用常规BFS来查找网格中的最短路径（即，无权图）。

- Juan Lopes

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方法，并创建一个二维数组来存储每个点的最短路径长度。出队以获取当前点，将当前点的相邻连接点添加到队列中，并将此点标记为VISITED，然后一切都与BFS相同。

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

- pwwpche

Answer 3

如果我理解你的问题，把它写出来需要太长时间了，但是我能想到最简单的方法是首先找到路径，沿着该路径检查碰撞，旋转并相应添加操作。

• 使用基本的路径算法找到结束点的路径。
• 将路径节点存储在可遍历数组中（如果路径算法是良好/简单的，则应为4个节点）。
• 尝试跟随路径节点（从i到数组计数）
• 在每次移动时检查碰撞。
• (do while) 如果可移动对象与墙相交，则旋转90度并重新尝试。
• (next) 如果成功，保存到移动操作列表（移动x/y，旋转z）
• 返回动作计数

在更复杂的网格上，这显然会变得更加复杂，但是您只需进行90度的转向。可以在大约9个动作内完成。

- Keith

Answer 4

使用广度优先搜索策略，根据是否必须转动物体来为边分配权重。

- joseca

---

这个方法存在问题，因为在搜索中我们可能会陷入循环，比如向上移动、向下移动、向上移动、向下移动... - Green Fire

这样做不行，因为你不知道对象当前的方向是什么--它可能是任何一个方向。-1。 - j_random_hacker

这比那复杂得多，旋转对象的能力意味着对象可以在相同位置处处于不同状态。 - Rerito