Concursul "Urmasii lui Moisil" 2002 Clasa a IX-a

Problema 1- Robotei

Pe o platforma dreptunghiulara situata în Oceanul Atlantic, în perioada marilor furtuni lucreaza numai roboti. Harta platformei este o matrice cu M+1 linii si N+1 coloane, numerotate de la 0 la M, respectiv de la 0 la N. Pe platforma exista R roboti, numerotati distinct de la 1 la R. Pentru fiecare robot, se cunoaste pozitia initiala si o secventa de comenzi, care determina modul de deplasare a robotului pe platforma. Pozitia unui robot este specificata printr-o pereche de coordonate întregi de pe harta si o orientare (N - nord, E - est, S - sud, V - vest ).

Directia NORD corespunde deplasarii din punctul (x, y) în punctul (x,y+1).
O secventa de comenzi este un sir de litere S, D, I, cu semnificatia:
S - stânga: robotul se întoarce la stânga cu 90° si ramâne în acelasi punct;
D - dreapta: robotul se întoarce la dreapta cu 90° si ramâne în acelasi punct;
I - înainte: robotul se deplaseaza cu un punct în directia în care este orientat, pastrându-si orientarea.
Un robot care se deplaseaza în afara platformei este pierdut pentru totdeauna. Totusi, un robot pierdut lasa un mesaj care va împiedica alti roboti sa cada de pe platforma din acelasi punct. Mesajul este lasat în ultimul punct ocupat de robot înainte de disparitie. O comanda de deplasare în afara platformei din acel punct va fi ignorata de ceilalti roboti. Robotii lucreaza secvential, adica robotii urca pe platforma pe rând, conform numerelor lor de ordine, se deplaseaza în pozitia finala, apoi coboara de pe platforma.
Cerinta
Scrieti un program care determina pozitia finala de pe platforma a fiecarui robot.
Date de intrare
Fisierul de intrare ROBO.IN contine:
-- pe prima linie coordonatele M, N ale coltului dreapta-sus al hartii (coordonatele coltului jos-stânga sunt 0, 0);
- pe a doua linie R, numarul de roboti;
- liniile urmatoare contin pozitiile si secventele de comenzi pentru roboti (câte doua linii pentru un robot). O pozitie este specificata pe o linie prin doua valori întregi (coordonatele robotului pe harta) si un caracter (reprezentând orientarea robotului), separate prin câte un spatiu. Pe urmatoarea linie se afla secventa de comenzi corespunzatoare.
Date de iesire
Pentru fiecare robot se va scrie pe o linie separata în fisierul de iesire ROBO.OUT pozitia finala. Daca un robot cade de pe platforma, se va scrie si mesajul PIERDUT dupa ultima lui pozitie pe platforma. Pe fiecare linie datele sunt separate prin câte un spatiu.
Restrictii
- Toate pozitiile initiale sunt interioare platformei.
- Valoarea maxima pentru orice coordonata este 50.
- Orice secventa de comenzi are cel mult 100 de caractere.
- Numarul maxim de roboti este 100.
Exemplu

Timp maxim de executie: 1 secunda/test