距离之间的转化

Manhattan 距离、Chebyshev 距离

Manhattan 距离可以和 Chebyshev 距离互相转化。考虑两个点 P1(x1,y1),P2(x2,y2)P_1(x_1, y_1), P_2(x_2, y_2)，其曼哈顿距离为

∣x1−x2∣+∣y1−y2∣ |x_1-x_2|+|y_1-y_2|

其切比雪夫距离为

max⁡(∣x1−x2∣,∣y1−y2∣) \max(|x_1-x_2|, |y_1-y_2|)

两个点的曼哈顿距离可以等价转化为切比雪夫距离。构造两个切比雪夫点 C1(x1+y1,x1−y1),C2(x2+y2,x2−y2)C_1(x_1+y_1, x_1-y_1), C_2(x_2+y_2, x_2-y_2)，则 P1,P2P_1, P_2 的曼哈顿距离为 C1,C2C_1, C_2 的切比雪夫距离。

【例题】

License

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。