笛卡尔平面中任意两点之间的最小曼哈顿距离是各自 X 轴和 Y 轴的绝对差之和。就像，如果我们有两个点 (X,Y) 和 (U,V)，那么距离将是：ABS(XU) + ABS(YV)。现在，我应该如何确定仅平行于坐标轴移动的几对点之间的最小距离，以便不需要在所选路径中访问某些给定点。我需要一个非常有效的算法，因为避免点的数量可以达到 10000，而查询数量的范围相同。点的坐标将小于 ABS(50000)。一开始我会得到一组要避免的点，所以我可能会使用一些离线算法和/或预计算。
例如，(0,0) 和 (1,1) 之间的曼哈顿距离是 2 从路径 (0,0)->(1,0)->(1,1) 或 (0,0)- >(0,1)->(1,1)。但是，如果我们的条件是 (1,0) 和 (0,1) 不能被访问，则最小距离增加到 6。这样的一条路径将是：(0,0)->(0,-1 )->(1,-1)->(2,-1)->(2,0)->(2,1)->(1,1)。
这个问题可以通过广度优先搜索或深度优先搜索来解决，其中广度优先搜索是标准方法。您也可以使用 A* 算法，它在实践中可能会给出更好的结果，但理论上（最坏的情况）并不比 BFS 好。
这是可以证明的，因为您的问题简化为解决迷宫问题。显然，您可以有如此多的障碍，以至于网格实际上变成了迷宫。众所周知，BFS 或 DFS 是解决迷宫的唯一方法。有关更多信息，请参阅迷宫求解算法（维基百科）。
我的最终建议：使用 A* 算法并希望最好。
您不了解此处的解决方案，或者我们不了解问题：
1）你有一个笛卡尔平面。因此，每个节点恰好有 4 个相邻节点，由 x+/-1、y+/-1 给出（忽略边）
2）做一个BFS（或DFS，A *）。您只能遍历 x/y +/- 1。预先存储 10000 个障碍物，然后检查节点 x/y +/-1 是否可按需访问。你不需要一个真正的图形对象
如果太慢，你说可以离线计算——10^10只需要1.25GB来存储索引障碍物查找表。让算法运行？
我哪里错了？