== include(page="template/taskheader" task_id="xcabluri") ==
Poveste şi cerinţă...
Deoarece a rămas fără fixativ, Ephie s-a gândit să apeleze la curentul care trece prin cablurile din spatele calculatorului pentru a-şi aranja părul. Totusi ea şi-a dat seama că chiar dacă întinde perfect cablurile, unele dintre ele se vor intersecta şi nu va mai putea să le scoată aşa de uşor. De aceea, ea vrea să afle pentru fiecare cablu în parte cu câte cabluri se intersectează dacă acestea sunt perfect întinse.
Cu toate că ea stă foarte rău cu orientarea în spaţiu, a reuşit să alcătuiască o hartă a cablurilor sub forma unei matrice bidimensională.
h2. Date de intrare
Fişierul de intrare $xcabluri.in$ ...
Fişierul de intrare $xcabluri.in$ conţine pe prima linie $N$ şi $M$ - numărul de linii respectiv numărul de coloane ale matricei alcătuită de Ephie. Pe fiecare din următoarele $N$ linii se află câte $M$ numere, reprezentând aşezarea cablurilor.
Ephie a marcat fiecare din cele $X$ cabluri ale sale cu câte un număr distinct, între $1$ şi $X$. Astfel, în matricea pe care v-a pus-o la dispoziţie se găsesc numere naturale pozitive, reprezentând traseul fiecăruia dintre cablurile sale şi $0$-uri, reprezentând spaţiile goale.
În matrice, orice cablu începe de pe coloana $1$, pentru ca în continuare să se continuă numai în dreapta-sus, dreapta sau dreapta-jos. Mai precis, dacă o porţiune a unui cablu se găseşte la coordonata $(i, j)$, atunci acesta se poate continua la una din coordonatele $(i - 1, j + 1)$, $(i, j + 1)$ respectiv $(i + 1, j + 1)$. Bineînţeles, orice cablu se termină pe coloana $M$.
Atunci când este perfect întins, un cablu ajunge să coincidă cu segmentul de dreaptă definit de punctele în care se află capetele sale (de pe coloanele $1$ şi $M$).
h2. Date de ieşire
În fişierul de ieşire $xcabluri.out$ ...
În fişierul de ieşire $xcabluri.out$ se vor găsi $X$ numere naturale separate prin spaţii: $I{~1~}, I{~2~}, ..., I{~X~}$, unde I{~i~} reprezintă numărul de cabluri cu care se intersectează cablul marcat cu numărul $i$, dacă toate cablurile sunt perfect întinse.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N, M ≤ 100$
* $1 ≤ X ≤ N$
* În configuraţia iniţială oricare două cabluri nu vor ocupa aceeaşi coordonată.
h2. Exemplu
table(example). |_. xcabluri.in |_. xcabluri.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|12 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 3 0 0 0 0 0 2 0 0 0 0 0 0 0
0 0 3 2 0 0 2 0 2 0 2 2 2 2 2
0 2 2 3 2 2 1 1 1 2 0 0 0 0 0
2 0 0 0 3 1 0 0 0 1 1 1 1 1 1
4 0 0 1 1 3 3 0 0 0 0 0 0 0 0
0 4 1 4 0 4 0 3 4 4 4 4 4 4 4
0 1 4 0 4 0 4 4 3 3 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 3 3 3 3 3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
| 2 1 3 2
|
h3. Explicaţie
...
Perechile de cabluri care se interectează după ce sunt perfect întinse sunt:
* 1 şi 3;
* 1 şi 4;
* 2 şi 3;
* 3 şi 4.
== include(page="template/taskfooter" task_id="xcabluri") ==
