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