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

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


Timp maxim de execuţie / test:
2s
Memorie totala disponibilă / stivă:
64MB / 1MB

Depozitul cu safeuri personale a băncii Gringotts Ltd are forma unui dreptunghi cu laturile n × m, divizat în n × m platforme pătrate de dimensiunea 1 × 1. Unica platformă liberă este în colțul din stânga sus. Ea marchează ieșirea din depozit. Unele dintre platforme sunt ocupate cu echipamente de supraveghere montate rigid, pe celelalte se află câte un safeu, care are dimensiunea platformei. În unul din safeuri se păstrează Piatra Filozofală. La cererea lui Dumbledore, spiridușii trebuie să scoată din depozit safeul cu Piatra Filozofală. Unica operație pe care o pot efectua ei este deplasarea unui safeu pe o platformă vecină, dacă aceasta este liberă. Se consideră vecine platformele care au o latură comună.

Cerinţă

Scrieți un program care să determine numărul minim de operații necesare pentru a scoate safeul cu Piatra Filozofală din depozit. Safeul se consideră scos din depozit dacă este adus pe platforma de la intrarea în depozit.

Date de intrare

Prima linie a fișierului de intrare safeu.in conține două numere n și m, dimensiunile depozitului. Urmează n linii a câte m simboluri fiecare. Simbolul “.” marchează poziția liberă. Unica poziție liberă este la intrarea în depozit. Simbolul “#” marchează o platformă cu echipament de supraveghere. Platformele cu echipamente de supraveghere nu pot fi deplasate și pe ele nu se plasează safeuri. Simbolul “c” semnifică o platformă cu safeu. Simbolul “X” – platforma pe care se află safeul cu Piatra Filozofală.

Date de ieşire

Dacă safeul nu poate fi scos din depozit, în fișierul de ieșire safeu.out se va înscrie un singur cuvânt Impossible. În caz contrar, unica linie a fișierului va conține un singur număr – numărul minim de operații necesar pentru scoaterea safeului indicat din depozit.

Restricţii

1N, M50.
1 < N sau 1 < M.
Fiecare dintre simbolurile “.” și “X” apar câte o singură dată.
Simbolul “.” este întotdeauna amplasat în colțul din stânga sus al depozitului.

Exemple

safeu.insafeu.out
3 3 .#X ccc c#c Impossible
2 3 .cX ccc 7

autor: Prof. Sergiu Corlat
propunător: Stud. Vlad Manea
FII
vlad.c.manea@gmail.com
Articole recomandate
Probleme recomandate
De la FII Competition 2011: lipsa, reducere, viena, sir9, sablon2, fibgcd, acoperire, razboi, centrala, benzina2, bradut2, capra, agendatelefonica, cds, micro, wg
De acelaşi autor: nice, fib, atac, mere, ff, patrate, astre, baby, zapada, pendul, unu, dragon, placi, druid, bete, comori, ploaia, lot, arcas, factk, robot1, kalah, cetati, palc, expo, porumb, universitate, capra, zuma, gsm, megascoala
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, 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, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
Despre simulare: lbd, iepuras, tren2, mgo, joc2, kafka, comori, loc, bile3, cat, felinare, spioni, lift, kalah, cutii, roboti, pesti, zar1, joc16, joc20, dame, conjectura, arc, wb, robot6
surse trimise | ajutor