瓦片的成对匹配

Question

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

我们有1000个瓷砖，其中每个瓷砖都是一个3x3的矩阵。矩阵中的每个单元格都有一个从0到9的整数值，表示该单元格的高程。问题是要找出最大数量的瓷砖对，使它们完美地契合在一起。可以旋转瓷砖以适应其它瓷砖。通过“完美契合”，指的是对于瓷砖A和瓷砖B:

A[i]+B[i]=const (i从0到8)

我想到的解决方法是，为每个瓷砖维护一个哈希值。然后，我会找到可能适合的瓷砖组合，并在哈希表中查找。

例如，对于下面的瓷砖：

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添加到最小元素）。 因此，我将得到两个可能的瓷砖组合，我会在表格中查找它们。

但是这种方法过于贪心，并且不能给出所需的答案。同时，我也无法想出一个适当的哈希函数，该函数将考虑所有可能的旋转方式。

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

我确信有一个暴力解决此问题的方法，但实际上我想知道是否存在与“ pairwise equal to k”问题相同的可行解决方案。

- Naman Choradia

---

有没有一个问题，它只需要检查所有可能的配对就能得到解决？如果没有，为什么不使用它呢？ - kraskevich

Answer 1

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

词典式排序由以下小于运算符定义：

给定两个矩阵M1，M2，如果M1[1]为正，则定义M1'为M1，否则为-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]等等，则M1<M2。

1. 从矩阵的每个元素中减去中间元素，即 A'[5] = A[5] 且 A'[i] = A[i] - A[5]。如果对于 i!=5，有 A'[i] + B'[i] = 0，则 A' 与 B' 匹配，高程为 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) 的所有矩阵对。如果一对矩阵匹配，则使用字典检查这两个矩阵是否是同一个原始矩阵的旋转，然后计算该对的高程。

- Angela Pretorius

Answer 2

不确定这是否是最有效的方法，但它肯定有效。

我会这样做：

1. 遍历所有瓷砖并检查每个瓷砖的最大值和最小值，并将其保存在不同的数组中。
2. 检查所有可能的配对。
   1. 如果 min(A) + max(B) == min(B) + max(A)，则检查 B 的某些旋转是否完全适合于 A。 如果是，则将 1 添加到计数器中。
   2. 否则，它不适合，因此您可以跳过此对的检查。

注意： 保存每个瓷砖的最大值和最小值的原因是它可能为我们节省不必要的计算和检查旋转，因为在 O(1) 中我们可以检查它是否适合。

- A. Sarid

---

在最坏的情况下，每对瓷砖可能都符合第一个条件。 - Naman Choradia

@NamanChoradia 是的，那是最坏的情况。但你仍然需要检查所有的对，所以这种方法可能会为你节省一些不必要的计算。在这里有一个权衡，你也可以实现暴力解决方案来检查所有的对。 - A. Sarid