harta4

Harta4

== include(page="template/taskheader" task_id="harta4") ==

Poveste şi cerinţă...

De-a lungul timpului, Secţiunea Unu a adunat numeroase fotografii din satelit, acestea fiind nişte hărţi a diferitelor locaţii în care diverse organizaţii teroriste îşi desfăşoară activitatea.
 
Birkhoff a constatat că toate aceste hărţi ocupă foarte mult spaţiu pe serverele Secţiunii, aşa că s-a hotărât să le comprime. Pentru a fi imposibil de decomprimat de cineva din afara Secţiunii, Birkhoff a inventat un sistem de decomprimare propriu.
 
O hartă decomprimată este stocată sub forma a două numere naturale $N$ şi $M$, reprezentând dimensiunea hărţii (numărul de linii respectiv numărul de coloane) şi o matrice de numere naturale cu $N$ linii şi $M$ coloane.
 
O hartă comprimată este stocată sub forma a două numere naturale $N$ şi $M$, reprezentând dimensiunea hărţii (numărul de linii respectiv numărul de coloane) şi un şir de numere naturale şi litere.
 
Conţinutul hărţii este codificat complet prin şirul de numere naturale şi litere. Astfel, se disting trei cazuri:
 
* codificarea începe cu un număr natural $K$, caz în care matricea hăţii are în toate celulele sale numărul $K$;
* codificarea începe cu litera "O", urmată de un număr natural (numit în continuare $L$) şi de descrierea a două alte hărţi, caz în care matricea hărţii a fost împărţită într-o sub-matrice superioară (de $L$ linii şi $M$ coloane) şi o sub-matrice inferioară (de $N - L$ linii şi $M$ coloane) iar cele două descrieri din codificare corespund respectiv celor două sub-matrice;
* codificarea începe cu litera "V", urmată de un număr natural (numit în continuare $C$) şi de descrierea a două alte hărţi, caz în care matricea hărţii a fost împărţită într-o sub-matrice stângă (de $N$ linii şi $C$ coloane) şi o sub-matrice dreaptă (de $N$ linii şi $M - C$ coloane) iar cele două descrieri din codificare corespund respectiv celor două sub-matrice.
 
Putem scrie cele de mai sus mai succint, astfel:
 
* Cod{~mat(N, M)~} -> K
* Cod{~mat(N, M)~} -> "O", L, Cod{~sup(L, M)~}, Cod{~inf(N - L, M)~}
* Cod{~mat(N, M)~} -> "V", C, Cod{~st(N, C)~}, Cod{~dr(N, M - C)~}
 
V-aţi oferit să-l ajutaţi pe Birkhoff, aşa că va trebui, pentru o hartă pe care v-a pus-o la dispoziţie, să-i spuneţi care este lungimea minimă a unui şir care o comprimă fără pierdere de calitate.

h2. Date de intrare