有一个带有障碍物的方形网格。在那个网格上，一个类有两个成员Person。他们面向某个方向（上、右、左或下）。每个人都有一定的能量。使人转动或移动会消耗能量（转动消耗 1 个能量单位，移动消耗 5 个能量单位）。
我的目标是让它们尽可能靠近彼此移动（表示为曼哈顿距离），尽可能消耗最少的能量。请记住，网格上有障碍物。
我该怎么做？
问问题
1455 次
2 回答
0
我会做出假设并稍后删除它们。
假设网格小于 1000x1000 并且您不能耗尽能量..：
假设他们不能互相到达：对于 Person1,Person2，找到他们各自的可达点集 R1,R2。
（以广度优先搜索为例）
按 x 值对 R1 和 R2 进行排序。
现在通过 R1 和 R2 找到最接近的点对。提示：我们对这两个数组进行了排序，这样我们就可以知道点的 x 坐标何时接近。我们在 x 坐标上的距离永远不必比当前找到的最小值更远。
假设他们可以互相到达：从 person1 使用 BFS，直到找到 person2 并记录路径
如果使用 BFS 找到的路径不需要转弯，那么这就是解决方案，
否则：
创建网格的 4 个副本（称它们为右网格、左网格、上网格、下网格）。
规则是，如果您向左移动，您只能在左侧网格中，如果您向右移动，您只能在右侧网格中，等等。要转弯，您必须从一个网格移动到另一个网格（使用能量）。
创建此结构，然后使用 BFS。
例子：
现在左侧网格假设您正在向左移动，因此从左侧网格创建一个图形，其中每个点都连接到其左侧的点，并带有向前移动的能量。
在左网格中唯一的其他选择是移动到上网格或下网格（使用1能量），因此连接上网格和左网格等的相应网格点。
现在您已经构建了图表，只需再次使用广度优先搜索。
我建议你使用 pythons NetworkX，它只有大约 20 行代码。
如果路上有障碍物，请确保不要连接方块。
祝你好运。
于 2012-04-26T08:02:22.547 回答
0
我会使用广度优先搜索并计算到达每个方格的最小能量值。当玩家相遇或没有更多能量时，它将终止。
于 2012-04-26T07:48:52.443 回答