瓷砖的成对匹配

Question

最近在编码比赛中,我遇到了这个问题.

我们有1000个瓷砖,每个瓷砖是3x3矩阵.矩阵中的每个单元格具有0到9的整数值,表示单元格的高程.问题是找到最大的瓷砖对,使它们完美贴合.可以旋转瓷砖以适合.通过装配它意味着用于瓷砖A和瓷砖B.

对于i = 0到8,A [i] + B [i] = const

我认为这个问题的方法是我可以保持对应于每个tile的哈希值.然后我会找到可能适合的瓦片组合,并在哈希表中查找.

防爆.对于下面的瓷砖

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)我们可以检查它是否不合适。