Monkey este un joc pentru un singur jucator, care se joaca pe o tabla dreptunghiulara
impartita casute care formeaza R linii si C coloane. In fiecare casuta a tablei
se afla o litera mare a alfabetului englez (de la A la Z).
Jucatorul are un jeton pe care este desenata o maimuta. Inainte de inceperea
jocului maimuta va fi plasata in coltul din stanga sus al tablei (prima linie,
prima coloana).
La o mutare, jucatorul poate plasa maimuta pe una dintre pozitiile adiacente
pozitiei sale curente (adica pe o pozitie invecinata, aflata sus, jos, in stanga
sau in dreapta). Singura restrictie este ca maimuta nu poate fi asezata de doua
ori peste o aceeasi litera.
Scopul jocului este de a face cât mai multe mutari.
Cerinta
Scrieti un program care sa determine numarul maxim de pozitii pe care le poate
"vizita" maimuta intr-un singur joc.
Date de intrare
Pe prima linie a fisierului de intrare monkey.in se afla doua numere naturale
R si C separate printr-un spatiu, reprezentand numarul de linii, respectiv numarul
de coloane ale tablei de joc. Pe fiecare dintre urmatoarele R linii se afla
C litere, care reprezinta literele aflate pe tabla pe linia respectiva.
Date de iesire
Fisierul de iesire monkey.out contine o singura linie pe care
se afla numarul maxim de pozitii de pe tabla de joc ce au putut fi vizitate
de maimuta.
Restrictii
1 <= R, C <= 20
Exemple
monkey.in
monkey.out
2 4
CAAB
ADCB
3
monkey.in
monkey.out
3 6
HFDFFB
AJHGDH
DGAGEH
6
monkey.in
monkey.out
5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH
10
prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi