Sa consideram o retea formata din puncte NxN puncte având coordonate întregi. Distanta dintre oricare doua puncte vecine pe orizontala sau verticala este 1. Unele noduri ale retelei sunt albe, altele sunt negre.
Utilizand drept colturi puncte ale retelei avand aceeasi culoare, se pot forma patrate.
De exemplu, pentru reteaua 4 × 4, din figura 1 exista un singur patrat (figura 2).

Figura 1                                                                Figura 2
Vom numerota liniile retelei de la 1 la N de sus in jos, iar coloanele retelei de la 1 la N de la stanga la dreapta. Astfel fiecare punct din retea poate fi identificat prin doua coordonate: linia si coloana pe care se afla.

Cerinta
Scrieti un program care sa determine pentru o anumita configuratie data numarul de patrate se pot forma având ca vârfuri puncte ale retelei de aceeasi culoare.

Date de intrare
Fisierul de intrare patrate.in contine pe prima linie un numar natural N - dimensiunea retelei. Urmatoarele N linii contin câte N numere din multimea {0, 1} separate prin cate un spatiu si descriu reteaua. Daca punctul cu coordonatele (i, j) este de culoare alba, atunci elementul j din linia i+1 este 0, iar daca e de culoare neagra - atunci 1.

Date de iesire
Fisierul de iesire patrate.out va contine o singura linie pe care va fi scris un singur numar natural reprezentand numarul de patrate se pot forma având ca vârfuri puncte ale retelei de aceeasi culoare.

Restrictii
2 <= N <= 50

Exemplu

Timp maxim de executie/test: 0.2 secunde

prof. Sergiu Corlat
Liceul Moldo-Turc Chisinau
Contact:scorlat@gmail.com