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

Poveste şi cerinţă...

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

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

În fişierul de ieşire $pictura.out$ ...

h2. Restricţii

* $1 ≤ N, M ≤ 1000$

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

h2. Exemplu
table(example). |_. 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

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

|
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