banda

Într-o matrice pătratică având toate elementele egale cu $0$ sau $1$, definim segmentul complet ca fiind un segment de dreaptă cu extremităţile pe conturul matricei.

• Segmentul complet de rang $1$ este format dintr-o linie a matricei având toate elementele egale cu $1$.
• Segmentul complet de rang $2$ este format dintr-o coloană a matricei având toate elementele egale cu $1$;
• Segmentul complet de rang $3$ este format dintr-o semidiagonală a matricei, paralelă cu diagonala principală (inclusiv aceasta) şi având toate elementele egale cu $1$;
• Segmentul complet de rang $4$ este format dintr-o semidiagonală a matricei, paralelă cu diagonala secundară (inclusiv aceasta) şi având toate elementele egale cu $1$;

Două sau mai multe segmente alăturate de acelaşi tip formează o bandă de acelaşi rang cu acestea.

Cerinţă

Fiind dată o matrice binară $n$, să se determine banda maximă a matricei. Dacă există mai multe astfel de benzi, se va afişa cea de rang maxim ($4$ > $3$ > $2$ > $1$), iar dintre acestea, cea cu suma indicilor elementelor maximă.

Date de intrare

Fişierul de intrare banda.in conţine pe prima linie valoarea $n$ reprezentând numărul de linii; pe fiecare din următoarele $n$ linii se vor memora elementele unei linii, separate prin spaţii.

Date de ieşire

Fişierul de ieşire banda.out va conţine pe primul rând rangul benzii, pe al doilea rând numărul de segmente complete ce formează banda, pe a treia linie numărul de elemente din bandă.

Restricții și precizări

• $0 < n \leq 1 \ 000$;
• Se garantează existența unei benzi în fiecare test.

Exemplu

banda.in

10
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1 1 0
0 0 0 0 1 1 1 1 1 0
0 0 0 1 1 1 1 1 0 0
0 0 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 1 1 0 1 1 1 1 1 1
1 1 1 0 1 0 1 0 0 1

banda.out

3
3
24

Explicație

Matricea conţine:

• rang $1$: $2$ benzi cu câte $2$ drepte şi $20$ valori $1$;
• rang $3$: $2$ benzi cu $3$ drepte şi $24$ valori $1$, respectiv $2$ drepte şi $3$ valori $1$;
• rang $4$: o bandă cu $2$ drepte şi $19$ de $1$, respectiv una cu $2$ drepte şi $3$ de $1$.

Banda maximă are rangul $3$, conţine $3$ drepte şi are $24$ valori 1.