Tezliklə Limandan Çıxış
Kapitan Clearbeard gəmisini yoxlamaq və təmir etmək üçün ekipajına bir neçə gün vaxt vermək məqsədilə limana getməyə qərar verdi. İndi, bir neçə gün sonra, quldurlar quru xəstəliyinə tutulurlar (Quldurlar gəminin yellənmə hərəkətini kifayət qədər hiss etmədikdə quru xəstəliyinə tutulurlar. Buna görə də quldurlar tez-tez bu hərəkəti rom içərək təqlid etməyə çalışırlar.). Bütün quldurlar limandan çıxmaq üçün çox xəstə olmadan əvvəl, kapitan Clearbeard limanı mümkün qədər tez tərk etməyə qərar verdi.
Təəssüf ki, liman açıq dənizə düz bir yol deyil. Şəhəri pis quldurlardan qorumaq üçün limanın girişi bir növ labirintdir və orada açılan körpülər var. Hər körpünün açılması müəyyən vaxt alır, buna görə də dolanbac yolla getmək daha sürətli ola bilər. Sizin vəzifəniz kapitan Clearbeard-a kömək etmək və açıq dənizə ən sürətli yolu tapmaqdır.
Quldurlar xəritədə hər bir hüceyrəyə bir dəqiqə ərzində avar çəkəcəklər. Gəmi xəritədə yalnız üfüqi və ya şaquli hərəkət edə bilər. 90 dərəcə dönmək əlavə vaxt tələb etmir.
Giriş verilənləri
Girişin ilk sətri izləyəcək test hallarının sayını göstərən tək bir rəqəmdən ibarətdir. Hər bir test halı aşağıdakı formatda verilir:
Üç tam ədəd olan bir sətir, h, w (3 ≤ h; w ≤ 500), və d (0 ≤ d ≤ 50), xəritənin hündürlüyü və eni və körpünün açılması üçün gecikmə.
h sətir, w simvol: xəritənin təsviri. Xəritə aşağıdakı simvollarla təsvir olunur:
"S", gəminin başlanğıc mövqeyi.
".", su.
"#", torpaq.
"@", açılan körpü.
Hər bir liman tamamilə torpaqla əhatə olunub, tək bir giriş istisna olmaqla.
Çıxış verilənləri
Girişdəki hər bir test halı üçün çıxışda tək bir sətirdə bir tam ədəd olmalıdır: açıq dənizə ən sürətli marşrutun səyahət vaxtı. Həmişə açıq dənizə bir marşrut var. Qeyd edək ki, açıq dəniz xəritədə göstərilmir, buna görə açıq dənizə çatmaq üçün xəritədən kənara çıxmalısınız.