Olympiade départementale d'informatique | paralele

Avem o matrice de dimensiuni $N \cdot M$, cu elemente $0$ și $1$. Numim segment o secvență de cel puțin două valori $1$ aflate una lângă alta, toate pe aceeași linie, sau toate pe aceeași coloană a matricei.

Cerință

Se cere determinarea numărului de perechi de segmente:

1. aflate pe linii distincte ale matricei;
2. aflate pe coloane distincte ale matricei;

Date de intrare

Fișierul paralele.in conține pe prima linie, separate prin câte un spațiu trei valori naturale, în ordine: $T, N$ și $M$. Dacă $T$ este $1$ se rezolvă doar cerința $1$, iar dacă $T$ este $2$ se rezolvă doar cerința $2$.
Începând cu linia a doua se află elementele matricei, o linie a matricei pe o linie a fișierului. Elementele de pe aceeași linie se separă prin câte un spațiu.

Date de ieșire

Fișierul paralele.out conține pe prima linie un număr natural reprezentând valoarea cerută.

Restricții și precizări

• $1 \leq T \leq 2$;

Exemplu

paralele.in

1 5 6
0 1 1 1 0 0
1 0 0 0 0 0
0 0 0 1 0 0
1 1 0 1 1 0
0 1 1 0 0 0

paralele.out

11

Explicație

Prima valoare din fișierul de intrare fiind $1$, ne interesează segmente formate pe linii. Pe prima linie este o secvență de valori $1$ formată din trei elemente. Ea produce trei segmente: cel cu primele două valori de $1$, cel cu ultimele două valori de $1$ și cel cu toate cele trei valori de $1$. Pe linia a doua nu se găsește niciun segment, nefiind cel puțin două valori 1 alăturate. Pe linia a treia nu se găsește niciun segment, pe linia a patra sunt două segmente iar pe linia a cincea este un singur segment.

Numărul cerut se obține astfel: fiecare dintre cele trei segmente de pe prima linie este paralel cu fiecare dintre segmentele de pe a patra și de pe a cincea linie iar segmentele de pe linia a patra sunt paralele cu segmentul de pe ultima linie. Pentru exemplul prezentat, dacă am fi avut $T = 2$ rezultatul calculat ar fi trebuit să fie $1$ (segmentul de pe coloana a doua este paralel cu segmentul de pe coloana a patra).