Pracsiu Dan (dnprx) Gigel a inventat un nou joc, de această dată utilizând un rebus sub forma de tablă pătratică cu n x n căsuțe. Fiecare căsuță conține câte o literă mare din alfabetul englez sau caracterul '.'. Literele formează pe orizontală sau pe verticală cuvinte delimitate prin caractere punct sau prin marginile tablei. Cel care joacă trebuie să determine cuvintele speciale din careu. Punctajul unui cuvânt se calculează ca suma codurilor ASCII ale literelor distincte care apar în acel cuvânt. Punctajul total al jocului se calculează însumând punctajele literelor distincte ale cuvintelor speciale distincte. Un cuvânt special îndeplinește simultan condițiile:
- este palindrom
- are lungime maximă relativ la alte cuvinte palindrom
Cerința
Să se scrie un program care sa determine, pentru un careu dat, punctajul maxim și cuvintele care permit obținerea punctajului maxim. Dacă nu există astfel de cuvinte se va afișa valoarea 0.
Date de intrare
Fișierul de intrare careu.in conține pe prima linie un număr natural n reprezentând dimensiunea careului. Următoarele n linii conțin fiecare câte n caractere, neseparate prin spații, reprezentând careul. Ultima linie a fișierului de intrare conține una dintre valorile 1 sau 2 reprezentând cerința.
Date de ieșire
Fișierul de ieșire careu.out conține pentru cerința 1, pe prima linie numărul de cuvinte speciale de valoare maximă găsite, iar pe următoarele linii se vor scrie aceste cuvinte în ordine alfabetică, câte unul pe linie; pentru cerința 2, pe prima linie a fișierului de ieșire se va scrie punctajul maxim determinat.
Restricții și precizări
2 <= n <= 50- Cuvintele sunt scrise cu litere mari și lungimea cuvintelor din soluție trebuie să fie cel puțin
2. - Pentru cerința 1 se acordă
60%din punctaj, iar pentru cerința 2 se acordă30%din punctaj - În concurs s-au acordat
10puncte din oficiu; aici se acordă10puncte pentru cele trei exemple.
Exemplul 1:
careu.in
3 A.A B.A ..C 1
careu.out
0
Explicație
Nu există nici un cuvânt special de lungime mai mare sau egală cu 2.
Exemplul 2:
careu.in
10 VERDE.CRIN DANA.DDDDD VOI.AOQOA. NU.AAOTE.. .UBOBU.AIA EZNGAIETAR ORIOATZULI TURN.NNNNN O.ZZCZZ.IU ELEGATEL.O 1
careu.out
8 AABAA AOQOA DDDDD EOTOE EZNZE NNNNN UBOBU ZZCZZ
Explicație
Cerința 1. Au fost determinate 8 cuvinte speciale
Exemplul 3:
careu.in
10 VERDE.CRIN DANA.DDDDD VOI.AOQOA. NU.AAOTE.. .UBOBU.AIA EZNGAIETAR ORIOATZULI TURN.NNNNN O.ZZCZZ.IU ELEGATEL.O 2
careu.out
832
Explicație
Cerința 2. Punctajul maxim pentru cele 8 cuvinte speciale este 832.
832 = 65+66+67+68+69+78+79+81+84+85+90
A B C D E N O Q T U Z