Швидко з гавані#3124
Капітан Чистобород вирішив затриматися в гавані на кілька днів, щоб його команда мала змогу оглянути та відремонтувати корабель. Тепер, кілька днів потому, пірати починають хворіти на "сухоземну хворобу" (Пірати хворіють на "сухоземну хворобу", якщо не відчувають хитання корабля. Тому вони інколи намагаються імітувати це, стоячи на бочках і розгойдуючись з боку в бік). Поки всі пірати не захворіли настільки, що не зможуть вийти в море, капітан Чистобород вирішує покинути гавань якнайшвидше.
На жаль, гавань — це не просто пряма дорога до відкритого моря. Щоб захистити місто від злих піратів, вхід у гавань спроєктований як лабіринт з розвідними мостами. Відкриття кожного мосту займає певний час, тому десь може бути швидше зробити обхід. Ваше завдання — допомогти капітану Чистобороду знайти найшвидший шлях до відкритого моря.
Пірати можуть гребти з максимальною швидкістю — одна хвилина за кожну клітинку карти. Корабель може рухатися по карті лише горизонтально або вертикально. Повернення на градусів не потребує додаткового часу.
Перший рядок вхідних даних містить одне число: кількість тестових випадків, що йдуть далі. Кожен тест задається у такому форматі:
Один рядок з трьома цілими числами , (3 \leq h; w \leq 500) та (0 \leq d \leq 50): висота, ширина карти і затримка на відкриття мосту.
рядків по символів: опис карти. На карті використовуються такі символи:
S — початкова позиція корабля.
. — вода.
# — суша.
@ — розвідний міст.
Кожна гавань повністю оточена сушею, окрім єдиного входу.
Для кожного тесту у вхідних даних виведіть одне ціле число у окремому рядку — час найшвидшої подорожі до відкритого моря. Шлях до моря завжди існує. Зверніть увагу, що відкрите море на карті не зображено, тому щоб дістатися до нього, потрібно вийти за межі карти.
Приклад 1