Имеется слой кирпичной кладки размером 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("Нет решения!");
