Я сталкивался с этимпроблема.

который просит подсчитать количество способов, которыми шаблон блокировки определенной длины может быть сделан в сетке 4x3 и следует правилам.там могут быть некоторые из точек не должны быть включены в путь

Допустимый шаблон имеет следующие свойства:

Образец может быть представлен с использованием последовательности точек, к которой он касается впервые (в том же порядке рисования рисунка), узор, идущий от (1,1) до (2,2), не совпадает с рисунком переходя от (2,2) к (1,1).

Для каждых двух последовательных точек A и B в представлении шаблона, если отрезок прямой, соединяющий A и B, проходит через некоторые другие точки, эти точки также должны быть в последовательности и предшествовать A и B, в противном случае шаблон будет недействительным. Например, представление шаблона, которое начинается с (3,1), затем (1,3), является недопустимым, поскольку сегмент проходит через (2,2), который не отображался в представлении шаблона до (3,1), и является правильным представление для этой модели (3,1) (2,2) (1,3). Но закономерность (2,2) (3,2) (3,1) (1,3) справедлива, потому что (2,2) появился раньше (3,1).

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

Длина шаблона - это сумма манхэттенских расстояний между каждыми двумя последовательными точками в представлении шаблона. Манхэттенское расстояние между двумя точками (X1, Y1) и (X2, Y2) равно | X1 - X2 | + | Y1 - Y2 | (где | X | означает абсолютное значение X).

Шаблон должен касаться как минимум двух точек

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

Есть ли способ рассчитать его в математическом уравнении или есть лучший алгоритм для этого?

ОБНОВИТЬ: вот что я сделал, это дает неправильные ответы! Я думаю, что проблема вisOk функция!notAllowed является глобальной битовой маской недопустимых точек.

bool isOk(int i, int j, int di,int dj, ll visited){
    int mini = (i<di)?i:di;
    int minj = (j<dj)?j:dj;

    if(abs(i-di) == 2 && abs(j-dj) == 2 && !getbit(visited, mini+1, minj+1) )
        return false;
    if(di == i && abs(j - dj) == 2 && !getbit(visited, i,minj+1) )
        return false;
    if(di == i && abs(j-dj) == 3 && (!getbit(visited, i,1) || !getbit(visited, i,2)) )
        return false;
    if(dj == j && abs(i - di) == 2 && !getbit(visited, 1,j) )
        return false;

    return true;
}

int f(int i, int j, ll visited, int l){
    if(l > L) return 0;
    short& res = dp[i][j][visited][l];
    if(res != -1) return res;
    res = 0;
    if(l == L) return ++res;

    for(int di=0 ; di<gN ; ++di){
        for(int dj=0 ; dj<gM ; ++dj){
            if( getbit(notAllowed, di, dj) || getbit(visited, di, dj) || !isOk(i,j, di,dj,  visited) )
                continue;
            res += f(di, dj, setbit(visited, di, dj), l+dist(i,j , di,dj));
        }
    }
    return res;
}