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

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


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

Vasile lucrează într-o parcare. Sarcina lui este să scoată maşinile clienţilor din parcare.
Terenul de parcare este dreptunghiular, format din nxm zone identice, aranjate pe n linii şi m coloane. Liniile sunt numerotate de la 1 la n, iar coloanele de la 1 la m. Ieşirea din parcare este în colţul parcării cu coordonatele (1,1).
În fiecare zonă se poate afla o maşină, un stâlp sau poate fi liberă. Parcarea este plină, singura zonă liberă fiind ieşirea din parcare. Prin urmare, este foarte complicat să scoţi o maşină din parcare. Pentru a-şi face loc, Vasile poate muta o maşină din zona în care este plasată în una dintre zonele învecinate, dacă aceasta este liberă.
Evident, stâlpii nu pot fi mutaţi, doar maşinile.
Două zone sunt învecinate dacă se află pe aceeaşi linie pe coloane consecutive sau pe aceeaşi coloană, pe linii consecutive.

Cerinţă

Scrieţi un program care să determine numărul minim de mutări de maşini pe care trebuie să le execute Vasile pentru a scoate o maşină din parcare, dacă acest lucru este posibil.

Date de intrare

Fişierul de intrare valet.in conţine pe prima linie numerele naturale n şi m separate prin spaţiu. Urmează n linii fiecare conţinând câte m caractere din mulţimea {'.', '#', 'c', 'X'}.
Caracterul '.' indică zona liberă.
Caracterul '#' indică un stâlp.
Caracterul 'c' indică o maşină parcată.
Caracterul 'X' indică maşina pe care Vasile trebuie să o scoată din parcare.
În fişierul de intrare există un singur caracter 'X' şi un singur caracter '.', plasat în colţul (1,1) al parcării.

Date de ieşire

Fişierul de ieşire valet.out va conţine o singură linie pe care va fi scris numărul minim de mutări pe care trebuie să le efectueze Vasile pentru a scoate maşina din parcare, dacă acest lucru este posibil. În caz contrar pe prima linie se va scrie cuvântul imposibil.

Restricţii

  • 1 ≤ n, m ≤ 50

Exemple

valet.in valet.out valet.in valet.out
3 3
.#X
ccc
c#c


imposibil
2 3
.cX
ccc



7

Explicaţie
Cele 7 mutări din al doilea exemplu sunt:
(1,2) ->(1,1)
c.X
ccc
(1,3)->(1,2)
cX.
ccc
(2,3)->(1,2)
cXc
cc.
(2,2)->(2,3)
cXc
c.c
(2,1)->(2,2)
cXc
.cc
(1,1)->(2,1)
.Xc
ccc
(1,2)->(1,1)
X.c

ccc

prof. Emanuela Cerchez
Colegiul Naţional "Emil Racoviţă" Iaşi
emanuela.cerchez@gmail.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2011: ore, pegals, xpn, efect, nrperm, b2k, sumdivprod, nr0, maxviz, oneton, oras1, ksecv, ripstick, antic, oak, nor, nrpomi, sumprod, paisprezece, cover1, prisme, gxor, progresii, anagramabil, zuma, nrpal, sdmin, lista, operatii1, codarb, codpatrat, adprod, puncte4, qtri, reconst, gsm, subsiruri, mijloc, trifoi, cubulete, romb, maxbin, albine2, probleme, triburi1, megascoala
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, 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, 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, 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, oras1, gheizere, zone, taxa, abq, cartite, joc21, traseu3, panda, expand
Despre Lee: inginer, insule, lbd, ocean14, iepuras2, sah, radio, lacuri, castel, excursia, soricel2, masina2, paianjen, suma2, soricel3, cub2, alee, rj, taxe1, sotron1, tom, ny, ai, robot3, pixy, oras1, maxtri, lgdrum, gheizere, abq, cartite, joc21, traseu3, wow, panda
Software recomandat
surse trimise | ajutor