Fişierul intrare/ieşire:	xcabluri.in, xcabluri.out	Sursă	Tabăra ICHB 2012, Ziua 2, Grupa 1
Autor	Dan Constantin Spatarel, Petru Trimbitas	Adăugată de	Dan-Constantin Spatarel •spatarel
Timp execuţie pe test	0.025 sec	Limită de memorie	5120 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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.

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

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

Date de ieşire

În fişierul de ieşire xcabluri.out se vor găsi X numere naturale separate prin spaţii: I₁, I₂, ..., 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.

Restricţii

• 1 ≤ N, M ≤ 100
• 1 ≤ X ≤ N
• În configuraţia iniţială oricare două cabluri nu vor ocupa aceeaşi coordonată.

Exemplu

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.

Cum se trimit solutii?