如何在连续的二维矩阵中找到曼哈顿距离？

Question

让我们说我的矩阵是

7 1 2
3 5 6
4 8 9

目标配置按如下方式排序:

1 2 3
4 5 6
7 8 9

使用曼哈顿距离算法我可以计算"7"到目的地的距离为2步,但是矩阵是连续的,即我可以在两个方向上移动行和列,因此"7"距离右侧点只有一步之遥.

如何修改曼哈顿距离算法以反映该属性？

谢谢.

Answer 1

在通常情况下,也就是说没有环绕的网格,我们将曼哈顿距离定义i, j为r, cas

abs(r-i) + abs(c-j)

这abs意味着绝对值.

在n水平线(行)和m垂直线(列)的环绕网格中,我们可以将曼哈顿距离计算为

min(abs(r-i), n-1-abs(r-i))  +  min(abs(c-j), m-1-abs(c-j))

哪个min是至少需要两个值的函数.

这个公式背后的原因是从第一行到最后一行的距离是n-1.如果我们d在任意两行之间有直接距离,则环绕距离e是这样的值:

d + e = n-1

e = n-1 - d

现在两行之间的距离是直接距离和环绕距离的最小值.我们同样争论列之间的距离.曼哈顿距离只是行之间距离和列之间距离的总和.

请考虑以下示例,其中包含n = 8行和m = 10列.我们希望从计算曼哈顿距离(2, 7)来(5, 1).

没有环绕,曼哈顿距离是:

abs(r-i) + abs(c-j)

= abs(5-2) + abs(1-7)

= abs(3) + abs(-6)

= 3 + 6

= 9

环绕式,曼哈顿距离为:

min(abs(r-i), n-1-abs(r-i))  +  min(abs(c-j), m-1-abs(c-j))

= min(3, 7-3) + min(6, 9-6)

= min(3, 4) + min(6, 3)

= 3 + 3

= 6