Задача C. Квадратное озеро

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

Условие

Квадратное озеро, покрытое многочисленными мелкими островками, задается матрицей размером NxN. Каждый элемент матрицы содержит либо символ '@', обозначающий островок, либо символ '.' (точка), обозначающий участок свободной воды. В левом верхнем углу озера находится квадратный плот размером MxM клеток. За один шаг плот может сдвигаться на одну клетку по горизонтали или вертикали. Требуется определить минимальное число шагов, необходимых для того, чтобы плот достиг правого нижнего угла озера.

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

В первой строке входного файла содержатся числа N и M, разделенные пробелами. В следующих N строках находится матрица, представляющая озеро, по N подряд идущих символов в строке. Подматрица размером MxM, находящаяся в левом верхнем углу, не содержит островов (т.е. начальное положение плота всегда допустимо).

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

Выходной файл должен содержать единственное число - количество необходимых шагов. Если правого нижнего угла достичь невозможно, то выходной файл должен содержать число − (минус один).

Ограничения

1 <= M <= N <= 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
7 2
.......
...@...
.......
..@....
.......
.......
....@..
10

0.063s 0.010s 13