如何在連續的二維矩陣中查找曼哈頓距離？

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, c

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