Алгоритм покрытия площади уголками

Необходимо найти все возможные варианты покрытия
Уголки только такого типа (3 квадрата):


Площадь которую нужно покрыть может быть любым прямоугольником m на n клеток без одной произвольной клетки (с условием, что хотя бы один вариант покрытия имеется).
Пример площади для заполнения:

Площадь, которую необходимо покрыть, имеет габариты m+n не больше 20 и ограничение по времени примерно 1,5-2 секунды, поэтому перебор в лоб не подходит

Ответ

Эффективное решение этой задачи использует динамику по профилю (и радуйтесь что не по рваному краю). Пример тут http://e-maxx.ru/algo/profile_dynamics но нужно немного доработать.
Однако ограничения не больше 20 сумма очень маленькие, поэтому можно сделать в лоб.
#include using namespace std;
const int N = 8; const int M = 8; char pos[N][M];
int rec(int x,int y, int d){ Omega++; if (y == M-1){ int s = 0; for (int i=0;iint main() { cout << rec(0,0,0)<По коду всё просто. Мы будем пытаться заполнить самую левую нижнюю (или как вам удобнее представлять порядок операций) пустую клетку. Если всего 5 вариантов что с ней делать. Перебираем рекурсивно каждый из них.
P.S. чтобы уложиться в 1 секунду нужно добавить любую меморизацию (или убрать рекурсию и переписать на циклы). Это нужно, т.к. взять любой прямоугольник 2*3 и там будет 2 способа. Рассматривать их отдельно не имеет смысла, но сильно замедляет работу. Без этого 10 на 10 будет работать порядка 8 секунд.