[OJI][X]Imagine
0Sa consideram o imagine alb-negru de dimensiune LxL pixeli. Un pixel poate fi alb (codificat cu valoarea 0) sau negru (codificat cu valoarea 1). Imaginile pot fi compresate in diverse moduri. Una dintre cele mai cunoscute scheme de compresie este urmatoarea:
1. Daca imaginea este formata atat din pixeli 1, cat si din pixeli 0, se retine valoarea 1, care indica faptul ca imaginea va fi partitionata in alte 4 subimagini, asa cum este descris la pasul 2. Altfel codificam intreaga imagine ca 00 sau 01 semnificand faptul ca intreaga imagine este formata numai din pixeli 0, respectiv numai din pixeli 1.
2. O imagine I este impartita in 4 subimagini A, B, C, D dupa cum este ilustrat in figura urmatoare:
I I I I I I B B B A A A I I I I I I B B B A A A I I I I I I => B B B A A A I I I I I I C C C D D D I I I I I I C C C D D D I I I I I I C C C D D D
Apoi se aplica din nou pasul 1, pentru fiecare dintre cele 4 subimagini, in ordinea A, B, C, D.
Numarul de biti (cifre de 0 sau 1) obtinuti in urma compresiei reprezinta dimensiunea imaginii compresate.
Data fiind o imagine, sa se determine dimensiunea imaginii compresate.
Olimpiada Municipala de Informatica, Iasi 2005
Date de intrare
Fisierul de intrare imagine.in contine pe prima linie numarul natural L, reprezentand dimensiunea imaginii. Urmatoarele L linii contin imaginea codificata, fiecare linie continand exact L valori 0 sau 1 separate prin cate un spatiu.
Date de iesire
Fisierul de iesire imagine.out contine o singura linie pe care se afla un numar natural care reprezinta dimensiunea imaginii compresate.
Restrictie
1< =L<=240
Exemple
imagine.in
4
1 1 1 1
1 1 0 1
0 1 0 0
0 0 1 1
imagine.out
30
imagine.in
8
0 0 0 0 1 1 1 1
0 0 0 0 1 1 1 1
0 0 0 0 1 1 1 1
0 0 0 0 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
imagine.out
9
Explicatii
1. Compresia imaginii din exemplul 1 se realizeaza astfel:
1 1 1 1 1 1 0 1 0 1 0 0 =1 ( 0 1 ) ( 1 1 ) ( 0 0 ) ( 1 1 ) 0 0 1 1 0 0 1 1 1 1 0 1
=1 1(0)(0)(0)(1) 01 1(1)(0)(1)(0) 1(0)(1)(1)(1) =
=1 1 00 00 00 01 01 1 01 00 01 00 1 00 01 01 01
Deoarece dupa compresare sunt necesari 30 de biti, dimensiunea imaginii compresate este 30.
2. Compresia imaginii din exemplul 2 se realizeaza astfel:
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 = 1 ( 1 1 1 1 ) ( 0 0 0 0 ) ( 1 1 1 1 ) ( 1 1 1 1 ) 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1
= 1 01 00 01 01
In acest caz dimensiunea imaginii compresate este 9.
Solutie oficiala :
Timp executie: Nu am reusit sa-l calculez
Memorie folosita : O(n^2)
Vom avea nevoie de o functie ce verifica daca o sub-imagine ce incepe la pozitia x1,y1 si se termina la x2,y2 are aceeasi culoare.Daca doar unul din pixelii respectivei imagini substrase este diferit se imparte imagine de lungime |x1-x2| si inaltime |y1-y2| in 4 cadrane si se aduna numarul de biti recursiv la solutie.
