找到两点之间的最小步数？
Finding the smallest number of steps between two points?
我有一个网格，网格有两个"Material" -
- 楼层
- 墙
例如：
在这个网格中，我们有具有大小和位置的对象（对象的位置是左上角的点）。
在每个对象上我们可以做一些像-
这样的动作
- 向上移动
- 下移
- 向左移动
- 右移
- 转动对象（相对于左上角）
我需要创建一个函数，return让我了解将对象从一个点移动到另一个点所需执行的最少操作量（我只需要动作量).
我使用 dijkstra's algorithm、 解决了这个问题，但没有使用转向操作 。
所以谁能帮我建立这个功能。
问题示例-
起点——
终点
而且我需要 return 我需要对一个对象执行的最少操作量。
使用Breadth-first search策略，根据对象是否必须转动来为边缘分配权重。
如果我明白你在问什么，写出来会花太长时间，但我能想到的最简单的方法是先找到路径，检查沿该路径的碰撞，旋转，然后添加相应的行动。
- 使用基本寻路算法找到到终点的路径。
- 将路径节点存储在某种可遍历数组中（如果路径算法是 good/simple，则总共应为 4 个）。
- 尝试跟随路径注释（i 到数组计数）
- 检查每次移动是否发生碰撞。
- (do while)如果可移动物体与墙相交，旋转90度再试。
- (下一步)如果成功，保存到移动动作列表(移动x/y，旋转z)
- Return 操作次数
如果网格更复杂，这显然会变得更复杂，但你只需要转90度。应该可以在 ~9 个动作中实现。
考虑在 3D 网格中寻找最短路径的问题，深度为 2（每种可能的状态：水平和垂直）。您必须编写禁止从一个深度移动到另一个深度的约束，例如，如果不适合这种方式，则不能垂直移动。
现在您只需使用常规 BFS 即可找到网格（即未加权图）中的最短路径。
对于你的问题，我觉得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，移动时，物体的top-left角停留在每个点）。
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个邻居加入队列，并将该点标记为VISITED，那么一切都和BFS一样。
得到最短路径后，re-run你的程序，保持一个物体在当前点是垂直还是水平的状态，模拟你在图像上的移动。仅在必要时添加转弯，您将获得添加转弯的结果。
我有一个网格，网格有两个"Material" -
- 楼层
- 墙
例如：
在每个对象上我们可以做一些像-
这样的动作- 向上移动
- 下移
- 向左移动
- 右移
- 转动对象（相对于左上角）
我需要创建一个函数，return让我了解将对象从一个点移动到另一个点所需执行的最少操作量（我只需要动作量).
我使用 dijkstra's algorithm、 解决了这个问题，但没有使用转向操作 。
所以谁能帮我建立这个功能。
问题示例-
起点——
终点
而且我需要 return 我需要对一个对象执行的最少操作量。
使用Breadth-first search策略，根据对象是否必须转动来为边缘分配权重。
如果我明白你在问什么，写出来会花太长时间，但我能想到的最简单的方法是先找到路径，检查沿该路径的碰撞，旋转，然后添加相应的行动。
- 使用基本寻路算法找到到终点的路径。
- 将路径节点存储在某种可遍历数组中（如果路径算法是 good/simple，则总共应为 4 个）。
- 尝试跟随路径注释（i 到数组计数）
- 检查每次移动是否发生碰撞。
- (do while)如果可移动物体与墙相交，旋转90度再试。
- (下一步)如果成功，保存到移动动作列表(移动x/y，旋转z)
- Return 操作次数
如果网格更复杂，这显然会变得更复杂，但你只需要转90度。应该可以在 ~9 个动作中实现。
考虑在 3D 网格中寻找最短路径的问题，深度为 2（每种可能的状态：水平和垂直）。您必须编写禁止从一个深度移动到另一个深度的约束，例如，如果不适合这种方式，则不能垂直移动。
现在您只需使用常规 BFS 即可找到网格（即未加权图）中的最短路径。
对于你的问题，我觉得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，移动时，物体的top-left角停留在每个点）。
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个邻居加入队列，并将该点标记为VISITED，那么一切都和BFS一样。
得到最短路径后，re-run你的程序，保持一个物体在当前点是垂直还是水平的状态，模拟你在图像上的移动。仅在必要时添加转弯，您将获得添加转弯的结果。