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

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


Timp maxim de execuţie / test:
0.2s
Memorie totala disponibilă / stivă:
2MB / 1MB

Collapse este un joc foarte popular. Tabla de joc este reprezentată de o zonă dreptunghiulară de pe ecran, zona fiind împărţită în celule, organizate în N linii şi M coloane. Fiecare celulă poate conţine o piesă roşie (identificată prin litera R), verde (identificată prin litera V) sau albastră (identificată prin litera A).
Grupul unei piese este format din toate piesele care au aceeaşi culoare cu piesa respectivă şi la care se poate ajunge deplasându-ne numai pe piese de aceeaşi culoare cu piesa respectivă. O deplasare se poate face în 4 direcţii (sus, jos, stânga sau dreapta). Un grup trebuie să conţină cel puţin două piese.
Acţionând printr-un clic pe o piesă, tot grupul de piese corespunzător piesei respective va dispărea.
După ce grupul piesei asupra căreia am acţionat printr-un clic a dispărut, piesele de pe tablă se „prăbuşesc”. Prăbuşirea se realizează executând, în ordine, următoarele două operaţii:
1. Mai întâi, toate piesele rămase „cad” (sunt deplasate în jos), pentru a umple golurile de pe coloane; ordinea pieselor pe coloane se păstrează.
2. Dacă o coloană se goleşte complet, ea va fi eliminată, deplasând celelalte coloane spre stânga, cât este posibil; ordinea coloanelor păstrându-se.



Jocul se termină când pe tabla de joc nu se mai pot forma grupuri de piese.
Vasile joacă acest joc de mulţi ani. Niciodată nu joacă la întâmplare, întotdeauna foloseşte aceeaşi strategie. La fiecare pas, Vasile face un clic pe o piesă din cel mai mare grup existent pe tabla de joc. Chiar dacă există mai multe posibilităţi de a alege piesa, el va face clic pe piesa situată pe cea mai din stânga coloană. Şi dacă există mai multe posibilităţi de a alege o piesă pe cea mai din stânga coloană, Vasile o va alege întotdeauna pe cea situată pe linia cea mai joasă.

Cerinţă

Scrieţi un program care să simuleze jocul şi care să determine numărul de clicuri pe care le execută Vasile până la terminarea jocului.

Date de intrare

Fişierul de intrare joc11.in conţine pe prima linie două numere naturale separate printr-un spaţiu N M, care reprezintă numărul de linii şi respectiv numărul de coloane de pe tabla de joc. Urmează N linii, fiecare linie conţinând M caractere din mulţimea {‘R’, ‘V’, ‘A’}.

Date de ieşire

Fişierul de ieşire joc11.out va conţine o singură linie pe care va fi scris numărul de clicuri pe care le execută Vasile până la terminarea jocului.

Restricţii

1 ≤ N, M ≤ 50

Exemple

joc11.injoc11.out
3 4 AVVR AAVV AVRR 3
8 7 RRARVRV RRRRVAV VRRRVAR VVRRAVV VVRRAAA AAARVVA AAARVVR ARRRVRR 7

autor: Prof. Emanuela Cerchez
propunător: Prof. Marinel Şerban
Liceul de Informatică “Grigore Moisil”
marinel_serban@yahoo.com
Articole recomandate
Probleme recomandate
De la ONI 2005: baschet, ingerasi, numar1, prieteni, robinson, aritma, cezar, cuburi2, joc8, bifo, joc9, pal, romeo, seceta, antena, avere, paianjen, suma2, vizibil, masina3, csir, lsort, patrat, ziduri, anticip, bsir, evantai, galax, spion, texan
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, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, 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 recursivitate: tren, mere, chimie, sarpe, soldati, formule, infinit, compress, ploaia, cartoane, sub, metro, windows, lacuri, apel, maxq, pav, paianjen, suma2, monkey, csir, lsort, imagine, dir, desert, echitabil, rez, logic, gradina, links, dreptunghiuri, expresie1, cumpanit, reziston, antitero, sablon3
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, erdos, grup, scor2, reteta2, rezervatie, scoici, tablou, game, stea, submatrix, cifru, jokes, oua, trecere, na, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, camion, ceas1, fibo, parc, excursia, matricea, zidar, joc6, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, soricel2, avere, vizibil, sah1, blockout, masina3, lsort, anticip, matrice1, evantai, spion, pereti, zumzi, roboti, placare, tabel, ocr, numere7, lacusta, becuri, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, iepurasi, colorare, mat, submatrix1, simetric1, plaja, xor2, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, sir9, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
Despre fill: rebus, sarpe, insule, lacuri, zuzu, gradina, dreptunghiuri, drenaj, fillmat, parcela, acces, tsunami, betasah, zona, zone, taxa, foto, ferma1, antitero, robotzi
Software recomandat
surse trimise | ajutor