Fişierul intrare/ieşire:	harta4.in, harta4.out	Sursă	Tabăra ICHB 2012, Ziua 1, Grupa 2
Autor	Dan Constantin Spatarel	Adăugată de	Dan-Constantin Spatarel •spatarel
Timp execuţie pe test	0.1 sec	Limită de memorie	12288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Harta4

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)}

Se impun restricţiile:

• 1 ≤ L ≤ N
• 1 ≤ C ≤ M

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.

Date de intrare

Fişierul de intrare harta4.in conţine pe prima linie două numere naturale N şi M. Pe fiecare din următoarele N linii se află câte M numere naturale, reprezentând harta pe care Birkhoff v-a pus-o la dispoziţie.

Date de ieşire

În fişierul de ieşire harta4.out va găsi un singur număr natural, reprezentând lungimea minimă a unui şir care comprimă harta dată fără pierdere de calitate.

Restricţii

• 1 ≤ N, M ≤ 30
• Elementele matricei vor fi numere naturale, cuprinse între 1 şi 100.

Exemplu

Explicaţie

Matricea dată poate fi codificată optim prin şirul:
O, 2, V, 2, 1, 2, 2, de lungime 7.
Pentru clarificare, putem paranteza şirul: (O, 2, (V, 2, (1), (2)), (2)).

Cum se trimit solutii?