Muallif: __thecrash__
C. Muzli labirint
Vaqt limiti: 1000 ms Xotira limiti: 256 mb
Pingvin Pingo muzlagan ko'l ustida o'ynamoqda. Ko'l \(n \times m\) o'lchamli jadval ko'rinishida. Har bir katak silliq muz ('.') yoki tosh ('#') bo'lishi mumkin. Pingo 'S' katagida turibdi, 'E' katakda esa muzda teshik bor. Pingo o'sha teshik orqali suvga sho'ng'ib, baliq ovlamoqchi.
Muz shu qadar silliqki, Pingo yurolmaydi, faqat sirpanadi. Bir itarilishda u to'rt yo'nalishdan birini, ya'ni yuqori, pastga, chapga yoki o'ngga tanlaydi va shu tomonga sirpanib ketadi. Sirpanish oldida tosh yoki ko'l cheti uchragunga qadar davom etadi, Pingo yo'lning o'rtasida to'xtay olmaydi. Agar sirpanish davomida Pingo teshik ustidan o'tsa, u darhol teshikka tushadi. 'S' va 'E' kataklari ham muz hisoblanadi.
Pingo teshikka yetib borishi uchun eng kamida necha marta itarilishi kerakligini aniqlang.
Kiruvchi ma'lumotlar
Birinchi qatorda ikkita butun son \(n\) va \(m\) (\(1 \le n, m \le 1000\), \(n \cdot m \ge 2\)) mos ravishda ko'lning qatorlari va ustunlari soni.
Keyingi \(n\) ta qatorning har birida \(m\) ta belgi '.', '#', 'S' yoki 'E' berilgan. Jadvalda 'S' va 'E' belgilari roppa-rosa bittadan uchraydi.
Chiquvchi ma'lumotlar
Itarilishlarning eng kam sonini chiqaring. Agar Pingo teshikka yetib bora olmasa, \(-1\) ni chop eting.
Misollar
| # | Input.txt | Output.txt |
|---|---|---|
| 1 |
5 6 S....# .#.... ...... ....#. #..E.. |
3 |
| 2 |
5 6 S.#..# .#.... #.E.#. ...... ###### |
-1 |
Izoh
Birinchi misolda Pingo avval pastga sirpanib, \((4, 1)\) katakda toshga urilib to'xtaydi. Keyin o'ngga sirpanib, \((4, 4)\) katakda to'xtaydi. Uchinchi marta pastga itarilganda u teshikka tushadi.
Ikkinchi misolda Pingo faqat \((1, 1)\), \((1, 2)\) va \((2, 1)\) kataklarda to'xtay oladi, teshikka hech qachon yetib bormaydi.
Uchinchi misolda Pingo o'ngga sirpanayotganda teshik ustidan o'tadi va unga tushadi.