Palabras baratas P80225


Statement
 

pdf   zip

thehtml

Dada una matriz n × m con letras diferentes, y una matriz asociada que indica el coste de cada letra, escribid todas las palabras que empiezan en una posición inicial dada, acaban en una posición final dada, y tienen un coste acumulado no superior a un máximo dado. Dentro de la matriz os podéis mover horitzontalmente y verticalmente, pero sin repetir casillas.

Entrada

La entrada consiste en un solo caso, con n y m, la matriz de letras, la matriz de costes, la fila y columna de la posición inicial, la fila y columna de la posición final, y el coste acumulado máximo. Suponed 1 ≤ n · m ≤ 52, y que todos los costes son enteros entre 1 y 106. Las filas y columnas se numeran a partir de 0.

Salida

Escribid todas las palabras válidas en cualquier orden.

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
    Spanish
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++