Labirint $n \times m$ kataklardan iborat: . — yo‘lak, # — devor, S — kirish, F — chiqish. Bir qadamda qo‘shni (yuqori, past, chap, o‘ng) yo‘lakka o‘tish mumkin. Kirishdan chiqishgacha eng kamida necha qadam kerak?
Kirish ma‘lumotlari
Birinchi qatorda $n$ va $m$ ($2 \le n, m \le 500$). Keyingi $n$ ta qatorda $m$ tadan belgi. S va F bittadan.
Chiqish ma‘lumotlari
Eng kam qadamlar soni; chiqishga yetib bo‘lmasa, -1.
Misollar
Kirish
3 4 S..# .#.. ...F
Chiqish
5
Kirish
2 3 S#F .#.
Chiqish
-1