编程竞赛问题：计数多胺

Question

请看我自己的答案，我想我做到了！

你好

编程竞赛的一个示例问题是编写一个程序，以找出在给定数量的宝石下可能有多少个多米诺骨牌。

因此，对于两块石头（n = 2），只有一个多米诺骨牌：

XX

您可能会认为这是第二种解决方案：

X
X

但事实并非如此。如果可以旋转多义字，它们并不是唯一的。

因此，对于4个石头（n = 4），有7个解决方案：

X
X   XX   X    X     X   X
X   X    XX   X    XX   XX   XX
X   X    X    XX   X     X   XX

该应用程序必须能够找到解决方案 1 <= n <=10

PS：不允许在Wikipedia上使用多氨基酸列表；）

编辑：当然，问题是：如何在Java，C / C ++，C＃中做到这一点

我用Java启动了这个项目。但是后来我不得不承认我不知道如何使用有效的算法来构建多米诺骨牌。

这是我到目前为止的内容：

import java.util.ArrayList;
import java.util.List;


public class Main
{

    private int countPolyminos(int n)
    {
        hashes.clear();
        count = 0;
        boolean[][] matrix = new boolean[n][n];
        createPolyominos(matrix, n);
        return count;
    }

    private List<Integer> hashes = new ArrayList<Integer>();
    private int count;

    private void createPolyominos(boolean[][] matrix, int n)
    {
        if (n == 0)
        {
            boolean[][] cropped = cropMatrix(matrix); 
            int hash = hashMatrixOrientationIndependent(matrix);
            if (!hashes.contains(hash))
            {
                count++;
                hashes.add(hash);
            }
            return;
        }
    // Here is the real trouble!!
    // Then here something like; createPolyominos(matrix, n-1);
    // But, we need to keep in mind that the polyominos can have ramifications
    }

    public boolean[][] copy(boolean[][] matrix)
    {
        boolean[][] b = new boolean[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; ++i)
        {
            System.arraycopy(matrix[i], 0, b, 0, matrix[i].length);
        }
        return b;
    }

    public boolean[][] cropMatrix(boolean[][] matrix)
    {
        int l = 0, t = 0, r = 0, b = 0;
        // Left
        left: for (int x = 0; x < matrix.length; ++x)
        {
            for (int y = 0; y < matrix[x].length; ++y)
            {
                if (matrix[x][y])
                {
                    break left;
                }
            }
            l++;
        }
        // Right
        right: for (int x = matrix.length - 1; x >= 0; --x)
        {
            for (int y = 0; y < matrix[x].length; ++y)
            {
                if (matrix[x][y])
                {
                    break right;
                }
            }
            r++;
        }
        // Top
        top: for (int y = 0; y < matrix[0].length; ++y)
        {
            for (int x = 0; x < matrix.length; ++x)
            {
                if (matrix[x][y])
                {
                    break top;
                }
            }
            t++;
        }
        // Bottom
        bottom: for (int y = matrix[0].length; y >= 0; --y)
        {
            for (int x = 0; x < matrix.length; ++x)
            {
                if (matrix[x][y])
                {
                    break bottom;
                }
            }
            b++;
        }

        // Perform the real crop
        boolean[][] cropped = new boolean[matrix.length - l - r][matrix[0].length - t - b];
        for (int x = l; x < matrix.length - r; ++x)
        {
            System.arraycopy(matrix[x - l], t, cropped, 0, matrix[x].length - t - b);
        }
        return cropped;
    }

    public int hashMatrix(boolean[][] matrix)
    {
        int hash = 0;
        for (int x = 0; x < matrix.length; ++x)
        {
            for (int y = 0; y < matrix[x].length; ++y)
            {
                hash += matrix[x][y] ? (((x + 7) << 4) * ((y + 3) << 6) * 31) : ((((x+5) << 9) * (((y + x) + 18) << 7) * 53));
            }
        }
        return hash;
    }

    public int hashMatrixOrientationIndependent(boolean[][] matrix)
    {
        int hash = 0;
        hash += hashMatrix(matrix);
        for (int i = 0; i < 3; ++i)
        {
            matrix = rotateMatrixLeft(matrix);
            hash += hashMatrix(matrix);
        }
        return hash;
    }

    public boolean[][] rotateMatrixRight(boolean[][] matrix)
    {
        /* W and H are already swapped */
        int w = matrix.length;
        int h = matrix[0].length;
        boolean[][] ret = new boolean[h][w];
        for (int i = 0; i < h; ++i)
        {
            for (int j = 0; j < w; ++j)
            {
                ret[i][j] = matrix[w - j - 1][i];
            }
        }
        return ret;
    }

    public boolean[][] rotateMatrixLeft(boolean[][] matrix)
    {
        /* W and H are already swapped */
        int w = matrix.length;
        int h = matrix[0].length;
        boolean[][] ret = new boolean[h][w];
        for (int i = 0; i < h; ++i)
        {
            for (int j = 0; j < w; ++j)
            {
                ret[i][j] = matrix[j][h - i - 1];
            }
        }
        return ret;
    }

}

Answer 1

刚刚在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