Voyage dans la grille
On vous propose une grille de dimensions
n x n, et vous devez trouver tous les chemins qui mènent du coin supérieur gauche au coin inférieur droit de la grille.Dans cette grille, vous ne pouvez vous déplacer que vers le bas ou vers la droite. Chaque case représente une position dans la grille qui peut être vide ou bloquée. Vous ne pouvez pas passer à travers une case bloquée. Votre objectif est donc de déterminer tous les chemins possibles entre le coin supérieur gauche et le coin inférieur droit en vous déplaçant uniquement vers le bas ou vers la droite.
Entrée
La première ligne contient un unique entier
n (1 ≤ n ≤ 10), qui correspond à la taille de la grille.Sortie
Affichez tous les chemins menant du coin supérieur gauche au coin inférieur droit, en ne tenant compte que des cases vides. Chaque chemin doit être imprimé sur une ligne distincte. Un chemin est décrit par une suite de caractères
D (pour indiquer un déplacement vers le bas) et R (pour un déplacement vers la droite). Vous pouvez afficher ces chemins dans n’importe quel ordre.Exemples
Input | Output |
3
0 0 1
0 0 0
0 1 0 | RDRD
DRRD |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB