Se citeste o matrice reprezentand un labirint, la fel ca in problemele anterioare (caracterele '.', '#', 'S', 'F'). Folosind algoritmul Lee, determinati un drum minim de la S la F si afisati-l ca o succesiune de miscari: 'N' , 'S' , 'V' , 'E' . Daca F nu este accesibil, afisati -1.
- Date de intrare
- Pe prima linie se citesc n si m, numarul de linii si de coloane ale matricei. Urmeaza n linii, fiecare continand un sir de m caractere.
- Date de iesire
- Se afiseaza sirul miscarilor drumului minim (fara spatii intre ele), sau -1 daca F nu este accesibil.
- Restrictii
- 1 <= n, m <= 30, matricea contine exact o celula S si o celula F
Exemple
Exemplul 1
Intrare
3 3 S.. .#. ..F
Iesire
SSEE
Exemplul 2
Intrare
3 3 S#. ### .#F
Iesire
-1