Uzb Eng

C35E. Isfandiyor paxtada
: 2 c
: 64

TATU talabalari paxta dalasiga xirmonga oz xissalarini qoshish uchun borishdi.Paxta dalasi NxM olchamda. Isfandiyor ilgor paxtakorlardan. Tushlik yaqinlashib qolgani sababli uning qorni juda ochdi. U birinchi bolib tushlikka bormoqchi. Yolda esa paxtakorlar va paxta uyumlari bor. U ilgor paxtakorlardan bolganligi sababli paxtani bosib otolmaydi. Shuning uchun u paxtakorning yonidan uzr sorab otadi. Ulardan uzr sorashni yomon koradi. Bundan tashqari yolda tosiqlar ham bor. U tushlikka eng kam paxtakorlardan uzr sorab bormoqchi. Unga yordam bering. Paxta dalasi NxM korinishidagi jadval orqali beriladi. Isfandiyor kordinatasi S harfi bilan, tushlik joyi E harfi bilan, tosiqlar esa T harfi bilan beriladi. Jadvalda yana 0 dan 9 gacha raqamlar bor, bu shu kordinatadagi paxtakordan uzr sorashlar sonini bildiradi.Isfandiyor tepaga , pastga ,ongga va chapga harakatlanishi mumkin.

:
Birinchi satrda n va m sonlari probel bilan, keying n ta qatorda m tadan simvol orqali jadval beriladi.
1 <= N,M <= 1000

:
Isfandiyorning eng kam uzr sorashlar sonini chiqaring.

5 7
000E0T3
T0TT0T0
010T0T0
2T0T0T0
0T0S000
3
:
:


Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.