伦敦 伦敦00:00:00 纽约 纽约00:00:00 东京 东京00:00:00 北京 北京00:00:00

400-668-6666

切比雪夫

当前位置:主页 > 切比雪夫 >
切比雪夫

【总结】曼哈顿距离转切比雪夫距离

  如果我们需要得到得到到一个点的距离小于等于K的点的信息呢。这些点构成的不在是边也坐标轴平行的矩形,而是一个对角线与坐标轴平行的菱形。

  可以通过转化,使得整个坐标轴旋转45,然后我们菱形变成了方方正正的矩形,又可以用而二维树状数组或者直接用前缀和来得到矩形区间信息。

  对于每一竖,我们得到(x,0)对应的(x,n-x+1),然后向上一个个移动,等效于向右上一个一个移动。

  那么根本不用记公式(虽然公式不难)。切比雪夫转曼哈顿的话,也只需要一个一个转就行了。不好处理边界的话,可以每个点的横纵坐标都加一个值,防止越界。


点击次数:  更新时间:2020-10-01 05:59   【打印此页】  【关闭
http://juegosamenos.com/qiebixuefu/77/