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

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}.
Se numeste sarpe este o succesiune de elemente ale matricei cu urmatoarele proprietati:
1. toate elementele ce constituie un sarpe au valoarea 1.
2. orice element al sarpelui (exceptand primul si ultimul) se invecineaza cu exact 2 alte elemente ale sarpelui (la Nord, Sud, Est sau Vest).
Un sarpe se numeste 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
Scrieti un program care sa determine pentru o configuratie data numarul de serpi maximali.

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
1111111110
0000000010
1100000011
1011110001
1010010001
1010010111
1110011100
1 7 10
1111111110
0000000010
0001010011
1011010001
1010010001
1010010111
1110011100
0 7 10
1011111110
0100000010
1101011011
1011010001
1010010001
1010010111
1110011100
3

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
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
surse trimise | ajutor