Rezolvare PBinfo #1478

Prin OCR (Optical Character Recognition) se înţelege tehnologia prin care un program de calculator identifică textul dintr-un fișier în care acesta nu e stocat ca şiruri de caractere, ci ca ansamblu de pixeli (imagine).

Să presupunem că am scanat o imagine alb negru care conţine doar cifre. Cifrele sunt formate din puncte (pixeli) negre iar fundalul din puncte albe. Imaginea va fi reprezentată ca un tablou dreptunghiular de cifre 0 şi 1, cifrele 1 formează obiectele din imagine iar cifrele 0 fundalul.

Cerinţă

Scrieţi un program care să determine:

a) câte cifre sunt în imagine;
b) numărul de apariţii ale fiecărei cifre.

Spre exemplu, dacă imaginea scanată arată ca în figura următoare:

atunci rezultatul va fi:

8
0 2 1 1 3 2 5 1 7 1 8 1.

Explicaţie: în total sunt 8 cifre, cifra 0 apare de 2 ori, 1 apare o dată, 3 de două ori, 5 o dată, 7 o dată şi cifra 8 are o singură apariţie.

Date de intrare

Pe prima linie a fișierului de intrare easyocr.in se găsesc două numere separate printr-un spațiu. Primul număr, notat cu n, reprezintă numărul de linii al matricei prin care se reprezintă zona dreptunghiulară, iar al doilea, notat cu m, reprezintă numărul de coloane. Pe următoarele n linii se află matricea cu cifrele care codifică imaginea, pe fiecare linie găsindu-se m cifre de 0 și/sau 1 scrise fără spații între ele (0 reprezintă o zonă albă, care nu face parte dintr-o cifră, iar 1 reprezintă o zonă dintr-o cifră).

Cifrele sunt dispuse vertical, paralel cu marginile zonei dreptunghiulare, dar pot fi situate pe nivele diferite. Dimensiunile cifrelor nu se modifică. De asemenea, cifrele nu se suprapun și nici nu se ating în zonele cu valori 1, dar pot fi una în spaţiul alteia. Cifrele arată ca în figura de mai jos:

Date de ieșire

Pe prima linie din fişierul de ieşire easyocr.out se va scrie numărul de cifre descoperite în imagine, iar pe a doua linie se vor scrie, separate prin câte un spaţiu, cifrele în ordine crescătoare, fiecare cifră fiind urmată de numărul său de apariţii. Dacă o cifră are numărul de apariții 0 (zero), atunci ea nu va fi afişată.

Restricții și precizări

• 0 ≤ n, m ≤ 1000
• 0 ≤ nr ≤ 2000, unde nr reprezintă numărul de cifre aflate în matrice.
• O parte din conturul unei cifre poate coincide cu conturul matricei (zonei dreptunghiulare).

Exemplu:

easyocr.in

17 15
000000000000000
011111000000000
010000000000000
010000000000000
011111000000001
000001000000011
000001011111001
011111000001001
000000000001001
011111000010001
000001000100101
000001000101100
011111000100100
000001000000100
000001000000100
011111000000100
000000000000100

easyocr.out

5
1 2 3 1 5 1 7 1

Explicație

În imagine se află 5 cifre unde:

• cifra 1 apare de 2 ori;
• cifra 3 apare o singură dată;
• cifra 5 apare o singură dată;
• cifra 7 apare tot o singură dată.