关于曼哈顿距离和切比雪夫距离的转换和应用
看到曼哈顿距离就不难想到可以与切比雪夫距离进行转换。
切比雪夫距离：
平面上两个点（x1，y1），（x2，y2） 之间的距离为max（ |x1-x2 | , | y1 - y2 | ）.
如何转换呢？考虑把原来的坐标系旋转45°，原来的坐标（x，y）就变成了 （x+y，x - y ）
然后原图上两点的曼哈顿距离就变成了切比雪夫距离了。
在转换之后，我们就可以转化成对于两个点其中一维的差值刚好为D，另一维度为<=D
为了方便讨论，我们先假设x差值为D，
这样来讨论：
x1−x2=D
−D≤y1−y2≤D
我们固定了一维x，那么另外一维y就处于一个范围内，我们就可以快速的处理每一个点有多少与之曼哈顿距离为D的节点了。
具体实现是按照x排序，如果x相同就按照y排序。
然后我们只需要找一个点x的两个距离为D的点，x+D和 x-D，对应有多少个y之差小于等于D
查看10道真题和解析