Задача о стене

[Svejk]

Здравствуйте, подскажите пожалуйста идею алгоритма для следующей задачи:
Существует схема произвольной стены (с отверстиями, неустойчивая короче любая) из составленная из квадратов. Схема передается в формате матрицы из 1 и 0, где 1 - есть кирпич, 0 - нет. Также задан набор блоков высотой и шириной от 1 до 8 единиц. Необходимо определить возможно ли собрать заданную стену из заданного набора блоков (не обязательно использовать все блоки), при этом блоки можно ставить как горизонтально, так и вертикально.

[Poma][a]

Я за перебор всех и вся..
А лучше ничего придумать не могу (пока(надеюсь))

[rrrFer]

Думал стену представлять в виде графа со степенью вершин 4, но профита это не даст по-ходу.

Но вот сходу, я бы выбрал все возможные наборы блоков из которых потенциально можно составить такую стену, а потом уже анализировал наборы.
Очевидно, что сложность генерации наборов не выше сложности алгоритма укладки блоков.
Но алгоритм решения задачи тогда будет выглядеть как <генерация наборов> + <укладка наборов>.
Т.е. на асимптотическую сложность генерация негативного влияния не окажет.

Генерация всех возможных наборов.
Если в стене N кирпичей, то и в блоках из которых ее можно построить тоже должно быть N кирпичей.

Суть в том, что генерация не учитывает форму. Все блоки имеют размер от 1 до 64. Надо создать массив из 64 элементов и раскидать по нему блоки.

Алгоритм выдаст что-то типа 1+22+35, 22+36, ... (если в исходной стене имеется 58 кирпичей). В сумме участвуют размеры блоков, а не сами блоки).

Если размер массива размера блоков постоянен то и количество наборов ограничено (тоже константно), значит по памяти алгоритм генерации будет иметь константную сложность.

Алгоритм укладки наборов должен распределить все наборы блоков по стене. Очевидно, что его сложность - это <количество наборов> * <сложность укладки набора>.

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

Но это уже гораздо более простая задача, потому что ВСЕ БЛОКИ НАБОРА ДОЛЖНЫ БЫТЬ ИСПОЛЬЗОВАНЫ. (это в корне отличает новую задачу от исходной).

[Utkin]

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

[rrrFer]

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

Дак все кирпичи одного размера.

Вопрос в том, что

110
110
100

Можно разбить на (1111), (11) ИЛИ (11), (11), (1) ИЛИ ((11),(11)), (1)

Возможны и более хитрые варианты, например

00100
11110
00111
01111

Тут может быть сходу k*k вариантов разделения, поэтому это не канает.
Выше я описал как упростить задачу, но как добить ее до конца я не думал (и не буду скорее всего).

[8Observer8]

Клёвая задача. Я хотел сделать минимальный частный случай, но даже он не так прост. Вот мои первые размышления

Если я правильно понял, минимальная стена - это 8x8 квадратиков (кирпичей). Это и есть минимальный частный случай

Для этого случая пользователь вводит число блоков и размеры каждого блока, которые могут быть: 1x1, 2x3, 1x8, 8x8 и т.д. Минимальное количество блоков - один, то есть 8x8 кирпичей, а максимальное - 64 блоков с размерами 1x1 (блок равен кирпичу)

К примеру, может быть такая ситуация, пользователь вводит:

Количество блоков: 5

Размер 1-ого блока: 1x8
Размер 2-ого блока: 2x4
Размер 3-ого блока: 2x4
Размер 4-ого блока: 5x4
Размер 5-ого блока: 5x4

Ответ: стену можно построить без дыр

Прикрепил иллюстрацию

Вот бы написать функцию, которая бы принимала размеры матрицы и количество блоков, а возвращала бы массивы всевозможных комбинаций размеров блоков. Имея эти массивы, можно было бы найти среди них тот массив с размерами, который ввёл пользователь. Либо тот массив, который включается в массив введённый пользователем. Если нет среди этих массив того, который включается в массив пользователя целиком, то построить стену без дыр нельзя

[rrrFer]

Если я правильно понял, минимальная стена - это 8x8 квадратиков (кирпичей).

Интересно из какой фразы ты это "понял"?

Ответ: стену можно построить без дыр

Вопрос "можно ли строить стену без дыр" никто не ставил.

Перечитай еще раз задачу.

[Poma][a]

Также задан набор блоков высотой и шириной от 1 до 8 единиц.

Отсюда

А разбивать.. Чейто я не верю, что это можно делать хорошо

[8Observer8]

Из фразы, что "задан набор блоков высотой и шириной от 1 до 8 единиц"

[rrrFer]

Из фразы, что "задан набор блоков высотой и шириной от 1 до 8 единиц"

Ну задан набор блоков, а причем тут "минимальный размер стены"?