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

Имеется слой кирпичной кладки размером 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; }

Ответ

Итак, рассмотрим всевозможные участки 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("Нет решения!");