eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Орехи для орехов

Орехи для орехов

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Райан и Ларри решили, что их орехи не слишком приятны на вкус. Однако имеется несколько орехов, расположенных в некоторых местах острова, и они очень вкусные! Но поскольку ребята ленивые и жадные, то они хотят знать кратчайший путь, по которому можно собрать все орехи. Можете ли Вы им помочь?

Входные данные

Первая строка каждого теста содержит размеры прямоугольного острова x и y (x, y20). Далее следуют x строк по y символов, описывающие карту местности. Она состоит из символов ., # и L. Изначально Ларри и Райан находятся в L, орехи обозначаются символами #. Ребята за один шаг могут попасть в любую из восьми соседних клеток. Количество клеток, в которых могут располагаться орехи, не более 15. Клетка с символом L на карте всего одна.

Выходные данные

Для каждой карты в отдельной строке вывести наименьшее количество шагов, за которое стартовав с клетки L, можно собрать все орехи, и вернуться в L.

Пример

Входные данные #1
5 5
L....
#....
#....
.....
#....
8 10
L.........
..........
.......#..
..........
#....#....
.........#
..........
....#.....
Выходные данные #1
8
23