E. Labirint va bolg‘a

Ali N × M katakli labirintning S katagida turibdi va chiqish — E katagiga yetmoqchi. . — bo‘sh katak, # — devor. Bir qadamda yuqoridagi, pastdagi, chapdagi yoki o‘ngdagi qo‘shni katakka o‘tish mumkin; labirintdan tashqariga chiqib bo‘lmaydi.

Alining qo‘lida bitta bolg‘a bor: butun yo‘l davomida u ko‘pi bilan bitta devorni buzib, o‘sha katakdan o‘tishi mumkin (buzilgan katakka kirish ham bitta qadam).

E ga yetish uchun eng kamida nechta qadam kerak? Yetib bo‘lmasa, -1 chiqaring.

Kirish ma’lumotlari

Birinchi qatorda N va M. Keyingi N ta qatorning har birida M ta belgidan iborat satr: ., #, S yoki E. S va E aynan bittadan.

Chiqish ma’lumotlari

Bitta butun son — eng kam qadamlar soni yoki -1.

Cheklovlar

• 1 ≤ N, M ≤ 500, N · M ≥ 2

1-misol: E atrofidagi sohaga bolg‘asiz kirib bo‘lmaydi. 3-qator, 4-ustundagi devorni buzib, pastga ikki qadam, so‘ng o‘ngga olti qadam yuriladi — jami 8.

2-misol: devor ustuni butun labirintni kesib o‘tgan — uni bir joyda buzish kerak: 4 qadam.