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

Question

我有一个网格，网格有两个“ Material ”-

• 楼层
• 墙

例如:

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

在每个对象上我们可以做一些 Action ，比如 -

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

我需要创建一个函数，返回将对象从一点移动到另一点所需执行的最少操作量(我只需要操作量)。

我使用 dijkstra's algorithm 解决了这个问题, 但没有转动 Action 。

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

问题示例-

• 起点 -

• 终点

而且我需要返回我需要对一个对象执行的最少操作量。

Answer 1

将问题视为在 3D 网格中寻找最短路径，深度为 2(每种可能的状态:水平和垂直)。您必须编写禁止从一个深度移动到另一个深度的约束，例如，如果不适合这种方式，则不能垂直移动。

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