Fișierul intrare/ieșire	patrate.in, patrate.out	Sursă	.campion 2007
Autor	Sergiu Corlat	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.1 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	2

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Pătrate

Să considerăm o rețea formată din NxN puncte având coordonate întregi. Distanța dintre oricare două puncte vecine pe orizontală sau verticală este 1. Unele noduri ale rețelei sunt albe, altele sunt negre. Utilizând drept colțuri puncte ale rețelei având aceeași culoare, se pot forma pătrate.

De exemplu, pentru rețeaua 4 × 4, din figura din stânga există un singur pătrat, ilustrat în figura din dreapta.

Vom numerota liniile rețelei de la 1 la N de sus în jos, iar coloanele rețelei de la 1 la N de la stânga la dreapta. Astfel fiecare punct din rețea poate fi identificat prin două coordonate: linia și coloana pe care se află.

Cerință

Scrieți un program care să determine pentru o anumită configurație dată numărul de pătrate ce se pot forma având ca vârfuri puncte ale rețelei de aceeași culoare.

Date de intrare

Fișierul de intrare patrate.in conține pe prima linie un număr natural N – dimensiunea rețelei. Următoarele N linii contin câte N numere din mulțimea {0, 1} separate prin câte un spațiu și descriu rețeaua. Dacă punctul cu coordonatele (i, j) este de culoare albă, atunci elementul j din linia i+1 este 0, iar dacă e de culoare neagră – atunci 1.

Date de ieșire

Fișierul de ieșire patrate.out va conține o singură linie pe care va fi scris un singur număr natural reprezentând numărul de pătrate ce se pot forma având ca vârfuri puncte ale rețelei de aceeași culoare.

Restricții

• 2 ≤ N ≤ 50

Exemplu