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.

Yechim yuborish uchun tizimga kiring yoki ro'yxatdan o'ting.

Navbatdagi musobaqa

Biriktirilgan musobaqa

SamCoding Round 11 (Div. 1)

Natijalar