== include(page="template/taskheader" task_id="xcabluri") ==
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.
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ă dacă întinde cablurile unele dintre ele se vor intersecta şi nu va mai putea să le scoată aşa de uşor. Din cauza asta ea vrea să afle pentru fiecare cablu cu câte cabluri se intersectează dacă acestea sunt întinse. Cu toate că ea stă foarte rău cu orientarea în spaţiu ea a reuşit să alcătuiască o hartă a cablurilor sub formă de matrice bidimensională.
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$ 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$).
Fişierul de intrare $xcabluri.in$ conţine pe prima linie $N$ şi $M$ dimensiunile matricei. Pe următoarele $N$ linii se află câte $M$ numere care reprezintă aşezarea cablurilor. $0$ reprezintă un spaţiu gol iar numerele reprezintă cabluri.
h2. Date de ieşire
Î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.
În fişierul de ieşire $xcabluri.out$ se vor afla $x$ numere separate prin spaţii reprezentând numărul de cabluri cu care se intersectează fiecare cablu aşezate în ordinea cablului.
h2. Restricţii
* $1 ≤ N, M ≤ 100$
* $1 ≤ X ≤ N$
* În configuraţia iniţială oricare două cabluri nu vor ocupa aceeaşi coordonată.
* $1 ≤ N,M ≤ 100$
* Un cablu începe pe coloana $1$ şi se termină pe coloana $M$.
* În configuraţia iniţială cablurile nu se vor suprapune.
* Un cablu poate continua pe linia de deasupra, pe aceeaşi linie sau pe linia de dedesupt şi pe coloana următoare.
* $1 ≤ indicele unui cablu ≤ N$
h2. Exemplu
table(example). |_. xcabluri.in |_. xcabluri.out |
|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
3 3 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 3 2 0 0 0 0 0 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
2 0 0 0 3 1 2 0 2 1 1 1 1 1 1
4 0 0 1 1 3 3 2 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
