在有障碍物的网格中找到两个最远的单元格
Find two farthest cells in a grid with obstacles
没有定义的起始单元格，如何以最有效的方式找到有障碍物（墙壁等）的网格中最远的两个单元格？
不需要是完美的结果，可以是近似值，前提是它足够好。
如果你知道怎么做，我爱你。
- 执行 8 向桶填充算法来查找死胡同。
为了最大限度地减少死端数量，首先将基数添加到队列中，然后是主要的中间基数（对角线）。还要跟踪最后一个死角，如果你发现一个新的死角离最后一个死角太近，你删除最后一个并保留新找到的死角。在大地图中，您还可以计算从死胡同到地图中心的曼哈顿距离，如果它太短，您就不要添加死胡同。
- 现在每个点到其他点只需 A*。
因为你测试了每条路径两次（p1 到 p2 然后 p2 到 p1）一旦你测试 p1 到 p2 你也可以立即注册 p2 到 p1 相同的距离将你需要做的次数减半A* 搜索。您需要进行 A* 搜索的次数可以通过 number of deadends * (number of deadends - 1) / 2.
计算得出
没有定义的起始单元格，如何以最有效的方式找到有障碍物（墙壁等）的网格中最远的两个单元格？
不需要是完美的结果，可以是近似值，前提是它足够好。
如果你知道怎么做，我爱你。
- 执行 8 向桶填充算法来查找死胡同。
为了最大限度地减少死端数量，首先将基数添加到队列中，然后是主要的中间基数（对角线）。还要跟踪最后一个死角，如果你发现一个新的死角离最后一个死角太近，你删除最后一个并保留新找到的死角。在大地图中，您还可以计算从死胡同到地图中心的曼哈顿距离，如果它太短，您就不要添加死胡同。
- 现在每个点到其他点只需 A*。
因为你测试了每条路径两次（p1 到 p2 然后 p2 到 p1）一旦你测试 p1 到 p2 你也可以立即注册 p2 到 p1 相同的距离将你需要做的次数减半A* 搜索。您需要进行 A* 搜索的次数可以通过 number of deadends * (number of deadends - 1) / 2.