O metodă de codificare a imaginilor, folosită, de exemplu, în formatul .jpeg, se bazează pe împărţirea unei regiuni pătratice dintr-o imagine în patru pătrate egale, numerotate ca în figura de mai jos.
Acest procedeu de împărţire poate continua la nivele de detaliere mai mari, ceea ce conduce la obţinerea unor numere în care pot să apară cifrele 1, 2, 3 sau 4, şi care corespund unor porţiuni pătratice din imaginea iniţială. În cea de a doua figură sunt prezentate codificările câtorva pătrate.
Un pătrat al cărui cod este cunoscut poate fi deplasat înspre stânga, înspre dreapta, în sus sau în jos cu un anumit număr de poziţii. O comandă de deplasare este de forma d nr
unde d este un caracter din mulţimea {L,U,R,D}, el arată direcţia pe care este efectuată mutarea, iar nr este un număr natural nenul şi mai mic sau egal decât 10, număr care arată deplasamentul faţă de poziţia curentă. De exemplu, comanda L 1 înseamnă mutarea pătratului cu o poziţie înspre stânga, U 2 înseamnă mutarea pătratului cu două poziţii mai sus, R 3 înseamnă mutarea pătratului cu trei poziţii înspre dreapta,
D 1 înseamnă mutarea pătratului cu o poziţie mai jos. De exemplu, comanda de deplasare D 2, aplicată pătratului cu codul 132, îl va duce pe acesta în pătratul cu codul 422. În urma unei comenzi un pătrat poate să ajungă peste un alt pătrat de aceeaşi mărime sau în afara imaginii. Dacă o comandă de deplasare are ca efect ieşirea pătratului în afara zonei ce corespunde întregii imagini, atunci respectiva comandă conduce la oprirea interpretării comenzilor care, eventual, o urmează.
Cerinţă
Scrieţi un program care citeşte o codificare a unui pătrat, apoi o succesiune de comenzi de deplasare referitoare la acel pătrat. Programul trebuie să afişeze numărul de ordine al primei comenzi care conduce la ieşirea pătratului în afara regiunii codificate. Dacă la finalul şirului de comenzi pătratul este încă în interiorul regiunii codificate, fără să fi ieşit vreodată în afara ei, atunci ca rezultat se va scrie codul poziţiei în care a ajuns pătratul după ultima mutare.
Date de intrare
Fişierul de intrare codpatrat.in
conţine pe prima linie o succesiune de cifre care semnifică codul pătratului care urmează să fie deplasat. Cifrele nu sunt separate de spaţii şi pot fi 1,2,3 sau 4. În continuare, pe fiecare dintre următoarele linii, până la sfârşitul fişierului, se găsesc comenzi de deplasare a pătratului. Într-o comandă apar un caracter şi un număr, separate printr-un spaţiu. Caracterul poate fi U, D, L sau R, cu semnificaţia descrisă in enunţ. Numărul dintr-o comandă este un număr natural nenul şi mai mic sau egal decât 10.
Date de ieşire
Fişierul de ieşire codpatrat.out
va conţine o singură linie, pe care va fi scris, după caz, numărul de ordine al primei comenzi care conduce la ieşirea pătratului în afara imaginii, sau codul poziţiei în care ajunge pătratul în urma efectuării comenzilor de deplasare, sub forma unei secvenţe de cifre 1, 2, 3 sau 4, între care nu există alte caractere.
Restricţii
Codul pătratului care urmează să fie deplasat este compus din cel mult 100 caractere.
Numărul de comenzi de deplasare este de cel mult 100.
Exemple
codpatrat.in
codpatrat.out
Explicaţii
1
D 1
R 1
L 1
R 1
D 1
5
Pătratul 1 iese în afara regiunii la mutarea a cincea
133
R 2
U 3
L 3
D 4
421
În urma efectuării celor patru comenzi pătratul care la început era în 133 ajunge în 421
