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

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


Timp maxim de execuţie / test:
0.2s
Memorie totala disponibilă / stivă:
16MB / 8MB

Scooby-Doo, celebrul personaj de desene animate, a intrat iar în bucluc. Acesta se găseşte acum într-o cameră dreptunghiulară de dimensiuni n x m alcătuită din celule pătratice de latură 1, divers colorate.
Se definesc :
Zonă - un grup cu număr maxim de celule de aceeaşi culoare, adiacente pe linie sau pe coloană.
SUPERZONA - o mulţime A de zone, cu proprietatea că fiecare are cel puţin k zone vecine aflate în aceeaşi mulţime A.
Pentru a fi în siguranţă, Scooby-Doo trebuie să se adăpostească într-o SUPERZONĂ cu număr maxim de celule.

Cerinţă

Părăsit de prietenii săi, Scooby-Doo nu se descurcă de unul singur şi vă roagă pe voi să rezolvaţi misterul şi să calculaţi numărul de celule ale celei mai mari SUPERZONE din matrice.

Date de intrare

Fişierul de intrare zone.in conţine pe prima linie numerele naturale n m k, separate prin câte un spaţiu. Pe următoarele n linii se află câte m caractere, fără spaţii între ele, reprezentând culorile celulelor din matrice.

Date de ieşire

Fişierul de ieşire zone.out va conţine pe prima linie un număr natural ce reprezintă numărul de celule ale celei mai mari SUPERZONE din matrice.

Restricţii

2 ≤ n, m, k ≤ 300
• Culorile sunt reprezentate prin litere mici ale alfabetului englez (′a′ - ′z′)
• Două celule se consideră adiacente dacă au o latură comună
• Două zone se consideră vecine dacă au cel puţin câte o celulă adiacentă.

Exemple

zone.inzone.outExplicaţii
4 3 2 aaa bad baa cda 11 Este selectată toată matricea fără zona formată din litera ′d′ de pe ultima coloană.

autor: Andrei Ciocan
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Probleme recomandate
De la ONI 2013: split, momente, gradina1, secvente2, flori2, romb1, cumpanit, spider, taxa, ausoara, drumuri2, confuzie, xnumere, bemo, aranjare2, showroom, cntgcd
De acelaşi autor: amedie, cutie1
Despre coada: balanta, inginer, camp, rebus, harta, insule, volei, lbd, magic3, axa, cadere, reinvent, ocean14, iepuras2, sah, balls, cd, toys, radio, caini, subperm, castel, excursia, casute, soricel2, masina2, salvare, paianjen, suma2, garaj, alee, lanterna, rj, caraibe, taxe1, sotron1, lanturi, tom, k1, dreptunghiuri, sokoban, ny, oldest, drumuri1, alpinist, tsunami, robot3, joc19, valet, oras1, gheizere, taxa, abq, cartite, joc21, traseu3, panda, expand
Despre matrice: vopsea, harta, opmat, sarpe, 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, 2ndesc, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
Despre fill: rebus, sarpe, insule, lacuri, zuzu, joc11, gradina, dreptunghiuri, drenaj, fillmat, parcela, acces, tsunami, betasah, zona, taxa, foto, ferma1, antitero, robotzi
surse trimise | ajutor