Fişierul intrare/ieşire:pictura.in, pictura.outSursăTiberiu Popoviciu 2011, Clasa a 9-a
AutorPerticas CatalinAdăugată deperticas_catalinperticas catalin perticas_catalin
Timp execuţie pe test0.325 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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ă în care apare culoarea respectivă) ş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.inpictura.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ă.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content