Paraules barates P80225


Statement
 

pdf   zip

thehtml

Donada una matriu n × m amb lletres diferents, i una matriu associada que indica el cost de cada lletra, escriviu totes les paraules que comencen en una posició inicial donada, acaben a una posició final donada, i tenen un cost acumulat no superior a un màxim donat. Dins de la matriu podeu moure-us horitzontalment i verticalment, però sense repetir caselles.

Entrada

L’entrada consisteix en un sol cas, amb n i m, la matriu de lletres, la matriu de costs, la fila i columna de la posició inicial, la fila i columna de la posició final, i el cost acumulat màxim. Suposeu 1 ≤ n · m ≤ 52, i que tots els costs són enters entre 1 i 106. Les files i columnes es numeren a partir de 0.

Sortida

Escriviu totes les paraules vàlides en qualsevol ordre.

Public test cases
  • Input

    2 4
    EbAc
    aIpU
    5 1 2 7
    5 2 3 1
    0 2  1 3  9
    

    Output

    ApU
    AbIpU
    
  • Input

    4 3
    COE
    RUY
    ASD
    FIN
    1 97  1
    1  1  1
    1  1  1
    1  1  1
    2 1  0 2  100
    

    Output

    SUOE
    SURAFINDYE
    SUYE
    SIFARUYE
    SINDYE
    SARUYE
    SAFINDYE
    SDYE
    SDNIFARUYE
    
  • Input

    1 1
    z
    1000000
    0 0  0 0  1000000
    

    Output

    z
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++