有一个正方形格子障碍 。 网格上，有一类的两个成员Person 。 他们面临着一定的方向（上，右，左或向下）。 每个人都有一定的能量。 使得人转动或使它们移动消耗能量（消耗转动1个能量单元，移动消耗能量5个单位）。
我的目标是让他们移动尽可能靠近彼此相邻（表示为曼哈顿距离），能源消耗尽可能少的量。 请记住，有对电网的障碍。
我会怎么做呢？
Answer 1:
我会用一个广度优先搜索和计数最小的能量值达到每平方米。 当玩家见面会终止或者有没有留下更多的能量。
Answer 2:
我会做出假设，后来将其删除。
假设格比1000×1000小，你不能能量用完..：
假设他们不能达到对方：为PERSON1，PERSON2，找到各自的到达地点，R1，R2的套。
（使用宽度例如第一搜索）
排序R1和R2由x值。
现在，经过R1和R2找到一对彼此最靠近的点。 提示：我们整理了两个数组，所以我们知道什么时候点都在他们的x坐标方面密切。 我们从来没有去更远的x坐标比目前发现的最小的。
假设他们能达到对方：从PERSON1使用BFS，直到你找到PERSON2并记录路径
如果使用BFS找到的路径不需要转弯，那么这是解决方案，
除此以外：
创建网格的4份（称他们为右格，左格，上格，下网格）。
规则是，你只能在左侧网格如果你是向左移动，你只能在正确的网格如果你向右移动，等转了，你必须从一个网格移动到另一个（使用能源）。
创建这个结构，然后使用BFS。
例：
现在，左格假设你向左移动，使创建，每一个点连接到点在其左侧与能量的向前移动量左格图。
在左 - 网格时唯一的其他选择是移动到上格或向下栅（它使用1个能量），因此从连接起来网格对应的格点和左格栅等
现在，您已经构建了图形，简单的使用广度优先重新搜索。
我建议你使用蟒蛇NetworkX，也只会是大约20行代码。
确保如果在路上的障碍不连接广场。
祝好运。
文章来源: Shortest Path, Least Turns Algorithm
