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