编程竞赛问题：计数多胺

编程竞赛问题：计数多胺

刚刚在Java中也解决了这个问题。由于所有这些似乎都存在性能问题。我也给你我的

董事会代表：

2个整数数组。1代表行，1代表列。

• 旋转：

  column[i]=row[size-(i+1)]

  ，

  row[i] = reverse(column[i])

  其中是反向的位颠倒根据尺寸（大小= 4和开头的2位取：

  rev(1100) = 0011

  ）
• 移位模块：

  row[i-1] = row[i]

  ，

  col[i]<<=1

• 检查是否设置了位：

  (row[r] & (1<<c)) > 0

• 板的唯一性： 当阵列行是唯一的时，板是唯一的。
• 董事会哈希： 数组行的 哈希 码
• ..

因此，这使所有 *** 作变得快速。他们中的许多人本来应该是

O(size²)

2D数组表示形式，而不是现在

O(size)

。

算法：

• 从大小为1的块开始
• 对于每种尺寸，从少1块石头的块开始。
• 如果有可能添加石头。检查它是否已经添加到集合中。
• 如果尚未添加。将其添加到此大小的解决方案中。
  • 将块添加到集合及其所有旋转中。（3轮，共4轮）
  • 重要的是，每次旋转后，将块尽可能向左/向左移动。
• +特殊情况：接下来的2种情况执行相同的逻辑
  • 向右移动第一个块，并在第一列中添加石头
  • 将第一个块移至底部，并在第一行中添加石头

性能：

• N=5

  ，时间：3ms

• N=10

  ，时间：58ms

• N=11

  ，时间：166ms

• N=12

  ，时间：538ms

• N=13

  ，时间：2893ms

• N=14

  ，时间：17266ms

• N=15

  ，NA（堆空间不足）

代码：https :
//github.com/Samjayyy/logicpuzzles/tree/master/polyominos