algorithm - 瓦片的成对匹配

Question

最近在一次编程比赛中我遇到了这个问题。

We have a 1000 tiles where each tile is a 3x3 matrix. Each cell in the matrix has an integer value from 0 to 9 which signifies the elevation of the cell. The problem was to find the maximum pairs of tiles such that they fit in perfectly. The tiles may be rotated to fit in. By fit in it means that for tile A and tile B

A[i]+B[i]=const for i=0 to 8

我想到的解决这个问题的方法是，我可以维护一个与每个图 block 对应的哈希值。然后我会找到可能的瓷砖组合一个可能的匹配并在哈希表中查找它。

例。对于下面的磁贴

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

对于此图 block ，“const”的范围从 9(将 0 加到最大元素)到 10(将​​ 9 加到最小元素)。所以我会得到两种可能的瓷砖组合，我会在表格中查找。

但是这种方法很贪心，没有给出所需的答案，而且我也想不出一个合适的哈希函数来考虑所有可能的旋转。

那么解决这个问题的好方法是什么？

我确信有一种蛮力方法可以解决这个问题，但我实际上想知道是否存在解决“pairwise equal to k”问题的可行解决方案。 p>

Answer 1

对于 n=1000，我会坚持使用 O(n^2) 蛮力解决方案。然而，下面描述了一个 O(n log n) 算法。

字典顺序由以下小于运算符定义:

给定两个矩阵 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'[i] +B'[i] = 0，则 A' 适合 B'对于 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).如果一对矩阵拟合，则在计算这对矩阵的高程之前使用字典检查这两个矩阵是否不是同一原始矩阵的旋转。