joc

Exista si jocuri care pot fi jucate de un singur jucator. Un astfel de joc este descris mai jos.

O tabla rectangulara de dimensiuni NxM este plina cu litere mari ale alfabetului (A-Z). La începutul jocului în coltul din stânga sus al tablei este dispusa o piesa. În fiecare moment, jucatorul poate muta aceasta piesa într-o pozitie vecina (sus, dreapta, jos, stânga), cu singura restrictie ca în pozitia respectiva sa nu existe o litera peste care piesa a mai trecut. Scopul jocului este de a mentine piesa în joc cât mai mult posibil. Jocul se opreste cand piesa, nemaiputand fi mutata intr-o pozitie valida, se opreste intr-o pozitie in care exista o litera peste care piesa a mai trecut.

Cerinta

Scrieti un program care determina numarul maxim de mutari pe care le poate face jucatorul.

Date de intrare

Prima linie a fisierului de intrare joc.in contine doua valori întregi N si M, separate printr-un singur spatiu, reprezentând dimensiunile tablei de joc.

Urmatoarele N linii contin fiecare câte M caractere reprezentând tabla de joc.

Date de iesire

Fisierul de iesire joc.out contine o singura linie pe care se afla numarul maxim de mutari pe care le poate face jucatorul.

Restrictii

· 1 <= N, M <= 30

Exemple

joc.in	joc.out
2 4 CAAB ADCB	3
3 6 HFDFFB AJHGDH DGAGEH	6
5 5 IEFCJ FHFKC FFALF HFGCF HMCHH	10

Timp maxim de executie/test: 0.1 secunde

prof. Serban Marinel

Liceul de Informatica"Gr. C. Moisil" Iasi

Contact: marinel_serban_at_yahoo.com