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

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


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

Fie un labirint reprezentat ca o matrice pătratică cu n linii (numerotate de sus în jos de la 1 la n) şi n coloane (numerotate de la stânga la dreapta de la 1 la n). Elementele matricei pot fi 0 (semnificând culoar de trecere) sau 1 (semnificând zid). Un roboţel se mişcă prin labirint după un anumit traseu, specificat ca o succesiune de direcţii de mişcare. Direcţiile pot fi:
• N (nord), adică din poziţia curentă (x,y) robotul se deplasează în poziţia (x-1,y), dacă nu este zid
• S (sud), adică din poziţia curentă (x,y) robotul se deplasează în poziţia (x+1,y), dacă nu este zid
• E (est), adică din poziţia curentă (x,y) robotul se deplasează în poziţia (x,y+1), dacă nu este zid
• V (vest), adică din poziţia curentă (x,y) robotul se deplasează în poziţia (x,y-1), dacă nu este zid.
Observaţi că roboţelul nu poate trece prin ziduri, prin urmare, dacă în direcţia de mişcare curentă se află un zid, el nu va efectua deplasarea respectivă.

Cerinţă

Dată fiind configuraţia labirintului, poziţia iniţială a roboţelului şi traseul pe care se deplasează acesta, să se determine poziţia finală a robotului.

Date de intrare

Fişierul de intrare traseu2.in conţine pe prima linie numărul natural n, reprezentând dimensiunea labirintului. Pe cea de a doua linie sunt scrise două numere naturale L C (cuprinse între 1 şi n), reprezentând poziţia iniţială a roboţelului (L fiind linia, iar C fiind coloana). Pe următoarele n linii se află câte n valori din mulţimea {0,1}, reprezentând configuraţia labirintului. Pe ultima linie se află un şir de caractere din mulţimea {′N′, ′S′, ′E′, ′V′}, reprezentând traseul roboţelului.

Date de ieşire

Fişierul de ieşire traseu2.out va conţine o singură linie pe care vor fi scrise două numere naturale cuprinse între 1 şi n reprezentând linia, respectiv coloana poziţiei în care se află roboţelul după parcurgerea traseului. Dacă în timpul deplasării pe traseu roboţelul părăseşte labirintul, pe prima linie vor fi scrise linia, respectiv coloana ultimei poziţii pe care a avut-o roboţelul în labirint.

Restricţii

1 ≤ n ≤ 100
• Traseul are lungimea ≤ 250
• Valorile numerice scrise pe aceeaşi linie în fişierul de intrare şi în fişierul de ieşire vor fi separate prin câte un spaţiu.
• Poziţia iniţială a roboţelului se află pe culoar.

Exemple

traseu2.intraseu2.outExplicaţii
5 2 1 1 0 0 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 1 1 1 1 0 0 0 ENESES 2 4 Din poziţia (2,1) roboţelul face o deplasare spre Est şi ajunge în poziţia (2,2). Următoarea deplasare este spre Nord şi ajunge în poziţia (1,2). Următoarea deplasare este spre Est şi ajunge în poziţia (1,3). Următoarea deplasare ar fi trebuit să fie spre sud, dar aceasta nu poate fi efectuată, fiindcă la sud este zid. Următoarea deplasare este spre Est şi ajunge în (1,4), apoi la Sud, şi ajunge în (2,4).
3 2 2 1 0 0 0 0 1 1 0 0 VVV 2 1 Din poziţia (2,2) roboţelul se deplasează spre vest, ajunge în poziţia (2,1).
La următoarea deplasare spre vest, roboţelul părăseşte labirintul.

propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Probleme recomandate
De la OMI Iaşi 2013: meteo1, unupatru, prodnr, moretime, xyz, vistiernic, dineu, vot1, pomi, fraze
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, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, 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
surse trimise | ajutor