algorithm - 是否有可能有一个 bool 矩阵的旋转不变标识符？

Question

假设我有一个由 1 和 0 组成的矩阵，我想要这个矩阵的“标识符”，无论矩阵旋转 90 度、180 度还是 270 度，它都具有相同的值，即 4-to -1 映射。理想情况下，此标识符应为矩阵大小的 1/4。是否可以编写执行此映射的函数？

背景:我在看this problem在 UVa 问题集上。我并不完全需要这样的功能来解决问题，但它存在似乎是合理的，并且使用它会产生更优雅的解决方案。

Answer 1

是的。您可以将原始矩阵 A 旋转为所有可能的配置 A'、A'' 和 A'''。然后，您可以使用您选择的某种排序方式对它们进行排序(只要保持一致)，选择第一个，然后使用您选择的任何哈希函数对其进行哈希处理(同样，实际的哈希函数并不重要，只要保持一致即可)。

显然，这可以通过不实际进行完整的旋转和排序来进行大量优化 - 您可以懒惰地进行比较，一旦知道哪个旋转首先排序就停止 - 但原理是相同的。