ultima problemă
grupă: micăsursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
sarpe
Timp maxim de execuţie/test:
0.1
secunde
Memorie totală disponibilă/stivă:
16MB/1 MB
Sa
consideram o matrice cu n linii
si m coloane cu elemente din
multimea {0 , 1 }.
sarpe este o succesiune de elemente ale matricei cu urmatoarele
proprietati:1 .maximal daca nu putem adauga un 1 la unul dintre capetele
sale fara a mari lungimea sarpelui, a combina doi serpi obtinand unul singur
sau fara a incalca proprietatea 2.
In
figura urmatoare sunt ilustrate 3 configuratii. Prima contine un singur sarpe
maximal, a doua nu contine nici un sarpe maximal, iar a treia contine 3 serpi
maximali.
Cerinta
Date
de intrare Fisierul de intrare sarpe.in
contine pe prima linie doua numere naturale n
si m separate prin spatiu, cu
semnificatia din enunt. Pe fiecare dintre urmatoarele n
linii se afla cate m caractere
('0 ' sau '1 ')
reprezentand elementele matricei.
Date
de iesire Fisierul de iesire sarpe.out
va contine o singura linie pe care va fi afisat un numar natural reprezentand
numarul de serpi maximali determinat.
Restrictii
1
<= n, m <= 200
Exemplu
sarpe.in
sarpe.out sarpe.in sarpe.out sarpe.in sarpe.out
7 10
1 7
10 0 7
10 3
prof. Emanuela Cerchez Grigore Moisil " Iasi
Articole recomandate
Probleme recomandate
De la Finala .campion 2009 : autobuze , mere , circuit , cadou , kpal , sumdif , chimie , ff De acelaşi autor : premii , finala , fractii , trei , manevre , nrcuv , an , vopsea , opmat , tramvai , bipal , kpal , replace , factori , barca , perechi , grupe , cod , reactii , factura , decript , trenuri , holo , cifre , firma , tribile , mesaj , tricouri , pajura , monede , programs , fry , repeat , red , pavaj , bacan , nrbinar , invest , cutie2 , loc , depou , nr3 , zid , felinare , sir3 , sqr , carte , labirint , stea , count , evaluare , super , schimb , zaruri , vectori , spirala , desen1 , rima , ceas1 , romane , sms , bac , excursia , joc7 , furnici , munte1 , cezar , marcare , excursie1 , culmi , sume1 , schi , nr4 , fractie , cod3 , medii , tren3 , top , sant1 , imagine , ocr , perfect , pluton , reforma , alee , ceas2 , paritate , borcane , aranjare , comoara1 , culmi1 , reactivi , submult , sablon1 , sir8 , sume2 , dansatori , smith , tom , matriosca , asociativ , control1 , calorii , immortal , concat , mat , cubinvers , mine , divizori , cheie , stelar , joct , minmax , cladire , adunscad , razboi , ore , oras1 , sumprod , prisme , operatii1 , lgdrum , unupatru , chibrituri , extraprime , prieten , rebus1 , grindina , opmult , betisoare , antitero , clase , pagini , ornament , ordine , spioni1 Despre recursivitate : tren , mere , chimie , soldati , formule , infinit , compress , ploaia , cartoane , sub , metro , windows , lacuri , apel , maxq , pav , joc11 , paianjen , suma2 , monkey , csir , lsort , imagine , dir , desert , echitabil , rez , logic , gradina , links , dreptunghiuri , expresie1 , cumpanit , reziston , antitero , sablon3 Despre matrice : vopsea , harta , opmat , light , magic2 , tetris , origami , concurs , iepuras , tribile , criptmat , cutie , patrate , 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 Despre fill : rebus , insule , lacuri , zuzu , joc11 , gradina , dreptunghiuri , drenaj , fillmat , parcela , acces , tsunami , betasah , zona , zone , taxa , foto , ferma1 , antitero , robotzi
