Дан лабиринт размером $$$N \times M$$$ клеток. В верхнем левом углу лабиринта находится квадрат со стороной $$$P$$$ клеток. За один шаг квадрат может перемещаться на одну клетку вверх, вниз, вправо или влево, если при этом он не столкнется с занятыми клетками. Необходимо найти наименьшую возможную длину пути, по которой квадрат может добраться до нижнего правого угла.
В первой строке вводятся три числа $$$N$$$, $$$M$$$, $$$P$$$. Далее идет $$$N$$$ строк по $$$M$$$ символов, обозначающих клетки лабиринта: '.', если клетка свободна, 'X', если занята. Гарантируется, что верхний левый и нижний правый квадраты $$$P \times P$$$ не содержат занятых клеток.
Выведите наименьшую возможную длину пути, или $$$-1$$$, если такого пути не существует.
5 5 2...XX....XX...XXX...XX...
6
5 5 2...XX...XXXX.XXXX...XX...
-1
Подзадача 1 (до 20 баллов): $$$1 \leq N,M \leq 10$$$, $$$P = 1$$$
Подзадача 2 (до 20 баллов): $$$1 \leq N,M \leq 2000$$$, $$$P = 1$$$
Подзадача 3 (до 20 баллов): $$$1 \leq N,M \leq 50$$$, $$$P = 2$$$
Подзадача 4 (до 20 баллов): $$$1 \leq N,M \leq 2000$$$, $$$1 \leq P \leq min(50,N,M)$$$
Подзадача 5 (до 20 баллов): $$$1 \leq N,M \leq 2000$$$, $$$1 \leq P \leq min(N,M)$$$
| Название |
|---|


