曼哈顿距离与切比雪夫距离的转换
曼哈顿距离
定义
平面内两点坐标分别为（x1，y1），（x2，y2）
则
$$
dis = |x_1 - x_2| + |y_1 - y_2|
$$
切比雪夫距离
定义
平面内两点坐标分别为（x1，y1），（x2，y2）
则
$$
dis = \max(|x1 - x2|, |y1 - y2|)
$$
两者的关系
第一组
将一个点 ((x, y)) 的坐标变为 ((x + y, x - y)) 后，原坐标系中的曼哈顿距离 (=) 新坐标系中的切比雪夫距离 。
当然有时候为了防止数组越界，在处理 x - y 的时候，可以全部加上一个定值常数，即转换为 ((x + y, x - y + C))
第二组
将一个点 ((x, y)) 的坐标变为
$$
\left( \frac{x+y}{2},\ \frac{x-y}{2} \right)
$$
后，原坐标系中的切比雪夫距离 (=) 新坐标系中的曼哈顿距离
1. 第一组变换证明
设原两点 ( A(x_1,y_1) )、( B(x_2,y_2) )，变换后新坐标：
$$ A’(x_1+y_1,\ x_1-y_1),\quad B’(x_2+y_2,\ x_2-y_2) $$
原曼哈顿距离：
- $$ d_{\text{Manhattan}} = |x_1-x_2| + |y_1-y_2| $$
新切比雪夫距离：
- $$ d_{\text{Chebyshev}}’ = \max\left(,|(x_1+y_1)-(x_2+y_2)|,,\ |(x_1-y_1)-(x_2-y_2)|,\right) $$
化简后可证
$$
( d_{\text{Manhattan}} = d_{\text{Chebyshev}}’ )
$$
2. 第二组变换证明
变换后新坐标： $$ A’\left(\frac{x_1+y_1}{2},\ \frac{x_1-y_1}{2}\right),\quad B’\left(\frac{x_2+y_2}{2},\ \frac{x_2-y_2}{2}\right) $$
原切比雪夫距离：
- $$ d_{\text{Chebyshev}} = \max\left(,|x_1-x_2|,\ |y_1-y_2|,\right) $$
新曼哈顿距离：
- $$ d_{\text{Manhattan}}’ = \left|\frac{x_1+y_1}{2} - \frac{x_2+y_2}{2}\right| + \left|\frac{x_1-y_1}{2} - \frac{x_2-y_2}{2}\right| $$
化简后可证
$$
( d_{\text{Chebyshev}} = d_{\text{Manhattan}}’ )
$$
应用意义
这些变换可将两种距离问题相互转换，利用不同距离在算法中的优势（如曼哈顿距离计算简单、切比雪夫距离在网格问题中直观 ），简化解题。