.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » monkey

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
monkey


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

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

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Şansa de a deveni campion 2002: adevar, marcare, joc10, prieteni1, bare, soricel1, traseu, zapezi, banda10, soricel2, masina2, excursie1, asmax, salvare, perechi1, culmi, tramvai1, numar2, sume1, raft, bloc, schi, joc12, sediu, soricel3, ferma, fni, sah1, suma3, granita, nr4, fractie, blockout, join, cod3, tunel, lover, trip, pepsi, string, medii, transport, tren3, avion, prime1, poligon1, premii1, garaj, carti2, gramada, microvirus, tv, gramezi1, puncte2, benzina, aranjari, numere5, fat, izo, cafea, top, echipe1, zoo, secvente
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
Despre backtracking: acop, bipal, magic2, vagoane, friends, tricouri, festival, numar, pento, ro, jobs, onu2, sir3, cai1, labirint, dans, ham, sudoku, caramele, linie, puncte, castel, excursia, joc7, pattern, avere, paianjen, medii, scara1, numere8, banda1, spirala1, cofetar, gradina, placa, smin, jucarii, immortal, concat, cubinvers, codif, izvor, avioane, jb, prisme, triburi1, genab, dineu, antitero, ornament, virgule
Despre recursivitate: tren, mere, chimie, sarpe, soldati, formule, infinit, compress, ploaia, cartoane, sub, metro, windows, lacuri, apel, maxq, pav, joc11, paianjen, suma2, csir, lsort, imagine, dir, desert, echitabil, rez, logic, gradina, links, dreptunghiuri, expresie1, cumpanit, reziston, antitero, sablon3
Software recomandat
surse trimise | ajutor