Un
robot punctiform se deplaseaza pe o placa dreptunghiulara care are coltul stânga-jos
în originea sistemului de coordonate, iar coltul dreapta-sus în
punctul de coordonate (A, B).
Robotul se afla initial în originea sistemului de coordonate si la un
pas se poate misca în una dintre cele 4 directii: Nord (din pozitia (x,
y) robotul ajunge în pozitia (x,
y+1)), Sud (din pozitia (x, y)
robotul ajunge în pozitia (x,
y-1), Est (din pozitia (x,y)
robotul ajunge în pozitia (x+1,
y)) sau Vest (din pozitia (x,
y) robotul ajunge în pozitia (x-1,
y)).
De la panoul de control al robotului se introduce o succesiune de N
pasi pe care robotul trebuie sa îi execute pentru a ajunge în coltul
dreapta-sus al placii (punctul de coordonate (A,
B)).
Din pacate, secventa de pasi introdusa este gresita si singura corectie care
se poate aplica, este ignorarea unei subsecvente de pasi din secventa data.
Cerinta
Scrieti un program care sa determine o subsecventa de pasi ce trebuie sa fie
ignorati astfel încât:
– robotul sa nu paraseasca placa;
– distanta dintre pozitia finala a robotului si coltul dreapta-sus al placii
sa fie minima.
Date de
intrare
Fisierul de intrare pasi.in contine
pe prima linie numerele naturale A B,
separate printr-un spatiu, reprezentând coordonatele coltului dreapta-sus
al placii. Pe cea de a doua linie se afla o secventa de caractere din multimea
{'N', 'S', 'E', 'V'}; caracterul i
reprezinta directia de miscare a robotului la pasul i
(N - Nord, S - Sud, E - Est si V - Vest).
Date de
iesire
Fisierul de iesire pasi.out va
contine o singura linie pe care va fi scrisa distanta dintre pozitia finala
a robotului si punctul (A, B)
(minima posibil), distanta obtinuta prin ignorarea unei subsecvente de pasi.
Restrictii
1 <= A, B <= 4000
0 < Numarul de pasi <=
5000
Distanta dintre doua puncte de coordonate (a, b), respectiv (c, d) se calculeaza
astfel abs(a-c)+abs(b-d).