Se citeste o matrice reprezentand un labirint, cu caracterele '.' (celula libera), '#' , 'S' (punctul de start) si 'F' (punctul final). Determinati, folosind algoritmul Lee (o parcurgere in latime cu o coada, pornind din S), numarul minim de pasi necesari pentru a ajunge din S in F, deplasandu-va doar sus, jos, stanga sau dreapta, prin celule libere. Daca F nu poate fi atins, 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 numarul minim de pasi din S pana in F, 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
4
Exemplul 2
Intrare
3 3 S#. ### .#F
Iesire
-1