### 问题描述 给定一个二维 $N \times M$ 的网格，表示小齐的冒险世界。网格中包含空白单元格和阻塞单元格，小齐不能跳跃。她必须遵循以下物理规则： 如果小齐处于网格的边缘，即下方没有单元格，则她将飞向太空，任务失败。 如果小齐下方的单元格为空白，则她会掉落到该单元格。 否则： $a:$ 小齐可以向左或向右移动，如果对应的单元格存在且为空白。 $b:$ 或者，小齐可以翻转重力方向。 当小齐改变重力方向时，位于她下方的单元格（在规则 $1$ 和规则 $2$ 中提到的位置）在具有较高行索引的单元格和具有较低行索引的单元格之间切换（输入的第一行的索引为 $1$，最后一行的索引为$N$）。初始情况下，具有较高行索引的单元格位于小齐的下方。 此外，博维迪安船长要营救一名叫“牛肉博士”的船员。协助小齐以尽可能少的重力翻转次数到达牛肉博士的位置。如果无法到达牛肉博士，请输出 $-1$。 ### 输入格式 第 $1$ 行：两个用空格分隔的整数 $N$ 和 $M$。 第 $2$ 行至 $1+N$ 行：第 $i+1$ 行描述博维迪安船长的冒险世界的第 $i$ 行。其中，$'.'$ 表示空白单元格，# 表示阻塞单元格，$'C'$ 表示博维迪安船长的起始位置，$'D'$ 表示牛肉博士的起始位置。 ### 输出格式 一个整数，表示博维迪安船长为到达牛肉博士所需的最小重力翻转次数。如果无法到达牛肉博士，请输出 $-1$。 ### 样例输入 ``` 5 5 ##### #...# #...D #C... ##.## ``` ### 样例输出 ``` 3 ``` ### 评测数据规模 $1 \leq N, M \leq 500$。