Ich bin darauf gestoßenProblem.

Dieser fragt nach der Anzahl der Möglichkeiten, wie ein Sperrmuster einer bestimmten Länge im 4x3-Raster erstellt werden kann, und folgt den Regeln.Möglicherweise sind einige der Punkte nicht im Pfad enthalten

Ein gültiges Muster hat die folgenden Eigenschaften:

Ein Muster kann anhand der Folge von Punkten dargestellt werden, die es zum ersten Mal berührt (in der gleichen Reihenfolge wie beim Zeichnen des Musters). Ein Muster von (1,1) bis (2,2) ist nicht dasselbe wie ein Muster von (2,2) nach (1,1) gehen.

Wenn für jeweils zwei aufeinanderfolgende Punkte A und B in der Musterdarstellung das Liniensegment, das A und B verbindet, einige andere Punkte durchläuft, müssen diese Punkte ebenfalls in der Reihenfolge vor A und B liegen, da sonst das Muster ungültig wird. Beispielsweise ist eine Musterdarstellung, die mit (3,1) dann (1,3) beginnt, ungültig, da das Segment (2,2) durchläuft, das in der Musterdarstellung vor (3,1) nicht vorlag, und das richtige Darstellung für dieses Muster ist (3,1) (2,2) (1,3). Aber das Muster (2,2) (3,2) (3,1) (1,3) ist gültig, weil (2,2) vor (3,1) erschien.

In der Musterdarstellung wird derselbe Punkt nicht mehr als einmal erwähnt, auch wenn das Muster diesen Punkt erneut durch ein anderes gültiges Segment berührt, und jedes Segment im Muster muss von einem Punkt zu einem anderen Punkt gehen, den das Muster nicht erreicht hat. ' Wenn Sie vorher nicht berühren, werden möglicherweise einige Punkte durchlaufen, die bereits im Muster enthalten sind.

Die Länge eines Musters ist die Summe der Manhattan-Abstände zwischen jeweils zwei aufeinander folgenden Punkten in der Musterdarstellung. Der Manhattan-Abstand zwischen zwei Punkten (X1, Y1) und (X2, Y2) beträgt | X1 - X2 | + | Y1 - Y2 | (wobei | X | den absoluten Wert von X bedeutet).

Ein Muster muss mindestens zwei Punkte berühren

Mein Ansatz war eine rohe Kraft, schleife über die Punkte, beginne am Punkt und dekrementiere die Länge rekursiv, bis eine Länge von Null erreicht ist. Addiere dann 1 zu der Anzahl der Kombinationen.

Gibt es eine Möglichkeit, es in einer mathematischen Gleichung zu berechnen, oder gibt es dafür einen besseren Algorithmus?

AKTUALISIEREN: Hier ist, was ich getan habe, es gibt einige falsche Antworten! Ich denke, das Problem liegt darinisOk funktion!notAllowed ist eine globale Bitmaske der nicht erlaubten Punkte.

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