2863: 重力鸭

小D最近在玩一个小游戏。 与一般游戏不同，这个游戏的主角并不能跳跃，只能够左右移动，而作为代替的 是，这个主角可以通过翻转重力的方向，来让自己达到目的地。 小D想知道，它最少需要翻转几次重力才能够成功地到达目的地。

游戏的地图是一个n*m的方阵。
在任何时候，角色可以选择向左移动，向右移动，或者翻转重力的方向。
在进行一次操作之前和之后，如果角色的位置向重力的方向的相邻格子是空的，那
么角色将会向那个方向跌落，直到遇到一个非空的格子或者离开地图。
任何时候，若玩家离开地图的范围，游戏被判定为失败。
请求得使用重力反转操作的最少次数。
重力方向初始向下，一次翻转操作可以将重力的方向由向下变为向上，或者由向
上变为向下。

• 第1行：两个正整数N,M，表示地图的宽和长。
• 第2 ∼ N + 1行：第i + 1行包含M个字符，表示地图。有且仅有下面的四种类型的
字符。
– .字符表示空的格子。
– #字符表示不可通行的障碍物。
– C字符表示起始点。
– D字符表示结束点。

• 第1行，包含一个整数，表示最少需要的翻转次数。如果无论如何都无法到达终
点，请输出-1

5 6
######
#...##
#...D#
#C...#
##.###

3