261 字
1 分钟
曼哈顿距离与切比雪夫距离
曼哈顿距离
设两个点坐标分别为 ,则这两个点的曼哈顿距离为 。
切比雪夫距离
设两个点的坐标分别为 ,则这两个点的切比雪夫距离为
这两种距离看似没有什么关系,一个是横纵坐标差之和,一个是取较大值。但是,其实他们是可以相互转化的。下面给出结论:
若 与 的曼哈顿距离为 ,则 和 的切比雪夫距离仍为 。证明是显然的,我们只需要对按照定义作差后比较就能发现两者相同。
📝 NOTE 以下给出摘自 OI Wiki 的分析方法:
设有 两个点,则他们的曼哈顿距离为:
容易发现, 的曼哈顿距离即为 的切比雪夫距离。
我们可以认为切比雪夫坐标系实际上是曼哈顿坐标系旋转 后再扩大 倍形成的。
这两种距离常常可以相互转化,对于在考虑某种距离困难的时候,不妨思考另一种距离会不会简单一些。
曼哈顿距离与切比雪夫距离
https://blog.hanyblue.com/posts/math/length/