Один из способов решить эту проблему рекурсивно начать с исходной сеткой черных и белых клеток, повторно определить конкретную черную сетку клетки, и попытаться покрыть (или «грызть прочь»), что ячейки сетки с куском всеми возможными способами. Например: всегда выбирайте самую нижнюю, самую правую черную ячейку сетки - то есть среди всех нижних черных ячеек в текущей подзадаче выберите самый правый.
Некоторые (на практике, большинство) места размещения части, которая покрывает выбранную ячейку, могут быть немедленно признаны недействительными, поскольку они также покрывают некоторую белую ячейку - и мы знаем, что все белые ячейки должны оставаться белыми. Если нет «хорошего» размещения любой доступной части (место размещения «хорошо», если оно покрывает выбранную ячейку и не содержит белых клеток), тогда мы можем вернуть NO для этой подзадачи: это невозможно решить. OTOH, если есть хотя бы одно «хорошее» размещение доступной части, оно может или не может привести к решению: для этого каждое такое «хорошее» место размещения создает подзадачу, в которой черные ячейки, соответствующие этой помещенной части, был удален (т. е. стал белым), а количество доступных частей только что сделанного предмета уменьшилось на единицу. Базовый случай возникает, когда черных клеток не осталось: в этом случае мы можем вернуть ДА, так как мы знаем, что можно разместить кусочки для достижения пустой сетки (в частности, это включает в себя не размещать кусочки вообще).
Этот рекурсивный подход потенциально несколько раз пересматривает некоторые подзадачи. Например, если часть исходной сетки содержит 4x2 блок черных клеток и у вас есть по крайней мере, следующие части 2-секционная доступны:
XX 2 Y 2
Y
, то вы можете заполнить этот 4x2 блок следующих способов
XXYY YXXY YYXX
XXYY YXXY YYXX
поэтому полученная подзадача (которая не имеет этого блока 4x2 и имеет 2 меньше каждого типа) будет решена 3 раза. Чтобы этого избежать, при определенных (довольно ограничительных) обстоятельствах вы можете использовать динамическое программирование сверху вниз (также известное как memoisation). Это приводит к решению каждой подзадачи не более одного раза, но (потенциально) требует хранения ответов (каждый один бит с указанием ДА или НЕТ) до все возможные подзадачи, из которых 2^(m * n) * (k_1 + 1) * (k_2 + 1) * ... * (k_t + 1), где m и n - ширина и высота сетки, а k_1, ..., k_t - числа доступных копий t разные типы штук. На практике это означает, что проблемы, превышающие примерно 5 * 5, будут нецелесообразными для решения (по крайней мере, если вы используете «очевидную» кодировку сетки, где каждая ячейка становится единичным битом целого числа, возможно, более экономичная кодировка, для которой требуется всего 2^b бит, где b - общее число изначально чёрных ячеек, а не общее количество ячеек в целом).(OTOH, если вы готовы притвориться, что существует неограниченное количество каждого типа пьесы, вам нужно всего лишь сохранить ответы 2^(m * n), потому что нам не нужно отслеживать, сколько из них Это может быть полезно в качестве быстрой первой проверки: если проблема не может быть решена даже при неограниченном количестве каждого типа предметов, то она, конечно же, не может быть решена с ограниченным числом из них.)
возможно релевантный: http://stackoverflow.com/questions/3516044/fill-arbitrary-2d-shape-with-given-set-of-rectangles –
Возможно, посмотрите на алгоритм разделения и покорения. Если вы можете найти способ представления областей, вы можете превратить его в решение динамического программирования снизу вверх. – MathBunny
Насколько я понимаю из вашего описания метода однострочного блока, что блоки нельзя вращать? – m69