Задача о кирпичной кладке

#алгоритм #любой_язык

Имеется слой кирпичной кладки размером N на M клеток. Один кирпич занимает ровно
две смежных клетки. Требуется рассчитать один из вариантов размещения кирпичей в следующем
слое кладки.

Ограничение: ни один из кирпичей нового слоя не должен полностью совпадать положением
ни с одним кирпичом предыдущего слоя.

Входные данные - матрица NxM, представляющая слой кладки, заполненная парами чисел
от 1 до NxM/2, где каждая пара чисел представляет собой один кирпич.

Пример входных данных и пример ответа:



т.е. на входе матрица:

{
    {  1,  1,  2,  2,  3,  3,  4,  4 },
    {  5,  5,  6,  6,  7,  7,  8,  8 },
    {  9,  9, 10, 10, 11, 11, 12, 12 },
    { 13, 13, 14, 14, 15, 15, 16, 16 },
}


на выходе:

{
    {  1,  2,  3,  4,  5,  6,  7,  8 },
    {  1,  2,  3,  4,  5,  6,  7,  8 },
    {  9, 10, 11, 12, 13, 14, 15, 16 },
    {  9, 10, 11, 12, 13, 14, 15, 16 },
}


Тестовый метод для проверки корректности слоя:

public bool CheckLayers(int n, int m, int[,] current, int[,] previous)
{
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (i < n - 1
                && current[i, j] == current[i + 1, j]
                && previous[i, j] == previous[i + 1, j]) return false;
            if (j < m - 1
                && current[i, j] == current[i, j + 1]
                && previous[i, j] == previous[i, j + 1]) return false;
        }
    }
    return true;
}

    

Ответы

Ответ 1

Итак, рассмотрим всевозможные участки 2х2 клетки слоя кладки:

    

Как видно, для любого участка 2х2 клетки всегда есть возможность подобрать пару кирпичей
для установки в следующем слое: т.е. если в участке один из кирпичей расположен "горизонтально"
(на самом деле весь слой горизонтальный, но для удобства обозначения я его поместил
вертикально), то берем пару "вертикальных" кирпичей, иначе берем пару "горизонтальных".
На картинках красными прямоугольниками я обозначил возможное размещение кирпичей в
следующем слое. Обратите внимание, если на выбранном участке 2х2 все клетки заняты
"половинками", т.е. нет ни одного целого кирпича, то пару кирпичей в следующем слое
можно разместить как вертикально, так и горизонтально, т.е. вышеописанный алгоритм
работает и для этого случая.

Таким образом, если оба входных значения N и M четные, то слой кладки можно разбить
на участки 2х2 клетки и заполнить их по вышеописанному алгоритму. Для четных 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("Нет решения!");


Ответ 2

Можно короче 


если одна размеренность чётная укладываем кирпичи вдоль по ней, если две можно вдоль двух
если очень надо уложить вдоль нечётной, укладываем вдоль неё все кроме последнего
кирпича, последний поперёк, следующий ряд так же (будет использоваться тот кирпич что
поперёк)
если очень надо уложить когда N и M нечётные, выбрав направление укладываем вдоль
первого ряда без последнего кирпича и дальше ряды как в предыдущем пункте, теряем одну
клетку.