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.
