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

#алгоритм

Необходимо найти все возможные варианты покрытия 

Уголки только такого типа (3 квадрата):







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

Пример площади для заполнения:



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

Ответы

Ответ 1

Эффективное решение этой задачи использует динамику по профилю (и радуйтесь что не
по рваному краю). Пример тут 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;i