切比雪夫距离是什么呢? 假设有两个点,a(x,y),b(m,n) 那么这两个点的切比雪夫距离就是max(|x-m|,|y-n|)
然而它有什么卵用吗?我也不知道
然而它可以转化为曼哈顿距离,这就非常6了.用了一个非常神奇的思想.
我们把坐标系顺时针旋转45°,这个点到原点的距离是固定的,然后我们用和角公式,这个点的坐标即为(sin45°*(x-y),sin45°*(x+y)).然后我们乘上sqrt(2);然后两个点的切比雪夫距离就是这种情形下的曼哈顿距离除以2.(中间有个非常麻烦的分类讨论...就不写了,完全版可以看这里:http://blog.csdn.net/dgq8211/article/details/7796711
那么我们就可以乱搞了!