După moartea tatălui său, Paul Atreides s-a refugiat în deșert printre fremeni. Aici el a primit numele Muad'Dib și a început să îi organizeze pe oamenii deșertului pentru a lupta împotriva Harkonnienilor în vederea redobândirii de către Casa Atreides a controlului asupra mirodeniei, bogăția inestimabilă a planetei-deșert Arrakis. Doar fremenii cunoșteau adevărata identitate al lui Muad'Dib, dar faima sa de profet a ajuns până pe Giedi Prim, planeta de reședință a Casei Harkonnen. Baronul Vladimir Harkonnen și-a dat seama că ar fi bine să cunoască acțiunile celui care a devenit într-un timp foarte scurt simbolul fremenilor. În acest scop, el a reușit să infiltreze printre fremeni un spion care avea asupra sa un dispozitiv de urmărire. Paul Muad'Dib și-a dat seama că este urmărit și s-a gândit să plece în deșert. Totuși, spionul a reușit să îi ascundă în interiorul distraiului un aparat de urmărire rudimentar. Acest aparat este capabil de a detecta doar direcția de mers, dar nu și distanțele parcurse.
Planeta Dune (denumirea dată de fremeni Arrakisului) este descrisă printr-un tablou bidimensional de dimensiuni m Ž n. O regiune stâncoasă este reprezentată de caracterul '+', o regiune deșertică prin caracterul '.', iar sietch-ul din care pleacă Muad'Dib prin caracterul '*'. Se știe că pericolul principal al planetei Dune îl reprezintă uriașii viermi de nisip. Doar cei foarte bine antrenați pot supraviețui întâlnirii cu acești monștri care pot avea lungimi de câțiva kilometri. Totuși, trăind în deșert, fremenii au descoperit cum pot să folosească acești viermi în avantajul lor. Ținuturile stâncoase sunt controlate de către Harkonnieni deoarece aici nu există pericolul viermilor. Din aceste motive tânărul Atreides se deplasează doar prin deșert. Deși nu găsește nici o explicație logică a acestui fapt, Baronul a aflat acest lucru și încearcă să folosească această informație. Pentru aceasta îl cheamă pe mentatul Thufir Hawat și îi cere să determine șansele pe care le are de a-l găsi pe profetul fremenilor. Pentru aceasta mentatul trebuie să determine numărul pozițiilor în care se poate afla Muad'Dib. Hawat știe că fremenul se poate deplasa doar pe orizontală și pe verticală și că dispozitivul de urmărire va detecta orice schimbare de direcție. După schimbarea unei direcții Muad'Dib se deplasează cu cel puțin o poziție în acea direcție, și modificările de direcție au loc întotdeauna cu 90°.
Prima linie a fișierului de intrare conține numerele m și n, separate printr-un singur spațiu. Următoarele m linii conțin câte n caractere care descriu suprafața planetei (caracterele admise sunt '.', '+' și '*' ; ele au semnificația prezentată anterior). Următoarea linie va descrie informațiile furnizate de dispozitivul de urmărire, neseparate prin spații. Litera 'N' indică o deplasare spre nord (spre prima linie a matricei), litera 'V' o deplasare spre vest (spre prima coloană), litera 'S' o deplasare spre sud (spre ultima linie), iar litera 'E' o deplasare spre est (spre ultima coloană).
Fișierul de ieșire va conține un singur număr care va indica numărul pozițiilor în care se poate afla Muad'Dib.
· 1 <= m, n <= 50;
· numărul schimbărilor de direcție este cel mult 1000; · Paul nu poate ieși în afara matricei.
DUNE.IN 4 5 ..... .+.+. +.... .++.* NVS DUNE.OUT 4
|