Teleportasiya!
Siz düzbucaqlı bir labirintdəsiniz və oradan mümkün qədər tez çıxmaq istəyirsiniz. Labirint kvadrat yerlərdən ibarət bir şəbəkədir. Bəzi yerlər bloklanıb, digərləri isə çıxışdır. Çıxış yerinə çatdığınız anda dərhal labirintdən çıxa bilərsiniz.
Hər dəfə bir addım ataraq cari yerinizə bitişik olan yerlərdən birinə keçə bilərsiniz. İki yer bitişik sayılır, əgər onlar bir tərəfi paylaşırsa. Yəni, yalnız bir addım Şimal, Cənub, Şərq və ya Qərbə hərəkət edə bilərsiniz. Labirintdən kənara çıxa və ya bloklanmış yerə keçə bilməzsiniz.
Bundan əlavə, hər hansı bir addımda teleport cihazınızı istifadə etməyi seçə bilərsiniz. Bu cihaz sizi labirintin içində təsadüfi bir bloklanmamış yerə bərabər ehtimalla göndərəcəkdir (mümkün olaraq, hal-hazırda dayandığınız yer də daxil olmaqla!). Əgər cihaz sizi həm də bir çıxış olan yerə göndərərsə, dərhal labirintdən çıxırsınız. Yaşasın!
Labirintdən çıxmağın yeganə yolu bir çıxışa hərəkət etməkdir (ya teleportla, ya da gəzərək), labirintin sərhədindən kənara çıxa bilməzsiniz. Labirintdən çıxmaq üçün lazım olan gözlənilən addımların sayını hesablamaq üçün bir proqram yazın. Fərz edin ki, labirintdən çıxmaq üçün lazım olan gözlənilən addımların sayını minimuma endirmək üçün hərəkətlərinizi (hərəkətlər və teleport cihazının istifadəsi) optimal şəkildə seçərsiniz. Teleport cihazının istifadəsi bir addım hesab olunur.
Giriş verilənləri
Bir neçə test halı olacaq. Hər test halı iki müsbət tam ədəd R və C (R <= 200, C <= 200) ilə başlayan bir sətirdən ibarətdir. Sonra, növbəti R sətir hər biri labirintin yerlərini təmsil edən C simvolu ehtiva edir. Simvollar aşağıdakılardan biri olacaq:
E: çıxışı təmsil edir, hər labirintdə ən azı bir 'E' olacaq.
Y: başlanğıc yerinizi təmsil edir, hər labirintdə dəqiq bir 'Y' olacaq.
X: bloklanmış yeri təmsil edir.
.: boş yeri təmsil edir.
'E', 'Y' və ya '.' ilə işarələnmiş hər hansı bir yerə hərəkət edə/teleport edə bilərsiniz.
Girişin sonu iki boşluqla ayrılmış 0 ilə işarələnmiş bir sətirlə göstərilir.
Çıxış verilənləri
Hər test halı üçün, labirintdən çıxmaq üçün lazım olan minimum gözlənilən addımların sayını, bu dəyəri minimuma endirmək üçün seçimlərinizi optimal şəkildə etdiyinizi nəzərə alaraq, bir sətirdə çap edin. Nəticənizi 3 ondalık dəqiqliklə çap edin. Çıxışlar arasında boş sətir çap etməyin.