Més camins en un tauler (1) P35368


Statement
 

pdf   zip

thehtml

Considereu un tauler n × 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.

Public test cases
  • Input

    2 3 0
    ...
    ...
    
    2 2 3
    XX
    .X
    
    3 4 0
    .X..
    ...X
    X...
    
    3 4 1
    .X..
    ...X
    X...
    
    3 4 2
    .X..
    ...X
    X...
    

    Output

    DRR
    RDR
    RRD
    ----------
    RD
    ----------
    DRDRR
    DRRDR
    ----------
    DDRRR
    DRRRD
    RDDRR
    RDRDR
    RRDDR
    ----------
    RDRRD
    RRDRD
    RRRDD
    ----------
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++ Python