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

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


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

Ana şi Bogdan au inventat un nou model de şotron. Ei desenează cu creta pe asfalt un caroiaj format din NxM pătrate organizate în N linii şi M coloane. O parte dintre aceste pătrate le colorează în roşu, celelalte în verde. În plus, un pătrat este selectat că pătrat de start şi un alt pătrat ca pătrat de final (acestea sunt verzi).
Scopul jocului este ca jucătorul să ajungă de la pătratul de start la pătratul final în cel mai scurt timp. Regulile jocului sunt:

  1. este interzis ca jucătorul să păşească într-un pătrat roşu; este permis să se deplaseze doar în cele verzi;
  2. atunci când jucătorul ajunge într-un pătrat el se poate deplasa în pătratul din faţa sa, în cel din stânga sa sau în cel din dreapta sa (faţa, stânga, dreapta sunt stabilite evident în funcţie de sensul de mers); prin urmare este interzis ca un jucător să se deplaseze înapoi sau în diagonală; de asemenea este interzis ca jucătorul să părăsească caroiajul;
  3. de-a lungul întregului drum de la start la final sunt permise în total cel mult K deplasări la dreapta;
  4. iniţial, când jucătorul este plasat în pătratul de start, el poate alege ce sens de deplasare doreşte;
  5. deplasarea de la un pătrat la altul durează o secundă.

Cerinţă

Scrieţi un program care să determine timpul minim necesar jucătorului pentru a ajunge din pătratul de start în pătratul final, respectând regulile din enunţ (dacă este posibil).

Date de intrare

Fişierul de intrare sotron1.in conţine pe prima linie trei numere naturale K N M, reprezentând numărul maxim de deplasări la dreapta, numărul de linii şi respectiv numărul de coloane ale şotronului. Pe următoarele N linii se află câte M numere din mulţimea {0, 1, 2, 3} cu următoarea semnificaţie:
0 reprezintă un pătrat verde
1 reprezintă un pătrat roşu
2 reprezintă pătratul de start (există un singur element 2)
3 reprezintă pătratul final (există un singur element 3).

Date de ieşire

Fişierul de ieşire sotron1.out va conţine o singură linie pe care va fi scris timpul minim necesar pentru a ajunge din pătratul de start în pătratul final, respectând regulile din enunţ. Dacă problema nu are soluţie, pe prima linie se va afişa valoarea -1.

Restricţii

  • 0 ≤ K ≤ 5
  • 2 ≤ N, M ≤ 20

Exemple

sotron1.in sotron1.out sotron1.in sotron1.out
1 3 4
0 0 2 0
0 1 1 0
0 0 3 0
6 0 3 4
2 0 0 0
1 1 1 0
3 0 0 0
-1

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 2009: efort, muzeu, bal, seti, basm, dansatori, smith, timer, secvsir, vot, cetati, reziduu, biliard, prefix1, accesibil, dp, jocv, placa, palc, prod3, predecesor, standard, cantor, nkbiti, nori, triti, kperms, impozit, tablite, fazan, lanturi, secvpar, tom, joker, matriosca, asociativ, lego, medalii, permutari, cfr, treegame, scanduri, site, fotbal, links, kbiti, segm, album, iepurasi, jucarii, m4, bradut, trmv, colorare, greutati, concat, graphgame, ic, echilibru, brazi, mat, cubinvers, mobil, distsir, parbit
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, 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, 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, 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, lbd, ocean14, iepuras2, sah, radio, lacuri, castel, excursia, soricel2, masina2, paianjen, suma2, soricel3, cub2, alee, rj, taxe1, tom, ny, ai, robot3, pixy, valet, oras1, maxtri, lgdrum, gheizere, abq, cartite, joc21, traseu3, wow, panda
Software recomandat
surse trimise | ajutor