Капитан Bovidian спасает члена экипажа, доктора Beefalo. Как во всех великих приключениях, мир показан сбоку двумерной сеткой $N \times M$ ($1 \le N, M \le 500$). Есть пустые и заблокированные непроходимые клетки.
Капитан не умеет прыгать и следует правилам физики.
Если непосредственно снизу нет клетки (край сетки), она улетает в космос и проваливает миссию.
Если клетка снизу пуста, она падает в неё.
Иначе: a) Можно двигаться влево или вправо, если соответствующая клетка существует и пуста. b) Или перевернуть направление гравитации.
При перевороте «снизу» (правила 1, 2) переключается между клеткой с номером строки на 1 больше и на 1 меньше. Первая строка входа — 1, последняя — $N$. Изначально снизу строка на 1 больше.
Доктор затерялась в мире. Достигните её клетки с минимумом переворотов гравитации. Если невозможно, выведите -1.
Входные данные
- Строка 1: целые $N$, $M$ через пробел.
- Строки $2..1+N$: строка $i+1$ описывает ряд $i$ мира. '.' — пустая клетка, '#' — заблокированная, 'C' — старт капитана, 'D' — старт доктора.
Выходные данные
- Строка 1: целое, минимум переворотов до доктора, либо -1 при невозможности.
Примеры
Входные данные 1
5 5 ##### #...# #...D #C... ##.##
Выходные данные 1
3
Примечание
Капитан из (4,2) переворачивает гравитацию, падает в (2,2), идёт вправо дважды в (2,4). Снова переворачивает, падает в (4,4), идёт вправо в (4,5). Последний переворот приводит к доктору в (3,5).
Автор задачи: Mark Gordon, 2013