Fişierul intrare/ieşire:patrate.in, patrate.outSursă.campion 2007
AutorSergiu CorlatAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.1 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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

patrate.inpatrate.out
4
0 1 0 0
0 0 1 1
1 0 0 0
0 1 1 1
1
Trebuie sa te autentifici pentru a trimite solutii. Click aici