Tezliklə Limandan Çıxış#3124
Kapitan Clearbeard ekipajının gəmini yoxlaması və təmiri üçün bir neçə gün limanda qalmağa qərar verdi. İndi, bir neçə gün keçdikdən sonra, quldurlar quru xəstəliyinə tutulmağa başlayıblar (Quldurlar quru xəstəliyinə, gəminin yelləncəyi hərəkətindən kifayət qədər faydalana bilməyəndə tutulurlar. Buna görə də bəzən onlar bu hərəkəti barellərin üstündə dayanıb sağa-sola yellənərək simulyasiya edirlər.). Bütün quldurlar limandan çıxmaq üçün qayığı çəkəcək qədər sağlam olarkən, Kapitan Clearbeard mümkün qədər tez limanı tərk etməyə qərar verdi.
Təəssüf ki, limana gedən yol birbaşa açıq dənizə çıxmır. Şəhəri pis quldurlardan qorumaq üçün limanın girişi bir neçə qaldırma körpüsü olan bir labirint kimi dizayn edilib. Hər bir körpünü açmaq müəyyən vaxt aparır, buna görə bəzən dolaşıq bir yol seçmək daha sürətli ola bilər. Sənin vəzifən Kapitan Clearbeard-a açıq dənizə çıxmaq üçün ən sürətli yolu tapmaqda kömək etməkdir.
Quldurlar xəritənin bir hüceyrəsini bir dəqiqəyə qət edə bilirlər. Gəmi xəritədə yalnız üfiqi və ya şaquli hərəkət edə bilər. dərəcə dönüş əlavə vaxt tələb etmir.
Əlavədə test hallarının sayı olan bir ədəd verilir. Hər bir test halı aşağıdakı formatdadır:
Bir sətrdə üç tam ədəd: , (3 \leq h; w \leq 500) və (0 \leq d \leq 50) — xəritənin hündürlüyü, eni və körpünün açılma gecikməsi.
sətrdə simvoldan ibarət xəritə təsviri. Xəritədə aşağıdakı simvollardan istifadə olunur:
S — gəminin başlanğıc mövqeyi.
. — su.
# — quru.
@ — qaldırma körpüsü.
Hər liman tamamilə quru ilə əhatə olunub, yalnız bir giriş istisna olmaqla.
Girişdəki hər bir test halı üçün çıxışda bir sətirdə bir tam ədəd çap edin: açıq dənizə ən sürətli marşrutun yol müddəti. Həmişə açıq dənizə bir yol mövcuddur. Qeyd edin ki, açıq dəniz xəritədə göstərilmir, yəni açıq dənizə çıxmaq üçün xəritənin kənarına çıxmaq lazımdır.
Nümunə 1