.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » patrate

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
patrate


Timp maxim de executie/test:
0.2 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

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

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2007: perechi, teanc, index, light, copaci, teren, pizza, grupe, cod, ecran, drum, soldati, factura, palma, decript, lbd, aven, cs, h, trenuri, sort, spam, complex, parent, holo, tren2, gray, siruri, arce, pasi, cifre, mgo, firma, joc, cartonase, vikingi, anagrame, balbe, vecini, balaur, tribile, conflicte, criptmat, mesaj, maxim, magic3, desen, plimbare, cutie, party, vagoane, robot, astre, trains, numere2, friends, tricouri, furtuna, net, baby, scaune, 3d, axa, bile2, vmem, pahare, termen, sablon, zapada, cuvinte, excursie, hd, pajura, pc, sir, cadere, pioni
De acelaşi autor: nice, fib, atac, mere, ff, astre, baby, zapada, pendul, unu, dragon, placi, druid, bete, comori, ploaia, lot, arcas, factk, robot1, kalah, cetati, palc, expo, porumb, universitate, safeu, capra, zuma, gsm, megascoala
Despre geometrie: forum, supertri, ozn, detinut, atac, afise, mere, ff, teren, volei, aven, robot, pahare, pendul, robot2, dragon, poligon, druid, laser, patrate3, ploaia, donald, lot, atac1, arcas, paralel, dotnet, aedaro, vectori, spirala, distanta, triunghi, center, harta1, seceta, antena, poligon1, benzina, zoo, texan, oypara, dreptc, mosia, sea, poligon3, poligon2, snipers, basm, cetati, placa, nori, cerc, smin, cern, cuiburi, acerc, select, proiect, poligon4, terenuri, monoton, acoperire, capra, testament, jb, sdmin, ozn1, parc1, gsm, triunghi5, puncte6, romb1, dreapta, grindina, tdrept
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, erdos, grup, scor2, reteta2, rezervatie, scoici, tablou, game, stea, submatrix, cifru, jokes, oua, trecere, na, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, camion, ceas1, fibo, parc, excursia, matricea, zidar, joc6, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, soricel2, avere, joc11, vizibil, sah1, blockout, masina3, lsort, anticip, matrice1, evantai, spion, pereti, zumzi, roboti, placare, tabel, ocr, numere7, lacusta, becuri, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, iepurasi, colorare, mat, submatrix1, simetric1, plaja, xor2, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, sir9, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
surse trimise | ajutor