Fugida del tauler P18760


Statement
 

pdf   zip

thehtml

Considereu un tauler d’escacs n × m. Inicialment us trobeu a la cantonada de baix a la dreta, és a dir, a la posició (n − 1, m − 1). El vostre objectiu és sortir del tauler. Hi ha algunes posicions prohibides, marcades amb asteriscos. Les caselles permeses tenen una ‘R’ o una ‍‘C’. Quan us trobeu sobre una ‘R’, podeu fer un moviment d’un rei dels escacs. Quan us trobeu sobre una ‘C’, podeu fer un moviment d’un cavall. A més, no podeu fer mai cap moviment que incrementi la fila o la columna on us trobeu. De quantes maneres diferents podeu sortir del tauler?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb dos naturals n i m, ambdós entre 1 i 12. Segueixen n línies amb m caràcters cadascuna, els quals poden ser un asterisc, una ‘R’ o una ‘C’. La cantonada de baix a la dreta no té mai un asterisc.

Sortida

Per a cada cas, escriviu el nombre de maneres diferents de sortir del tauler. Aquest nombre sempre és més petit que 109.

Public test cases
  • Input

    1 2
    *R
    
    1 2
    CR
    
    2 2
    **
    *R
    
    3 3
    RR*
    R**
    **C
    
    3 7
    CR***RR
    RR*CRRR
    RRRRRRC
    

    Output

    2
    4
    0
    10
    7
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++