Tam Pansion#6626
Bir oyun M×N ölçülü lövhədə oynanılır, burada bəzi kvadratlar "maneələr" kimi işarələnmişdir (aşağıdakı şəkildə tünd kvadratlar kimi göstərilmişdir). Oyunçu topun başlanğıc mövqeyini seçir (bərk boz nöqtə kimi göstərilmişdir) və hərəkət etmək üçün bir istiqamət (yuxarı, aşağı, sola və ya sağa) seçir. İstiqamət seçildikdən sonra top həmin istiqamətdə hərəkət edir, ta ki maneəyə, lövhənin sərhədinə və ya öz trayektoriyasına dəyənə qədər. Bu obyektlərdən birinə dəyəndə top dayanır. Sonra oyunçu başqa bir istiqamət seçə bilər və top eyni qaydada hərəkət edəcək. Oyun heç bir qanuni hərəkət qalmadıqda bitir. Oyunçu yalnız trayektoriya lövhədəki bütün boş kvadratları əhatə edərsə qalib gəlir. Aşağıdakı şəkildə oyunu 10 addımda qazanmağın bir yolunu göstərən bir trayektoriya izlənilir.
Lövhənin ilkin quruluşu verildikdə, oyunu qazanmaq üçün minimum addım sayını hesablayan bir proqram yazın.
Giriş faylındakı hər bir hal lövhənin ölçüsünü göstərən iki tam ədəd m və n (1 ≤ m, n ≤ 30) ilə başlayır. Növbəti m sətir lövhənin ilkin quruluşunu təsvir edir. Hər sətir müvafiq kvadratın maneə və ya boş olduğunu göstərən '*' və ya '.' simvollarından ibarətdir. [Məsələn, yuxarıdakı şəkildəki hal üçün giriş faylına baxın.] İlkin lövhənin tamamilə maneələrlə örtülmədiyi təmin edilir. Faylın sonuna qədər işləyin; məlumatların sonu bayrağı yoxdur.
Lövhəni əhatə etmək üçün minimum addım sayını çıxarın. Formatı dəqiq izləyin: "Case", bir boşluq, hal nömrəsi, iki nöqtə və bir boşluq, oyunu qazanmaq üçün minimum addım sayını və ya qazanmağın heç bir yolu yoxdursa, -1 rəqəmini göstərin. Heç bir son boşluq çap etməyin.
Nümunə 1