Pfadbeschreibung
Du hast ein
n x n-Gitter aus Zellen. Ein Pfad beginnt in der Zelle (1, 1), besucht alle Zellen und endet in der Zelle (n, 1). Dabei kann der Pfad sich nur nach rechts (R), links (L), oben (U) oder unten (D) bewegen, und er darf jede Zelle höchstens einmal betreten. Der Pfad wird durch die Zeichen LRUD beschrieben, wobei jedes Zeichen eine entsprechende Bewegungsrichtung vorgibt.
Allerdings sind in der Pfadbeschreibung einige Zeichen durch Fragezeichen (?) ersetzt, was bedeutet, dass die genaue Richtung an diesen Stellen unbekannt ist.Deine Aufgabe besteht darin, die Anzahl aller möglichen Pfade zu ermitteln, die mit der gegebenen Pfadbeschreibung übereinstimmen.
Eingabe
Die erste Zeile enthält eine einzelne Ganzzahl
n (3 ≤ n ≤ 6), welche die Größe des Gitters angibt.
Die zweite Zeile enthält die Pfadbeschreibung, einen String bestehend aus L, R, U, D und ?, wobei jedes Zeichen eine Bewegung in die entsprechende Richtung repräsentiert. Die Länge der Pfadbeschreibung beträgt .Ausgabe
Gib eine einzige Zahl aus, die die Anzahl aller verschiedenen Pfade angibt, die zu der vorgegebenen Pfadbeschreibung passen.
Beispiele
Eingabe | Ausgabe |
3
RR??LUL? | 1 |
4
??R??????????L? | 3 |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB