Fișierul intrare/ieșire patrate.in, patrate.out Sursă .campion 2007
Autor Sergiu Corlat Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.1 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in patrate.out
4
0 1 0 0
0 0 1 1
1 0 0 0
0 1 1 1
1

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii