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

本文只讨论二维空间中的这两种距离。

定义

切比雪夫距离

有 $A(x_1,y_1)$、$B(x_2,y_2)$，那么切比雪夫距离定义为 $\max\{|x_2-x_1|,|y_2-y_1|\}$

一般模型：棋盘上或者在图中一个点到另外相邻八个点的距离为 $1$。

曼哈顿距离

二维空间内，两个点之间的曼哈顿距离为它们横坐标之差的绝对值与纵坐标之差的绝对值之和。

即 $A(x_1,y_1)$、$B(x_2,y_2)$ 那么 $|AB|=|x_2-x_1|+|y_2-y_1|$

一般模型：网格图中从一个点走向另一个点的最短距离。

两者的相互转化

$\begin{aligned} |x_2-x_1|+|y_2-y_1| &= \max\{x_2-x_1+y_2-y_1,x_2-x_1+y_1-y_2,x_1-x_2+y_2-y_1,x_1-x_2+y_1-y_2\} \\ &= \max\{|(x_2+y_2)-(x_1+y_1)|,|(x_2-y_2)-(x_1-y_1)|\} \end{aligned}$

曼哈顿意义下的点 $(x,y)$ <=> 切比雪夫意义下的点 $(x+y,x-y)$

切比雪夫意义下的点 $(x,y)$ <=> 曼哈顿意义下的点 $(\frac{x+y}{2},\frac{x-y}{2})$

例题