Qiyin masala
Poligondagi yo'l
Vaqt: 1 s
Xotira: 128 MB
Testlar: 7
Mashg'ulot poligoni h × w katakli xarita ko'rinishida berilgan: . — bo'sh katak, # — to'siq, S — start, F — finish. Kursant bir qadamda yuqori, past, chap yoki o'ng qo'shni katakka o'tadi (to'siqqa kira olmaydi). Startdan finishgacha eng kamida necha qadam kerak? Yetib bo'lmasa -1 chiqaring.
Kiruvchi ma'lumot
Birinchi qatorda h va w (1 ≤ h, w ≤ 100). Keyingi h qatorda xarita.
Chiquvchi ma'lumot
Eng kam qadamlar soni yoki -1.
Misol
Kirish
3 4 S..# .#.. ...F
Chiqish
5
Izoh
Kenglik bo'yicha qidiruv (BFS) algoritmini qo'llang.