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