曼哈顿距离 & 切比雪夫距离

两者可以相互转化来优化解法。

---

给出二维平面的两个点 $(x_1, y_1),(x_2,y_2)$。

曼哈顿距离

$dis=|x_1-x_2|+|y_1+y_2|$

切比雪夫距离

$dis = max{( |x_1-x_2| , |y_1+y_2| )}$

转化

二维平面把一个坐标系的曼哈顿距离转化为切比雪夫距离，则将每一个点的 $(x,y)$ 转化为 $(x+y,x-y)$ 或者 $(x-y,x+y)$。

二维平面把一个坐标系的切比雪夫距离转化为曼哈顿距离，则将每一个点的 $(x,y)$ 转化为 $(\frac{x+y}{2},\frac{x-y}{2})$ 或者 $(\frac{x-y}{2},\frac{x+y}{2})$。