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

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


Timp maxim de execuţie/test:
0.2 secunde
Memorie totala disponibilă/stivă:
32 MB/1 MB

Făt-Frumos a plecat din nou să salveze o frumoasă fată de împărat. În ţara pe care o traversează se află ape şi munţi şi păduri şi câmpii. Harta ţării poate fi reprezentată ca o matrice cu N linii şi M coloane, elementele matricei fiind:
c - dacă elementul reprezintă o porţiune de câmpie
a - dacă elementul reprezintă o zonă acoperită cu apă
m - dacă elementul reprezintă o zonă muntoasă
p - dacă elementul reprezintă o zonă împădurită.
Iată un exemplu de hartă:

ccccaaaaamcccccccccc
ccccaaaaamccccmmmmcc
cccaaaaamccccccccmcc
cccaaaamcccccccccmcc
cccaaaamcccmmpppcmcc
cccaaaaaaaacmppppmcc
cccaaaaaaaammmppmccc
cccaaaaaaaaccmppmppp
ccccaaaaaaamcmccmppp
mmmmmmmmcccmcmppmppp
cccccccccccmcmpppmpp
cccccccccccmcmcccmpp
ccmmmmmmmmmmcmcccmpp
ccmccccccccmcmcccmpp
ccccmccccccmcmcccccc
ccccmccccccccmcccccc

Făt-Frumos se află în colţul stânga-sus al hărţii (elementul de pe linia 1 şi coloana 1) şi trebuie să ajungă în colţul din dreapta-jos (elementul de pe linia N şi coloana M), unde se află fata de împărat. În colţul stânga-sus şi colţul dreapta jos se află zone de câmpie.
La un pas, Făt-Frumos se poate deplasa din elementul curent în unul dintre cele 4 elemente învecinate sus, jos, stânga, dreapta.
Făt-Frumos nu ştie să înoate (deci nu poate trece prin apă), îi este frică de vietăţile pădurii (deci nu va trece prin păduri), iar condiţia fizică nu îi permite să treacă prin munţi.
Pentru a-l ajuta pe Făt-Frumos tu poţi construi cel mult K poduri şi poţi incendia cel mult L păduri.
Podurile pot fi doar orizontale sau verticale, pot trece doar peste ape, pot avea orice lungime şi trebuie să fie complete (adică extremităţile podului nu pot fi în apă, podul trebuie să traverseze întreaga secvenţă de elemente consecutive pe linie/coloană acoperită de apă).
Făt-Frumos se poate urca pe un pod doar pe la unul dintre capetele podului, iar odată urcat pe pod trebuie să îl parcurgă în întregime. Pentru a urca pe un pod orizontal Făt Frumos trebuie să se afle pe linia pe care este construit podul, la unul dintre capete (la capătul din stânga se poate urca deplasându-se doar spre Est, adică din celula de pe aceeaşi linie, coloana precedentă; la capătul din dreapta al podului orizontal el se poate urca doar deplasându-se spre vest, adică din elementul situat pe aceeaşi linie, coloana următoare). Pentru a urca pe un pod vertical Făt Frumos trebuie să se afle pe coloana pe care este construit podul, la unul dintre capete (pentru capătul de sus el se deplasează spre Sud, pentru capătul de jos, el se deplasează spre Nord). Coborârea de pe pod se face pe linia (pentru pod orizontal), respectiv coloana (pentru pod vertical) pe care se află podul, pe poziţia la care se termină podul.
Podurile nu se pot intersecta, dar dacă este necesar podurile pot fi construite unul deasupra celuilalt (astfel încât nu se poate trece de pe un pod pe altul).

O pădure este o zonă maximală formată numai din elemente împădurite (cu valoarea p) astfel încât între oricare două elemente din aceeaşi pădure se poate ajunge prin mişcări de tipul celor descrise mai sus, trecând doar prin elemente împădurite. Incendierea unei păduri va determina eliminarea sa de pe hartă (integral).

Cerinţă

Scrieţi un program care determină podurile ce trebuie să fie construite şi pădurile ce trebuie să fie arse astfel încât Făt-Frumos să poată ajunge la fata de împărat.

Date de intrare

Fişierul de intrare camp.in contine pe prima linie numerele naturale separate prin spatiu N M separate prin spaţiu. Pe cea de a doua linie se află numerele naturale K şi L, separate prin spaţiu. Pe următoarele N linii se află câte M caractere din mulţimea {'c','a','m','p'}, reprezentând harta ţării.

Date de ieşire

Fişierul de ieşire camp.out va conţine harta, după construirea podurilor şi incendierea pădurilor. Un segment de pod orizontal va fi reprezentat prin caracterul - (minus), un segment de pod vertical prin caracterul |, iar un element traversat de două poduri suprapuse va conţine caracterul + (plus). Elementele în care se află păduri arse vor conţine caracterul c (ca şi câmpiile).

Restricţii

  • 1 ≤ M, N ≤ 50
  • 1 ≤ K, L ≤ 10
  • Pentru datele de test va exista întotdeauna soluţie, nu neapărat unică.

Exemple

camp.in camp.out
16 20
2 1
ccccaaaaamcccccccccc
ccccaaaaamccccmmmmcc
cccaaaaamccccccccmcc
cccaaaamcccccccccmcc
cccaaaamcccmmpppcmcc
cccaaaaaaaacmppppmcc
cccaaaaaaaammmppmccc
cccaaaaaaaaccmppmppp
ccccaaaaaaamcmccmppp
mmmmmmmmcccmcmppmppp
cccccccccccmcmpppmpp
cccccccccccmcmcccmpp
ccmmmmmmmmmmcmcccmpp
ccmccccccccmcmcccmpp
ccccmccccccmcmcccccc
ccccmccccccccmcccccc
ccccaaaaamcccccccccc
ccccaaaaamccccmmmmcc
cccaaaaamccccccccmcc
cccaaaamcccccccccmcc
cccaaaamcccmmpppcmcc
cccaaaaaa|acmppppmcc
cccaaaaaa|ammmppmccc
ccc------+-ccmppmccc
ccccaaaaa|amcmccmccc
mmmmmmmmcccmcmppmccc
cccccccccccmcmpppmcc
cccccccccccmcmcccmcc
ccmmmmmmmmmmcmcccmcc
ccmccccccccmcmcccmcc
ccccmccccccmcmcccccc
ccccmccccccccmcccccc

prof. Emanuela Cerchez
Liceul de Informatică „Grigore Moisil” Iaşi
emanuela.cerchez@gmail.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2008: celule, premii, cai, scp, forum, vedete, film, finala, ab, nice, supertri, mod3, degrade, fractii, balanta, inginer, ozn, hora, trei, rebus, sl, detinut, fbr, noroc, simetric, egal, manevre, connect3, gropi, nrcuv, ruleta, carti, pod, bonuri, tgv, fib, uscat, 2sir, atac, matrice2, zeratul, afise, an, dezbateri, test, miniasm, platforma, lac, vopsea, harta, nrbun2, barfa, nrbun, bunici, opmat, acop, tren, cub, picnic, cursa, rv, compus, comun, magic, votare, onu, tramvai, bipal, nspecial, retea, secvop
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, 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, lbd, 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, 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, zone, taxa, abq, cartite, joc21, traseu3, panda, expand
Software recomandat
surse trimise | ajutor