Se consideră o matrice pătratică cu 16 linii și 16 coloane. Elementele acestei matrice pot fi 0 sau 1. Această matrice reprezintă, de fapt, o literă a alfabetului englezesc (litera este formată din elementele a căror valoare este 1). Va trebui să determinați care este litera reprezentată de această matrice.
În acest scop veți avea la dispoziție un număr de N matrice pătratice cu 16 linii și 16 coloane care conțin reprezentări standard ale literelor. Litera corespunzătoare matricei date este dată de "cea mai apropiată matrice dintre cele N". Va trebui să definim distanța dintre două matrice. Pentru a determina o astfel de distanță, fiecărui element cu valoarea 1 din prima matrice va trebui să îi corespundă un element cu valoarea 1 din cea de-a doua matrice și fiecărui element cu valoarea 1 din cea de-a doua matrice să îi corespunda un punct din prima matrice. Așadar se va realiza o corespondență între elementele celor două matrice. Presupunem, fără a restrânge generalitatea, că prima matrice conține mai multe elemente cu valoarea 1 decât a doua. Numărul elementelor cu valoarea 1 din prima matrice va fi notat cu p, iar numărul elementelor cu valoarea 1 din cea de-a doua va fi notat cu q. În aceste condiții, fiecărui element cu valoarea 1 din cea de-a doua matrice îi vor corespunde [p/q] elemente din prima matrice. Dacă q nu este divizor al lui p, vor rămâne elemente în prima matrice care nu au corespondent. Acestora le vor corespunde elemente distincte din cea de-a doua matrice. Cu alte cuvinte, corespondențele vor fi "echilibrate", în sensul că dacă unui element dintr-o matrice îi corespund k elemente (și acest k este minimul numărului de elemente corespunzătoare elementelor din matrice), atunci tuturor celorlalte elemente le vor corespunde fie k, fie k + 1 elemente. Distanța dintre două matrice va fi dată de suma distanțelor dintre elementele puse în corespondență. Dacă un element de pe poziția (i1, j1) în prima matrice îi corespunde un element (i2, j2) în cea de-a doua, atunci distanța dintre cele două elemente va fi |i1 - i2| + |j1 - j2|. Evident, corespondențele trebuie alese în așa fel încât distanța dintre cele două matrice să fie cât mai mică posibil.
Fișierul de intrare OCR.IN conține pe primele 16 linii elementele matricei care reprezintă litera care trebuie recunoscută.
Pe următoarea linie se va afla numărul N al literelor date. Va urma descrierea literelor. Pentru fiecare literă vom avea 17 linii. Prima dintre ele va identifica litera (un caracter). Următoarele 16 linii vor conține descrierea literei. Valorile de pe o linie nu vor fi separate prin spații.
Fișierul de ieșire OCR.OUT trebuie să conțină o singură linie pe care se va afla un singur caracter reprezentând litera recunoscută.
OCR.IN
0000000000000000 0000000000000000 0000000000000000 0000000100000000 0000001010000000 0000010001000000 0000100000100000 0001000000010000 0001000000010000 0001111111110000 0001000000010000 0001000000010000 0001000000010000 0000000000000000 0000000000000000 0000000000000000 2 A 0000000000000000 0000000000000000 0000000100000000 0000001110000000 0000010001000000 0000100000100000 0001000000010000 0001100000110000 0001111111110000 0001100000110000 0001000000010000 0001000000010000 0001000000010000 0000000000000000 0000000000000000 0000000000000000 C 0000000000000000 0000000000000000 0000000000000000 0000111111111100 0001111000000010 0001110000000100 0001100000000000 0001100000000000 0001100000000000 0001100000000000 0001100000000000 0001100000000000 0001110000000100 0001111000000010 0000111111111100 0000000000000000 OCR.OUT A
|