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

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


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

Pe un lac se afla doua lebede, dar fiindca lacul este partial înghetat ele sunt separate de gheata.
Lacul are forma unui caroiaj dreptunghiular si consta din NxM patrate aranjate sub forma a N linii si M coloane. Unele dintre patrate sunt acoperite de gheata.
Lacul a început sa se dezghete treptat - într-o zi se dezgheata (se transforma în apa) toate patratele acoperite de gheata care ating apa (au o latura comuna cu un patrat reprezentând apa).
Figura urmatoare ilustreaza lacul din exemplu, apoi lacul dupa o zi, apoi lacul dupa doua zile:

Lebedele pot pluti numai pe apa, deplasându-se din patratul în care se afla într-un patrat învecinat pe orizontala sau verticala (nu si pe diagonala).

Cerinta
Scrieti un program care sa determine dupa câte zile se pot întâlni cele doua lebede.

Date de intrare
Fisierul de intrare lbd.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 câte M caractere din multimea {'.','X','L'}. Caracterul '.' (punct) reprezinta un patrat cu apa; caracterul X (litera X majuscula) reprezinta un patrat acoprit de gheata; caracterul 'L' reprezinta un patrat în care se afla o lebada.

Date de iesire
Fisierul de iesire lbd.out va contine o singura linie pe care va fi scris un singur numar natural, reprezentând numarul de zile dupa care cele doua lebede se pot întâlni.

Restrictii
1<=N, M <=1500

Exemple

lbd.in lbd.out

8 17
...XXXXXX..XX.XXX
....XXXXXXXXX.XXX
...XXXXXXXXXXXX..
..XXXXX.LXXXXXX..
.XXXXXX..XXXXXX..
XXXXXXX...XXXX...
..XXXXX...XXX....
....XXXXX.XXXL...

2

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi
Contact:emanuela.cerchez@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, 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, patrate, 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: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
Despre coada: balanta, inginer, camp, rebus, harta, insule, volei, 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, zone, taxa, abq, cartite, joc21, traseu3, panda, expand
Despre Lee: inginer, insule, ocean14, iepuras2, sah, radio, lacuri, castel, excursia, soricel2, masina2, paianjen, suma2, soricel3, cub2, alee, rj, taxe1, sotron1, tom, ny, ai, robot3, pixy, valet, oras1, maxtri, lgdrum, gheizere, abq, cartite, joc21, traseu3, wow, panda
Despre simulare: iepuras, tren2, mgo, joc2, kafka, comori, loc, bile3, cat, felinare, spioni, lift, kalah, cutii, roboti, pesti, zar1, joc16, safeu, joc20, dame, conjectura, arc, wb, robot6
Software recomandat
surse trimise | ajutor