砌砖问题

因此，让我们考虑砌体层的 2x2 单元的所有可能部分：

如您所见，对于 2x2 单元的任何部分，总是可以拿起几块砖安装在下一层：即 如果在该区域中，其中一个砖块是“水平”放置的（实际上整个层是水平的，但为了便于指定，我将其垂直放置），那么我们取一对“垂直”砖块，否则我们取一对“水平”的。在图片中，我用红色矩形表示了下一层可能放置的砖块。请注意，如果在选定的 2x2 区域中，所有单元格都被“一半”占据，即 没有一整块砖，那么下一层的几块砖可以垂直和水平放置，即 上述算法也适用于这种情况。

因此，如果输入值 N 和 M 都是偶数，那么砌体层可以划分为 2x2 单元的部分，并根据上述算法进行填充。对于偶数 N 和 M，解总是存在并且是微不足道的。

现在，考虑 N 或 M 为奇数的情况。需要注意的是，如果 N 和 M 同时都是奇数，那么我们不能用整数个砖块来平铺层，即 不可能有这样的输入数据，我们不考虑这种情况。

因此，砌体层的尺寸之一是奇数。考虑“宽度”M 为奇数的情况，如果“高度”N 为奇数，那么我们总是可以转置输入数据并使用相同的算法。

让我们将砌体“划分”成 2 个单元格高的“水平”条纹（高度是均匀的，所以这是可能的），并独立考虑每个条纹。对于这样的条带，我们必须至少垂直放置一个积木，并且这块积木必须在 0、2、4、...、(M-3) 或 (M-1) 垂直（如果我们有垂直砖位于具有奇数索引的垂直，那么在垂直中将至少有一个（偶数两个）具有偶数索引的垂直砖，我们将考虑它）。值得注意的是，垂直砖的左右两侧会有偶数个垂直。

那些。对于每个高度为 2 个单元格的水平条，我们查看具有偶数索引的垂直线，如果其中一个垂直线没有垂直砖，那么我们在下一层放置一个垂直砖，并填充左侧区域根据偶数 N 和 M 的算法，它的右边。如果在条带 2xM 中所有偶数垂直都被垂直砖占据，那么没有解决方案。

我无法证明算法的正确性，但我没有设法找到输入数据的反驳示例。

剩下的只是将这个算法翻译成代码。

C# 中的幼稚实现：

class Layer
{
    int[,] array;
    int n, m;
    public bool IsTransposed { get; set; } = false;
    public int N => IsTransposed ? m : n;
    public int M => IsTransposed ? n : m;

    public Layer(int[,] bricks) => (n, m, array) = (bricks.GetLength(0), bricks.GetLength(1), bricks);
    public Layer(int n, int m) : this(new int[n, m]) { }

    public int this[int row, int column]
    {
        get => IsTransposed ? array[column, row] : array[row, column];
        set => array[IsTransposed ? column : row, IsTransposed ? row : column] = value;
    }

    public Layer GenerateNext()
    {
        if (N % 2 + M % 2 == 2) return null;
        var next = new Layer(N, M);
        var index = 0;
        if (N % 2 + M % 2 == 0)
        {
            for (int row = 0; row < N; row += 2)
                for (int column = 0; column < M; column += 2)
                    Fill(row, column);
        }
        else
        {
            if (N % 2 == 1) IsTransposed = next.IsTransposed = true;
            for (int row = 0; row < N; row += 2)
            {
                bool exist = false;
                int reservedColumn = 0;
                for (int column = 0; column < M; column += 2)
                    if (this[row, column] != this[row + 1, column])
                    {
                        exist = true;
                        reservedColumn = column;
                        break;
                    }
                if (!exist) return null;
                next[row, reservedColumn] = next[row + 1, reservedColumn] = ++index;
                for (int column = 0; column < reservedColumn; column += 2)
                    Fill(row, column);
                for (int column = reservedColumn + 1; column < M; column += 2)
                    Fill(row, column);
            }
            IsTransposed = next.IsTransposed = false;
        }
        return next;

        void Fill(int r, int c)
        {
            if (this[r, c] == this[r, c + 1] ||
                this[r + 1, c] == this[r + 1, c + 1])
            {
                next[r, c] = next[r + 1, c] = ++index;
                next[r, c + 1] = next[r + 1, c + 1] = ++index;
            }
            else
            {
                next[r, c] = next[r, c + 1] = ++index;
                next[r + 1, c] = next[r + 1, c + 1] = ++index;
            }
        }
    }

    public override string ToString()
    {
        int max = this[0, 0];
        for (int row = 0; row < N; ++row)
            for (int column = 0; column < M; ++column)
                if (this[row, column] > max) max = this[row, column];
        int d = max.ToString().Length;
        var format = "{0," + d + "} ";
        var sb = new StringBuilder();
        for (int row = 0; row < N; ++row)
        {
            for (int column = 0; column < M; ++column)
                sb.AppendFormat(format, this[row, column]);
            sb.AppendLine();
        }
        return sb.ToString();
    }
}

使用示例：

int[,] bricks =
{
    {  1,  1,  2,  2,  7,  3,  4,  4 },
    {  5,  9,  6,  6,  7,  3,  8, 12 },
    {  5,  9, 10, 10, 11, 11,  8, 12 },
    { 13, 13, 14, 18, 15, 15, 16, 16 }
};
var layer = new Layer(bricks);
var nextLayer = layer.GenerateNext();
Console.WriteLine(layer);
if (nextLayer != null) Console.WriteLine(nextLayer);
else Console.WriteLine("Нет решения!");

可以更短

• 如果一个维度是偶数，我们沿着它铺砖，如果两个可以沿着两个
• 如果你真的需要沿着奇数铺设，我们将所有东西都铺设在它上面，除了最后一块砖，最后一块横着，下一行以同样的方式（将使用横着的砖）
• 如果你真的需要在 N 和 M 是奇数时铺设，选择方向，我们沿着第一行铺设，没有最后一块砖，然后像上一段一样铺设，我们失去一个单元格。