Алгоритм нарезать на квадратную матрицу матрицу

Question

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

РЕДАКТИРОВАТЬ:

Хорошо, возможно, это не ясно: у меня есть сетка элементов, которые могут иметь некоторые значения, подобные этому:

0011121

0111122

2211122

0010221

0012221

То был мой вход , и я хочу в вывод что-то вроде этого:

| 0 | 0 | 111 | 2 | 1 |

| 0 | 1 | 111 | 22 |

| 2 | 2 | 111 | 22 |

| 00 | 1 | 0 | 22 | 1 |

| 00 | 1 | 2 | 22 | 1 |

Когда каждый | X | массив, который является частью входного массива. Моя цель - минимизировать количество выходных массивов

Answer 1

Эта проблема, похоже, не имеет эффективного решения.

Рассмотрим подмножество примеров вашей проблемы, определенное следующим образом:

• Существует только 2 значения матричных элементов, скажем 0 и 1.
• Рассмотрим только матричные элементы со значением 0.
• Определите каждый матричный элемент m_ij с единичным квадратом в прямоугольной angular 2D-сетке чей нижний левый угол имеет координаты (i, n-j).
• Множество единичных квадратов SU, выбранных таким образом, должно быть «соединено» и не должно иметь «отверстий»; формально, для каждой пары квадратов единиц (m_ij, m_kl) \in SU^2: (i, j) != (k, l) существует последовательность <m_ij = m_i(0)j(0), m_i(1)j(1), ..., m_i(q)j(q) = m_kl> из q+1 единиц квадратов, такая, что (|i(r)-i(r+1)| = 1 _and_ j(r)=j(r+1)) _or_ (i(r)=i(r+1) _and_ |j(r)-j(r+1)| = 1 ); r=0...q (юнит-квадраты, смежные в последовательности, имеют одну сторону), и множество SUALL всех единиц квадраты с координатами нижнего левого угла от целых чисел минус SU также «связаны».

Разрезание матриц, допускающих эту конструкцию, на минимальное количество квадратных подматриц эквивалентно разбиению наименьшего ортогонального многоугольника SU (который является объединением всех элементов SU) в минимальное количество квадратов.

Этот пост SE.CS дает ссылки (и одно доказательство), что покажите, что эта задача является NP-полной для целых длин сторон квадратов набора листов.

Обратите внимание, что в соответствии с тем же постом разбиение на прямоугольники выполняется за полиномиальное время.

Answer 2

Некоторые подсказки могут быть полезны.

Для представления уменьшенной матрицы может быть лучше вектор, потому что он должен быть сохранен (start_x, start_y, value ... не уверен, что другая матрица очень полезна).

Шаг 1: l oop на x для n вхождений (начните с y = 0)
Шаг 2: l oop на y для / до n вхождений. В большинстве случаев здесь будет больше, чем n. (регистр m больше, чем n исключен, так как не может сделать квадрат) Хорошо, просто оставьте минимальное значение [m]
Шаг 3: отметка на векторе (start_x, start_y, value)
Повторите Шаг 1-3 с x = m до конца x
Шаг 4: Конец x, отрегулируйте y, начиная с самого левого найденного_x (вектор m-in, повторный вектор). ...
продолжайте до конца матрицы.

Нужно быть очень осторожным с тем, как сделаны границы (квадраты), чтобы включить в результат полное покрытие исходной матрицы.
Переформулировать полную исходную матрицу можно точно заново из вектора результата.
(нужно найти пробелы и поместить их в вектор, полученный из step_4)

Примечание! Это не полное решение, может быть, это то, как начать и выяснить на каждом шаге, что нужно отрегулировать.