曼哈顿距离与切比雪夫距离的转换

曼哈顿距离

平面内两点坐标分别为（x1，y1），（x2，y2）

则

d i s = | x_{1} - x_{2} | + | y_{1} - y_{2} |

平面内两点坐标分别为（x1，y1），（x2，y2）

则

d i s = max (| x 1 - x 2 |, | y 1 - y 2 |)

将一个点 ((x, y)) 的坐标变为 ((x + y, x - y)) 后，原坐标系中的曼哈顿距离 (=) 新坐标系中的切比雪夫距离。

当然有时候为了防止数组越界，在处理 x - y 的时候，可以全部加上一个定值常数，即转换为 ((x + y, x - y + C))

将一个点 ((x, y)) 的坐标变为

(\frac{x + y}{2}, \frac{x - y}{2})

后，原坐标系中的切比雪夫距离 (=) 新坐标系中的曼哈顿距离

设原两点 ( A(x_1,y_1) )、( B(x_2,y_2) )，变换后新坐标：

A^{'} (x_{1} + y_{1}, x_{1} - y_{1}), B^{'} (x_{2} + y_{2}, x_{2} - y_{2})

原曼哈顿距离：
- $d_Manhattan = | x_{1} - x_{2} | + | y_{1} - y_{2} |$
新切比雪夫距离：
- $d_{Chebyshev}^{'} = max (| (x_{1} + y_{1}) - (x_{2} + y_{2}) |, | (x_{1} - y_{1}) - (x_{2} - y_{2}) |)$
化简后可证

(d_{Manhattan} = d_{Chebyshev}^{'})

变换后新坐标： $$ 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_Chebyshev = max (| x_{1} - x_{2} |, | y_{1} - y_{2} |)$
新曼哈顿距离：
- $d_{Manhattan}^{'} = | \frac{x_{1} + y_{1}}{2} - \frac{x_{2} + y_{2}}{2} | + | \frac{x_{1} - y_{1}}{2} - \frac{x_{2} - y_{2}}{2} |$
化简后可证
$(d_{Chebyshev} = d_{Manhattan}^{'})$

这些变换可将两种距离问题相互转换，利用不同距离在算法中的优势（如曼哈顿距离计算简单、切比雪夫距离在网格问题中直观），简化解题。