Горіхи для горіхів#2302
Раян і Ларрі вирішили, що їхні власні горіхи не дуже смачні. Однак на острові є деякі місця з дуже смачними горіхами! Оскільки хлопці ледачі й жадібні, вони хочуть знайти найкоротший шлях, щоб зібрати всі смачні горіхи. Чи можеш ти їм допомогти?
Перший рядок кожного тесту містить розміри прямокутного острова та (x, y \leq 20). Далі йдуть рядків, кожен з яких містить символів, що описують карту. Карта складається з символів , # та . Спочатку Ларрі та Раян знаходяться на , а горіхи позначені символом #; порожні клітини позначені . За один крок хлопці можуть перейти у будь-яку з суміжних клітин. Горіхів на карті не більше . На карті є рівно одна клітина, позначена .
Для кожної карти в окремому рядку виведіть мінімальну кількість кроків, необхідну, щоб почати з , зібрати всі горіхи і повернутися на .
Приклад 1