Se citeste o matrice reprezentand un labirint, la fel ca in problemele anterioare (caracterele '.', '#', 'S', 'F'). De aceasta data, aveti voie sa distrugeti cel mult un singur obstacol pe parcursul drumului (trecand astfel prin acea celula). Determinati, folosind algoritmul Lee extins cu o stare suplimentara (daca a fost deja folosita distrugerea), numarul minim de pasi din S in F. Daca F nu poate fi atins nici asa, 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, folosind cel mult o distrugere de obstacol, sau -1.
- Restrictii
- 1 <= n, m <= 25, 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
4