Горіхи для горіхів
Райан і Ларрі вирішили, що їх горіхи не дуже приємні на смак. Проте є декілька горіхів, розташованих в деяких місцях острова, і вони дуже смачні! Але оскільки хлопці ліниві та жадібні, то вони хочуть знати найкоротший шлях, по якому можна зібрати всі горіхи. Чи можете Ви їм допомогти?
Вхідні дані
Перший рядок кожного тесту містить розміри прямокутного острова x та y (x, y ≤ 20). Далі слідують x рядків по y символів, що описують карту місцевості. Вона складається з символів '.', '#' та 'L'. Спочатку Ларрі і Райан знаходяться в 'L', горіхи позначаються символами '#'. Хлопці за один крок можуть потрапити в будь-яку з восьми сусідніх клітин. Кількість клітин, у яких можуть розташовуватися горіхи, не більша за 15. Клітинка з символом 'L' на карті усього одна.
Вихідні дані
Для кожної карти в окремому рядку виведіть найменшу кількість кроків, за яку можна стартувавши з клітинки 'L', зібрати усі горіхи і повернутися в 'L'.