algorithm - 移动受限时查找网格中两点之间的距离

Question

网格中有多个点。

假设 (x,y) 可以在单个时间单位内从 (x-1,y+1) 到达。那么求点 (x1,y1) 到 (x2,y2) 之间距离的一般公式是什么。

说 (0,0) 到 (-2,-1) 即坐标也可以是负数。

我想不出通用公式。

Answer 1

如果我正确地理解了这个问题，并且对角线移动与“曼哈顿”移动具有相同的成本，那么在大多数情况下它比曼哈顿距离便宜——只有 x 和 y 距离的最大值是相关的:

最大(绝对值(x1 - x2)，绝对值(y1 - y2))

基本上，您以每单位 1 的成本沿对角线移动，直到到达 x2 或 y2，然后沿着网格移动。