28554번 - Паякан в беде 다국어

Полковник Куорич и его приспешники преследуют тулкуна Паякана на добывающем корабле. Неподалеку располагается база На'ви и тулкун уже почти почувствовал себя спасенным. Однако, чтобы добраться до базы, ему необходимо преодолеть рифовые заграждения. Поле из рифовых заграждений представляет собой прямоугольник из клеток размера $n \times m$, каждая из клеток может быть либо рифом, либо водой.

Тулкун имеет длину $k$ и ширину $1$, и хочет проплыть эти рифы как можно быстрее. Тулкуны весьма неповоротливы, поэтому могут двигаться только вперед и назад относительно своего текущего направления (от хвоста к голове), а также поворачивать на $90^\circ$ по следующим правилам: если голова тулкуна длины $k$ находилась в точке $(i, j)$, то после поворота его хвост окажется в точке $(i, j)$, а голова в точке $(i + k - 1, j)$ или $(i - k + 1, j)$, если он был ориентирован горизонтально, и в точке $(i, j + k - 1)$ или $(i, j - k + 1)$, если он был ориентирован вертикально. Ниже показаны оба поворота из горизонтального положения для $k > 1$ и $k = 1$ (во втором случае меняется только направление):

Каждый сдвиг на одну клетку и каждый поворот занимают у Паякана одну единицу времени.

Изначально Паякан может заплыть на поле в любой ориентации, то есть занять либо клетки $(1, 1) \ldots (1, k)$, либо $(1, 1) \ldots (k, 1)$, при этом его голова будет находиться либо в точке $(1, k)$, либо в точке $(k, 1)$. Считается, что вы спасете его, если он окажется головой в правой нижней клетке рифового поля, то есть в точке $(n, m)$. Помогите Паякану спастись и определите, за какое время он сможет оказаться в правом нижнем углу, или скажите, что это невозможно.

В первой строке через пробел даны три целых числа $n$, $m$ и $k$ --- размеры поля и длина тулкуна ($1 \leqslant n, m \leqslant 1000$; $1 \leqslant k \leqslant \min(n, m)$; $n \cdot m \leqslant 10^5$).

В следующих $n$ строках дано описание поля, каждая строка имеет длину $m$ и состоит из символов '\#' соответствует рифу, символ '.' --- воде.

Выведите одно число --- количество действий, которое надо совершить тулкуну, чтобы попасть в правый нижний угол поля, или $-1$, если это невозможно.

В первом примере тулкун может начать в направлении <<вправо>>, проплыть две клетки вперед, повернуться по часовой стрелке и сделать еще два движения вперед. В сумме перемещение занимает $5$ действий.

Путь тулкуна во втором примере показан на рисунке ниже. Маленькие стрелки соответствуют перемещениям головы вперед или назад, а большие --- поворотам.