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.in	traseu2.out	Explicaţ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