Description du Parcours
On dispose d’une grille de dimensions
n x n. Un parcours part de la cellule (1, 1), visite toutes les cellules, puis se termine à la cellule (n, 1). À chaque étape, le déplacement peut s’effectuer vers la droite (R), la gauche (L), le haut (U) ou le bas (D), et chaque cellule ne peut être visitée qu’une seule fois. Le parcours est défini à l’aide des caractères LRUD, où chaque caractère représente un mouvement dans la direction correspondante.
Cependant, certains de ces caractères sont remplacés par des points d’interrogation (?), ce qui signifie que la direction est inconnue.Votre objectif est de déterminer combien de parcours différents correspondent à cette description incomplète.
Entrée
La première ligne contient un entier
n (3 ≤ n ≤ 6), qui représente la taille de la grille.
La deuxième ligne contient la description du parcours, une chaîne composée des caractères L, R, U, D et ?, dans laquelle chaque caractère indique la direction prise. La longueur de cette description est égale à .Sortie
Affichez un seul entier, correspondant au nombre de parcours différents qui satisfont la description donnée.
Exemples
Entrée | Sortie |
3
RR??LUL? | 1 |
4
??R??????????L? | 3 |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB