Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | pictura.in, pictura.out | Sursă | Tiberiu Popoviciu 2011, Clasa a 9-a |
| Autor | Perticas Catalin | Adăugată de |  perticas catalin •perticas_catalin |
| Timp execuţie pe test | 0.325 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Pictura
Mitruţ s-a apucat de curând de pictat matrici. Fiindcă vrea să vadă cât de pricepuţi sunteţi voi la pictură, el vă pune la dispoziţie o matrice cu N*M căsuţe pictate de el. Fiecare căsuţă are o culoare între 0 şi K. Dacă o căsuţă are culoarea 0, înseamnă că încă nu a fost pictată. Numim o ‘zonă’ de culoare x, o submulţime maximală de căsuţe din matrice cu proprietatea că toate au culoarea x şi există drum între oricare două(trecând prin căsuţe adiacente de acceaşi culoare). Se ştie că toate zonele urmează o linie(de grosime 1) care poate să-şi schimbe direcţia şi să se auto-intersecteze, dar nu se poate dubla(grosimea este 1 peste tot). Pentru mai multă claritate urmăriţi explicaţiile de mai jos.
Zonă validă de culoare x
(2 auto-intersecţtii, 9 schimbări de direcţie)
0 0 0 0 x x x x 0
0 0 x 0 x 0 0 x x
0 x x x x x x 0 x
0 0 x 0 x 0 x 0 x
0 0 x 0 x x x 0 x
0 0 x 0 0 0 0 0 x
0 0 x x x x x x x
Zonă incorectă de culoare x (nu apare în teste)
0 0 0 0 x 0 0 0 0
0 0 0 0 x x 0 0 0
0 0 0 x x x 0 0 0
0 0 0 x 0 0 0 0 0
0 0 0 x 0 0 0 0 0
0 0 0 x x x 0 0 0
0 0 0 0 0 0 0 0 0
Cerinţă
Să se determine K, numărul de culori folosite, iar pentru fiecare culoare i, determinaţi numărul Zi de zone în care apare, Di de câte ori îşi schimbă direcţia (suma schimbăriilor de direcţie pentru fiecare zonă) şi Ii de câte ori se auto-intersectează (suma numărului de intersecţii pentru fiecare zonă).
Date de intrare
Fişierul de intrare pictura.in conţine pe prima linie numerele N şi M. Pe fiecare din următoarele N linii se află câte M numere întregi care descriu matricea lui Mitruţ.
Date de ieşire
Fişierul de ieşire pictura.out conţine pe prima linie numărul K de culori folosite. Următoarele K linii cuprind fiecare câte 3 numere. Linia i+1 conţine numerele Zi, Di şi Ii separate prin spaţii.
Restricţii
• 1 ≤ N,M ≤ 1000
Exemplu
| pictura.in | pictura.out |
|---|---|
| 6 6 3 3 0 1 0 1 0 3 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 1 2 2 0 1 1 1 0 2 2 0 0 0 | 3 2 3 1 1 2 0 1 1 0 |
Explicaţie
Sunt 3 culori în matricea dată:1, 2 şi 3.
Culoarea 1 apare în două zone, din care în una se auto-intersectează o dată şi îşi schimbă direcţia de trei ori, iar în cealaltă deloc.
Culoarea 2 apare într-o singură zonă şi îşi schimbă direcţia de două ori.
Culoarea 3 apare şi ea doar într-o zonă. Direcţia ei este schimbată o singură dată.
