曼哈顿距离 与 切比雪夫—简介和应用

xiaoxiao2025-04-15  11

定义两点(x1,y1),(x2,y2)的曼哈顿距离 定义两点(x1,y1),(x2,y2)的切比雪夫距离

切比雪夫与曼哈顿距离可以互相转化。 一个点曼哈顿距离中的点,用切比雪夫距离计算时用。 一个点切比雪夫距离中的点,用曼哈顿距离计算时用。

这有什么用呢? 在坐标系中画出来,可以发现距离(0,0)曼哈顿距离为1的点呈一个菱形(其实是正方形旋转135°(45°)),切比雪夫距离为1的呈正方形。 曼哈顿转切比雪夫:一般来说一个正方形状更便于用各类数据结构来维护。(例:洛谷4648 [IOI2007] pairs 动物对数 ) 切比雪夫转曼哈顿:一般是便于统计距离和。(例:3964 [TJOI2013]松鼠聚会)

转载请注明原文地址: https://www.6miu.com/read-5028356.html

最新回复(0)