Din nefericire un elf s-a pierdut în labirintul minotaurilor.
Labirintul poate fi privit ca un caroiaj ale cărui celule pot fi libere sau ocupate de ziduri. Elful se poate deplasa pe verticală sau orizontală doar în celulele libere. Spre bucuria lui a descoperit că nu a pierdut harta labirintului pe care o primise de la minotauri.
Fișierul de intrare INPUT.TXT conține pe prima linie dimensiunile m și n ale labirintului.
Următoarele m linii vor descrie celulele labirintului. Pe fiecare astfel de linie se vor afla câte n caractere. O celulă liberă va fi identificată prin caracterul L, iar una ocupată prin caracterul O. Ultima linie a fișierului va conține poziția inițială a elfului.
Fișierul de ieșire OUTPUT.TXT trebuie să conțină pe prima linie lungimea minimă a unui drum care îl va duce pe elf la marginea labirintului.
Cea de-a doua linie va conține o descriere a drumului. Fiecare mișcare a elfului va fi codificată printr-o literă. O mișcare de pe a i-a linie a labirintului pe cea de-a (i-1)-a linie a acestuia va fi codificată prin N. O mișcare de pe a i-a linie a labirintului pe cea de-a (i+1)-a linie a acestuia va fi codificată prin S. O mișcare de pe a i-a coloană a labirintului pe cea de-a (i-1)-a coloană a acestuia va fi codificată prin V. O mișcare de pe a i-a coloană a labirintului pe cea de-a (i+1)-a coloană a acestuia va fi codificată prin E.
INPUT.TXT
4 5 OLLOL OLOLO OLLLO OLOOO 2 4 OUTPUT.TXT 4 SVVS
|