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
patrate.in
patrate.out
4
0 1 0 0
0 0 1 1
1 0 0 0
0 1 1 1
1
prof. Sergiu Corlat
Liceul Moldo-Turc
Chisinau
Contact:scorlat@gmail.com
