Лабиринт

Автор:Кленин А.   Ограничение времени:4 сек
Входной файл:input.txt   Ограничение памяти:16 Мб
Выходной файл:output.txt  

Условие

Лабиринт размером N x N клеток задан массивом символов. Символ '#' обозначеет стену, символ '.' — проход. Передвигаться по лабиринту можно шагами по горизонтали или вертикали, но не по диагонали.

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

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

Первая строка входного файла содержит размер лабиринта N.

Следующие N строк содержат по N символов — описание лабиринта.

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

Выходной файл должен содержать единственное целое число — длину кратчайшего пути, либо −1, если пути не существует

Ограничения

1 ≤ N ≤ 1500, левый верхний угол лабиринта всегда свободен.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
.#
..
2
2
2
.#
#.
-1

0.101s 0.018s 15