pictura

Pictura

== include(page="template/taskheader" task_id="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.

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)

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 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)

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

h2. 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ă).

Să se determine $K$, numărul de culori folosite, iar pentru fiecare culoare $i$, determinaţi numărul $Z{~i~}$ de zone în care apare, $D{~i~}$ de câte ori îşi schimbă direcţia (suma schimbăriilor de direcţie pentru fiecare zonă în care apare culoarea respectivă) şi $I{~i~}$ de câte ori se auto-intersectează (suma numărului de intersecţii pentru fiecare zonă).

h2. 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ţ.

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ţ.

h2. 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.

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 $Z{~i~}$, $D{~i~}$ şi $I{~i~}$ separate prin spaţii.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N, M ≤ 1000$

h2. Exemplu
table(example). |_. pictura.in |_. pictura.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 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

|
h3. 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ă.
 

== include(page="template/taskfooter" task_id="pictura") ==

5498