Més camins en un tauler (1) P35368

Considereu un tauler $n \times m$ amb alguns obstacles. Trobeu tots els camins que surten de la cantonada superior esquerra, arriben a la cantonada inferior dreta, i passen exactament per sobre de $k$ obstacles. Els únics moviments permesos són cap avall i cap a la dreta.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb $n$, $m$ i $k$, seguits d’$n$ línies amb $m$ caràcters cadascuna. Els punts indiquen posicions lliures, i les ‘X’ obstacles. Podeu assumir que $n$ i $m$ estan entre 2 i 10, i que sempre hi haurà almenys un camí possible.

Sortida

Per a cada cas, escriviu en ordre lexicogràfic tots els camins possibles. Feu servir ‘D’ per als moviments cap avall, i ‘R’ per als moviments cap a la dreta. Escriviu una línia amb 10 guions després de cada cas.

Observació

La solució esperada és un backtracking senzill.