P2208 [USACO13OPEN] What's Up With Gravity S
题目描述
Bovidian 船长正在拯救她的船员，Beefalo 博士。
和所有伟大的冒险故事一样，这个故事也是发生在一个 2D 平面上的。
这个平面是 $M\times N$（$1\le N,M \le500$）的格子组成的网格，代表着船长的世界的一个侧视图。
有些格子是空的，另一些则是实心的，并且不能直接通过。
很不幸的是，船长跳不起来。她必须遵守这个世界的特殊物理法则。
1. 如果船长的正下方没有方块（换句话说，即使她正在网格的边缘），那么她就会掉入宇宙中，同时意味着冒险失败。
2. 如果船长的正下方的方块是空的，那么她就会掉到这个方块。
3. 在不满足 1. 与 2. 的情况下，船长可以做以下的事情：
1. 如果左边（或右边）的方格是空的，那么她可以走到那个格子。
2. 船长可以翻转重力的方向。
当船长改变翻转重力的方向时，我们就改变船长“下方”的定义。
“下方”的定义只能是两种：
1. 比船长位置所在的方格的列编号更大的格子。
2. 比船长位置所在的方格的列编号更小的格子。
一开始的时候，“下方”的定义是比船长位置所在方格的列编号更大的格子。
Beefalo 博士正迷失在这个世界中的某一处，请帮助船长从起点到达博士的地方。
如果可以到达，请输出最少需要的翻转重力的次数。
如果不可以到达，请输出 $-1$。
输入格式
第 $1$ 行输入两个整数 $N,M$。
第 $2$ 行到 $N+1$ 行中，第 $i+1$ 行则是代表船长世界的第 $i$ 行。每行有 $M$ 个字符。
其中 `,` 代表着一个空的格子，`#` 代表着一个实心的格子，`C` 代表着船长的位置，`D` 代表着博士的位置。
输出格式
一行，输出一个整数。
如果船长可以到达，请输出最少需要的翻转重力的次数。
如果不可以到达，请输出 $-1$。
说明/提示
输出解释：
首先，船长在 $(4,2)$，接着她翻转重力，到达 $(2,2)$。
接着她向右走走到 $(2,4)$，接着她第二次翻转重力，到达 $(4,4)$。
然后她继续向右走到 $(4,5)$，最后在翻转一次重力，到达博士所在的 $(3,5)$。