瓷磚的兩兩匹配

Question

最近在編碼競爭中，我遇到了這個問題。

我們有1000塊瓷磚，其中每塊瓷磚是3x3矩陣。 矩陣中的每個單元格都具有從0到9的整數值，這表示單元格的高程 。問題是要找到最合適的瓷磚對，例如 。瓦片可以旋轉以適應，通過配合 在它意味着對於瓦片A和瓦片乙

A [1] + B [i]於=常數對於i = 0至8

我認爲這個問題的方法是我可以維護一個對應於每個tile的散列值。然後我會發現可能的拼貼組合可能是 ，並在散列表中查找它。

Ex。對於低於

5 3 2     4 6 7       5 7 8 
4 8 9 matches with  5 1 0 for const = 9 & with 6 2 1 for const=10 
1 4 5     8 5 4       9 6 5 

瓦片該圖塊的「const的」將範圍從9（添加0到最大元素）至10（9添加到最小元素）。 因此，我會得到兩個可能的組合瓷磚，我會在表中查找。

但是這種方法是貪婪的，並沒有給出所需的答案，我也無法想到一個適當的散列函數，它將考慮所有可能的旋轉。

那麼如何解決這個問題是一個好方法？

我確信有一種蠻力的方式來解決這個問題，但我實際上想知道在「成對等於k」問題的線上是否存在可行的問題解決方案。

Answer 1

不知道這是否是最有效的方法，但它確實有效。

我會做的是：

1. 去了所有的瓷磚，並檢查最大和每瓦的最小值，並將其保存在不同的陣列。
2. 檢查所有可能的配對。
   1. 如果min(A) + max(B) == min(B) + max(A)那麼檢查一下B的旋轉是否完全符合A。如果是這樣，請將1添加到您的計數中。
   2. 否則，它不適合，所以你可以跳過這對檢查。

注：其原因既節約了最大和最小用於每個圖塊的是，它會爲我們節省不必要的計算和檢查旋轉爲O(1)，我們可以檢查，如果它不適合。

Answer 2

對於n = 1000，我會堅持使用O（n^2）蠻力解決方案。但是，O（n log n）算法如下所述。

的lexicographicalish順序由以下小於運算符定義：

鑑於兩個矩陣M1, M2，定義M1'爲M1如果M1[1]爲正，並且如果-M1是M1[1]負，同樣或M2' 。我們說M1<M2如果M1'[1]<M2'[1],，或者如果M1'[1] == M2'[1]和M1'[2] < M2'[2],或如果M1'[1] == M2'[1]和M1'[2] == M2'[2]和M1'[3] < M2'[3]等

1. 從的矩陣即A'[5] = A[5]和A'[i] = A[i] - A[5].元件的其餘部分則A」減去每個矩陣的中間元件如果A'[i] +B'[i] = 0爲i!=5，並且海拔爲A'[5] + B'[5].

2. 創建一個矩陣和字典數組。旋轉每個矩陣，使左上角的絕對值最小，然後將其添加到數組中。如果有多個具有相同絕對值的轉角，則複製矩陣並將兩個旋轉存儲在數組中。

   如果一個矩陣的一些旋轉與自身適應和i,j此矩陣的轉指標，添加鍵值對(i,j)和(j, i)到字典中。

3. 創建索引1,2 ...的數組S，並使用詞典形式的排序對S進行排序。

4. 代替需要爲O（n^2）操作來檢查所有可能的對矩陣，僅需要檢查所有對矩陣具有索引是S_i和S_(i+1).如果一對矩陣的配合，使用字典來檢查兩個矩陣在計算對的高程之前不是同一原始矩陣的旋轉。