Me encontré con estoproblema.

que pide calcular la cantidad de formas en que se puede hacer un patrón de bloqueo de una longitud específica en una cuadrícula de 4x3 y sigue las reglas.puede haber algunos de los puntos que no deben incluirse en la ruta

Un patrón válido tiene las siguientes propiedades:

Un patrón puede representarse usando la secuencia de puntos que toca por primera vez (en el mismo orden de dibujar el patrón), un patrón que va de (1,1) a (2,2) no es lo mismo que un patrón pasando de (2,2) a (1,1).

Por cada dos puntos consecutivos A y B en la representación del patrón, si el segmento de línea que conecta A y B pasa a través de otros puntos, estos puntos también deben estar en la secuencia y anteceder a A y B; de lo contrario, el patrón no será válido. Por ejemplo, una representación de patrón que comienza con (3,1) y luego (1,3) no es válida porque el segmento pasa a través de (2,2) que no apareció en la representación de patrón antes (3,1), y el correcto La representación de este patrón es (3,1) (2,2) (1,3). Pero el patrón (2,2) (3,2) (3,1) (1,3) es válido porque (2,2) apareció antes (3,1).

En la representación del patrón no mencionamos el mismo punto más de una vez, incluso si el patrón tocará este punto nuevamente a través de otro segmento válido, y cada segmento en el patrón debe ir de un punto a otro que el patrón no hizo ' t toque antes y podría pasar por algunos puntos que ya aparecieron en el patrón.

La longitud de un patrón es la suma de las distancias de Manhattan entre cada dos puntos consecutivos en la representación del patrón. La distancia de Manhattan entre dos puntos (X1, Y1) y (X2, Y2) es | X1 - X2 | + | Y1 - Y2 | (donde | X | significa el valor absoluto de X).

Un patrón debe tocar al menos dos puntos

mi enfoque fue una fuerza bruta, bucle sobre los puntos, comenzar en el punto y usar decrecientemente recursivamente la longitud hasta alcanzar una longitud cero y luego sumar 1 al número de combinaciones.

¿Hay alguna manera de calcularlo en una ecuación matemática o hay un algoritmo mejor para esto?

ACTUALIZAR: ¡Esto es lo que he hecho, da algunas respuestas incorrectas! Creo que el problema está enisOk función!notAllowed es una máscara global de bits de los puntos no permitidos.

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;
}