感觉我是全世界最后一个会这个东西的。
三种常见的距离表示方法是欧几里得距离、曼哈顿距离、切比雪夫距离。
-
欧几里得距离：\(dis(i,j)=\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}\)，最常用的距离表示法，适合在坐标系中使用。
-
曼哈顿距离：\(dis(i,j)=|x_i-x_j|+|y_i-y_j|\)，适合在网格图中使用。
-
切比雪夫距离：\(dis(i,j)=\max(|x_i-x_j|,|y_i-y_j|)\)，适合在八联通的图中使用。
我们不关注欧几里得距离，考虑一下曼哈顿和切比雪夫距离如何转换。
对于 \(A(x_1,y_1)\) 和 \(B(x_2,y_2)\)，其曼哈顿距离为 \(|x_1-x_2|+|y_1-y_2|\)。去掉绝对值号：
\[dis(A,B)=\max(x_1-x_2+y_1-y_2,x_1-x_2-y_1+y_2,-x_1+x_2+y_1-y_2,-x_1+x_2-y_1+y_2) \]由于切比雪夫距离是在 \(\max\) 中套绝对值，考虑把上面的式子变成 \(\max\) 套绝对值。
\[dis(A,B)=\max(|(x_1+)|,||) \] 标签：曼哈顿,max,比雪夫,距离,与切,绝对值,dis From： https://www.cnblogs.com/BYR-KKK/p/18165447