Turist gəzintisi
Olimpiada — dünya səviyyəli bir idman tədbiridir. Olimpiya oyunlarına ev sahibliyi etmək şansı qazanan şəhər, hər dəfə öz komandalarını dəstəkləmək üçün gələn milyonlarla azarkeşi, idmançıları və böyük Oyunların ölkələr və qitələr arasındakı sərhədləri sildiyi hər kəsi heyran etməyə çalışır.
Londonun Olimpiadanın keçirilməsi sahəsində böyük təcrübəsi var: Böyük Britaniyanın paytaxtı 2012-ci ildə rekord üçüncü dəfə Oyunlara ev sahibliyi etdi. Əvvəlki iki dəfə, 1908 və 1948-ci illərdə obyektiv səbəblərə görə möhtəşəm bayram təşkil etmək mümkün olmadı, buna görə də bu dəfə geniş miqyasda qeyd etmək qərara alındı.
Olimpiya obyektlərinin yaradılmasına ingilislər britaniyalara xas rasional yanaşdılar, qənaətli tikinti strategiyasını tətbiq etdilər. Arenaların tikintisində müasir materiallardan istifadə edildi ki, bu da yarışlardan sonra obyektlərin tez və asanlıqla sökülməsinə imkan verirdi.
Çoxsaylı ziyarətçilər üçün xüsusi olaraq Londonda olimpiya (və yalnız deyil) görməli yerləri göstərən xüsusi xəritələr hazırlandı. Vasinin də əlinə belə bir xəritə düşdü. Onun maraqlandığı yarışlardan azad vaxtı var idi və o, xəritədə qeyd olunan mümkün qədər çox maraqlı obyektləri ziyarət edərək özünə turistik gəzinti təşkil etmək istəyir.
Londonda küçə hərəkət qaydaları olduqca özünəməxsusdur, lakin Vasi onları xüsusi öyrənməməyə qərar verdi — o, praktikada yoxladı ki, əgər o, şəhərin şimal-qərb hissəsində yerləşən otelindən yalnız cənuba və ya şərqə doğru hərəkət edirsə və geri qayıdanda yalnız qərbə və ya şimala doğru hərəkət edirsə, heç vaxt problem yaşamır.
Sizin vəzifəniz Vasinin öz qaydalarına uyğun hərəkət edərək Olimpiya Londonunun mümkün qədər çox görməli yerlərini ziyarət etməsi və eyni zamanda otelə qayıtması üçün belə bir marşrut tərtib etməkdir.
Giriş verilənləri
Giriş faylının ilk sətirində test hallarının sayı verilir (ən çox 20). Hər bir test halının ilk sətirində iki ədəd var: W və H (2 ≤ W, H ≤ 100), xəritənin eni və hündürlüyü. Hər bir test halının növbəti H sətirində hər biri W simvolu olan sətirlər var və bunlar göstərir:
'.' - hərəkət edilə bilən boş sahə;
'*' - maraqlı obyekt (bu da hərəkət edilə bilən sahədir);
'#' - bloklanmış sahələr (bu sahələrdə hərəkət etmək mümkün deyil).
Vasinin qaldığı oteldən, xəritənin sol üst küncündə yerləşən, xəritənin sağ alt küncünə həmişə bir yol olduğunu qəbul edə bilərsiniz.
Çıxış verilənləri
Hər bir test halı üçün ayrı sətirdə Vasinin ziyarət edə biləcəyi maraqlı obyektlərin maksimum sayını — yalnız bir ədəd çıxarın. Eyni maraqlı olimpiya və ya turistik obyekt iki dəfə ziyarət edildikdə yalnız bir dəfə sayılır.