Fişierul intrare/ieşire:bitmap.in, bitmap.outSursăHappy Coding 2007
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.55 secLimită de memorie67583 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Bitmap

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(B1) + Codificare(B2), unde "+" reprezinta operatia de concatenare, B1 este bitmap-ul rezultat prin pastrarea primelor M/2 linii ale bitmap-ului B si a tuturor coloanelor, iar B2 este bitmap-ul rezultat prin pastrarea ultimelor M-M/2 linii ale bitmap-ului B si a tuturor coloanelor (astfel, B1 va avea M/2 linii si N coloane, iar B2 va avea M-M/2 linii si N coloane).
    • Codificare(B) = "B" + Codificare(B1) + Codificare(B2), unde "+" reprezinta operatia de concatenare, B1 este bitmap-ul rezultat prin pastrarea primelor N/2 coloane ale bitmap-ului B si a tuturor liniilor, iar B2 este bitmap-ul rezultat prin pastrarea ultimelor N-N/2 linii ale bitmap-ului B si a tuturor liniilor (astfel, B1 va avea M linii si N/2 coloane, iar B2 va avea M linii si N-N/2 coloane).
    • Codificare(B) = "C" + Codificare(B1) + Codificare(B2), unde "+" reprezinta operatia de concatenare, B1 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 B2 este bitmap-ul rezultat prin pastrarea tuturor liniilor cu numere pare ale bitmap-ului B si a tuturor coloanelor (astfel, B1 va avea M-M/2 linii si N coloane, iar B2 va avea M/2 linii si N coloane).
    • Codificare(B) = "D" + Codificare(B1) + Codificare(B2), unde "+" reprezinta operatia de concatenare, B1 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 B2 este bitmap-ul rezultat prin pastrarea tuturor coloanelor cu numere pare ale bitmap-ului B si a tuturor liniilor (astfel, B1 va avea M linii si N-N/2 coloane, iar B2 va avea M linii si N/2 coloane).

Fiind dat un bitmap, gasiti lungimea celei mai scurte codificari a acestuia.

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.

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.

Restrictii

  • 1 ≤ T ≤ 1105
  • 1 ≤ M,N ≤ 11

Exemplu

bitmap.inbitmap.out
2
4 6
000000
111111
000000
111111
5 8
01011111
01011111
01011010
01011010
01011010
3
9

Explicatie

O codificare de lungime minima pentru primul test este: C01
O codificare de lungime minima pentru cel de-al doilea test este: BD01A1D10

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content