Sopa de lletres amb punts P87801


Statement
 

pdf   zip

thehtml

Considereu un tauler f × c on cada casella té una lletra i un nombre que diu quant val aquella casella. Donades diverses paraules p, cal dir el màxim nombre de punts que es pot aconseguir posant p horitzontalment (cap a la dreta) o verticalment (cap avall), de manera que totes les lletres coincideixin amb les del tauler.

Entrada

L’entrada consisteix en diversos casos, cadascun amb les dimensions f i c, seguides de f ‍files amb c lletres minúscules cadascuna, seguides de f files amb c naturals cadascuna. Després ve un nombre t seguit de t paraules no buides formades amb lletres minúscules. Podeu suposar que f i c estan entre 1 i 100, que el valor de cada casella es troba entre 0 i 106, i que les paraules donades no tenen més de 100 lletres.

Sortida

Per a cada paraula de cada cas, escriviu la màxima puntuació possible posant la paraula horitzontalment o verticalment. Si la paraula no hi és, escriviu “no”.

Public test cases
  • Input

    3 4
    a b c a
    b c a e
    c a b d
    10 20 30 40
    50 60 70 80
    15 25 35 45
    3
    bca
    cabb
    a
    
    1 1
    z
    1000000
    2
    y
    z
    

    Output

    180
    no
    70
    no
    1000000
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++ Python
    User solutions
    C++ Python