матрица - кирпичи

[Icekream]

Поджалуйста, помогите с решением задачи. Вот условие:"Стена для рекламных щитов из М рядов по N одинаковых кирпичей в каждом. Каждый последующий ряд смещён относительно предыдущего на 1/2 кирпича. Четные ряды сверху смещаются влево, а нечётные вправо. конфигурация из кирпичей является устойчивой, если каждый кирпич опирается по крайней мере, на один кирпич в нижележащем ряду. Очевидно, что из заданной конструкции можно удалить некоторые кирпичи без потери её устойчивости.
Требуется:
Написать программу, которая по заданным числам M и N (0<M, n<1000) находит конструкцию, получающуюся из исходной путём удаления, по возможности максимального количества кирпичей, чтобы верхний ряд остался без изменений, а конструкция не потеряла устойчивость." Надо решить с помощью режима CRT a не GRAPH.Это срочно! Заранее спасибо.

[Abstraction]

Что должно являться выходом программы? В каком виде должна быть "конструкция"?

[Icekream]

входные данные: кол-во столбцов и строк,
выходные данные выводится кол-во оставшихся чисел(кирпичей). Удаляемые числа равны нулю
каждая строка начинается с единицы и далее идёт по порядку
вот пример того что должно получиться:
После ввода данных:
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
Полученная матрица:
1 2 3 4 5
1 0 3 0 5
2 0 4 5
2 0 4 5

[Icekream]

только каждая матрица идёт в шахматном порядке, как кирпичи

[Icekream]

Первая матрица:
1 2 3 4 5
_1 2 3 4 5
1 2 3 4 5
_1 2 3 4 5
Полученная матрица:
1 2 3 4 5
_1 0 3 0 5
__2 0 4 5
___2 0 4 5
Только без подчёркиваний

[Abstraction]

Ответ в примере неправильный. Удалено шесть кирпичей, можно восемь.

1 2 3 4 5
 1 2 0 4 0
0 2 0 4 0
 0 2 3 0 0

Что-то общую логику нащупать не получается. Значит, пускаем в ход граф выбора.
1) Верхний ряд должен остаться на месте - это не обсуждается.
2) Для следующего вниз ряда, при данной конфигурации предыдущего есть конечное множество минимальных (т.е. таких, из которых нельзя вынуть кирпич) комбинаций, его поддерживающих. Для любой неминимальной комбинации ряда, стену с очевидностью можно улучшить. Минимальные комбинации можно пока найти простым перебором комбинаций (для каждой - вначале проверка, поддерживает ли она вышележащий ряд, если да - то набор попыток убрать имеющиеся кирпичи), а на досуге придумать способ получше.
3) Начиная с верхнего ряда как отправной точки, мы строим "Фронт". "Фронт" состоит из множества "частичных вариантов"; "частичный вариант" - это карта некоторого количества верхних слоёв стены и "вес". Изначально "фронт" состоит из одного варианта "заполненный верхний ряд", с "весом" N.
4) На каждом шаге мы перебираем фронт. Нам нужен элемент, у которого "вес" минимален. Если этот вариант дошёл донизу, он и есть решение. Если нет, мы убираем этот вариант из "фронта", строим все возможные варианты ряда ниже, и каждый раз добавляем во "фронт" текущий вариант с таким присоединённым нижним рядом и "весом", равным "весу" исходного элемента, плюс количество кирпичей в присоединённом ряду и минус один. Такой анализ займёт конечное время и даст в результате оптимальный вариант.

Обратите внимание, что под словом "множество" понималась структура данных, неспособная содержать два одинаковых элемента. Если реализовывать её списком, то при добавлении во "фронт" новых вариантов, необходимо проверять, не лежит ли уже там такой.

[Icekream]

А как должен выглядеть листинг программы?

[Abstraction]

По всей видимости, должна быть создана структура(запись) "частичный вариант", должна быть доступна динамическая структура "список" или "множество", наверное, отдельные подпрограммы для поиска решения и вывода "частичного варианта" на экран (вторая может здорово помочь при отладке, среди прочего)...

Как это написать на Pascal? Хороший вопрос; надеюсь, кто-нибудь ответит...

[Icekream]

Спасибо за помощь, так как вы подали мне идею))