== include(page="template/taskheader" task_id="bitmap") ==
Poveste si cerinta...
Niste cercetatori au inventat un mod de a codifica un bitmap de dimensiuni $MxN$ sub forma unui sir de caractere. Sirul este, de fapt, o reprezentare a unor operatii efectuate asupra bitmap-ului. Algoritmul de codificare este descris in continuare:
* daca toate celulele bitmap-ului au culoarea $1$, atunci codificarea este $"1"$
* daca toate celulele bitmap-ului au culoarea $0$, atunci codificarea este $"0"$
* altfel, trebuie sa alegeti una din urmatoarele modalitati pentru a codifica bitmap-ul:
** $Codificare(B) = "A" + Codificare(B{~1~}) + Codificare(B{~2~})$, unde $"+"$ reprezinta operatia de concatenare, $B{~1~}$ este bitmap-ul rezultat prin pastrarea primelor $M/2$ linii ale bitmap-ului $B$ si a tuturor coloanelor, iar $B{~2~}$ este bitmap-ul rezultat prin pastrarea ultimelor $M-M/2$ linii ale bitmap-ului $B$ si a tuturor coloanelor (astfel, $B{~1~}$ va avea $M/2$ linii si $N$ coloane, iar $B{~2~}$ va avea $M-M/2$ linii si $N$ coloane).
** $Codificare(B) = "B" + Codificare(B{~1~}) + Codificare(B{~2~})$, unde $"+"$ reprezinta operatia de concatenare, $B{~1~}$ este bitmap-ul rezultat prin pastrarea primelor $N/2$ coloane ale bitmap-ului $B$ si a tuturor liniilor, iar $B{~2~}$ este bitmap-ul rezultat prin pastrarea ultimelor $N-N/2$ linii ale bitmap-ului $B$ si a tuturor liniilor (astfel, $B{~1~}$ va avea $M$ linii si $N/2$ coloane, iar $B{~2~}$ va avea $M$ linii si $N-N/2$ coloane).
** $Codificare(B) = "C" + Codificare(B{~1~}) + Codificare(B{~2~})$, unde $"+"$ reprezinta operatia de concatenare, $B{~1~}$ este bitmap-ul rezultat prin pastrarea tuturor liniilor cu numere impare ale bitmap-ului $B$ (liniile sunt numerotate incepand de la $1$) si a tuturor coloanelor, iar $B{~2~}$ este bitmap-ul rezultat prin pastrarea tuturor liniilor cu numere pare ale bitmap-ului $B$ si a tuturor coloanelor (astfel, $B{~1~}$ va avea $M-M/2$ linii si $N$ coloane, iar $B{~2~}$ va avea $M/2$ linii si $N$ coloane).
** $Codificare(B) = "D" + Codificare(B{~1~}) + Codificare(B{~2~})$, unde $"+"$ reprezinta operatia de concatenare, $B{~1~}$ este bitmap-ul rezultat prin pastrarea tuturor coloanelor cu numere impare ale bitmap-ului $B$ (coloanele sunt numerotate incepand de la $1$) si a tuturor liniilor, iar $B{~2~}$ este bitmap-ul rezultat prin pastrarea tuturor coloanelor cu numere pare ale bitmap-ului $B$ si a tuturor liniilor (astfel, $B{~1~}$ va avea $M$ linii si $N-N/2$ coloane, iar $B{~2~}$ va avea $M$ linii si $N/2$ coloane).
Fiind dat un bitmap, gasiti lungimea celei mai scurte codificari a acestuia.
h2. Date de intrare
...
Prima linie a fisierului de intrare $bitmap.in$ contine numarul de teste $T$. Urmatoarele linii descriu cele $T$ teste. Prima linie a fiecarui test contine $2$ numere intregi $M$ si $N$, reprezentand numarul de linii si de coloane ale bitmap-ului. Fiecare din rumatoarele $M$ linii contine un sir de $N$ caractere din multimea ${'0','1'}$, reprezentand cate o linie a bitmap-ului.
h2. Date de iesire
...
Pentru fiecare test, afisati in fisierul de iesire $bitmap.out$ cate o linie continand lungimea minima a unei codificari a bitmap-ului din testul respectiv.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 1105$
* $1 ≤ M,N ≤ 11$
h2. Exemplu
table(example). |_. bitmap.in |_. bitmap.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|2
4 6
000000
111111
000000
111111
5 8
01011111
01011111
01011010
01011010
01011010
|3
9
|
h3. Explicatie
...
O codificare de lungime minima pentru primul test este: $C01$
O codificare de lungime minima pentru cel de-al doilea test este: $BD01A1D10$
== include(page="template/taskfooter" task_id="bitmap") ==
