Задача Z. Змейка ≡

Условие

Подружки Катя и Надя уже давно играют в игру «Змейка».

Поле для игры представляет собой клетчатый квадрат со стороной n. В каждой клетке квадрата может быть либо зеленая лужайка, либо пень. Изначально в их распоряжении находится змейка длиной 1. За один шаг змейка может перемещаться в одном из 4х направлений: вверх, вниз, вправо и влево. Однако змейка не может ползать по пенькам.

Так же на поле имеется одно яблоко. В момент, когда змейка наползает на яблоко, яблоко пропадает и появляется в другом месте, а длина змейки увеличивается на единицу. (В этот момент туловище змейки продляется на ту клетку, из которой только что выполз хвост). Обратите внимание, что змейка не может переползать через саму себя или ползти в клеточку, в которой находится ее хвост (хвост уже старенький и выползти не успевает).

В последнее время девочки соревнуются в прохождении уровня на скорость. Им известны все места появления яблок, которых оказалось ровно k, и интересно минимальное число ходов, за которое можно собрать все яблоки. Помогите Кате и Наде по описанию лабиринта найти число ходов.

Формат входного файла

В первой строке входного файла находится число n. В последующих n строках содержится по n символов задающих лабиринт. Лужайке соответствует символ ‘.’, пню – ‘#’, i-ому яблоку цифра i

Формат выходного файла

В единственной строке выходного файла должно содержаться одно число – минимальное требуемое число ходов. Если собрать все яблоки не возможно, выведите -1.

Ограничения

2 ≤ n ≤ 10.

2 ≤ k ≤ 8.

Примеры тестов

3
#3.
1.2
#4#
        

6

3
#43
1.2
#5#
        

-1