Reise durchs Gitter
Du erhältst ein n x n Gitter, in dem du alle Wege finden sollst, die von der oberen linken Ecke bis zur unteren rechten Ecke führen.
In diesem Gitter kannst du dich nur nach unten oder nach rechts bewegen. Jede Zelle steht für eine Position im Gitter und ist entweder leer oder blockiert. Blockierte Zellen dürfen nicht passiert werden. Dein Ziel ist es, alle möglichen Wege zu finden, indem du dich ausschließlich nach unten oder nach rechts von der oberen linken Ecke zur unteren rechten Ecke fortbewegst.
Eingabe
Die erste Zeile enthält eine einzelne ganze Zahl n (1 ≤ n ≤ 10), die die Größe des Gitters angibt.
Ausgabe
Gib alle Wege von der oberen linken Ecke zur unteren rechten Ecke aus, wobei nur die leeren Zellen berücksichtigt werden. Jeder Weg soll in einer neuen Zeile ausgegeben werden und besteht aus den Zeichen D (für „down“/nach unten) und R (für „right“/nach rechts). Die Reihenfolge der ausgegebenen Wege ist beliebig.
Beispiele
Eingabe | Ausgabe |
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