#P27. Madeline在路上
Madeline在路上
问题描述
现在,一个手残党在玩平台跳跃游戏,你决定去帮助他。
在这个游戏中,每一次玩家可以在以下操作中选择可以执行的操作去执行。
当你下方有障碍物时,你可以选择以下操作:
1 左移一格
2 右移一格
3 上跳一格后立刻再上移一格。
4 上跳一格后立刻再上移一格,然后立刻左移一格
5 上跳一格后立刻再上移一格,然后立刻右移一格
当你下方没有障碍物时,你可以选择以下操作:
6 下落一格
7 下落一格,然后立刻左移一格
8 下落一格,然后立刻右移一格
对于操作:
当且仅当一个操作涉及的所有点均无障碍物,且满足前提条件时,我们才认为该操作可以使用。例如,当你上方第二格存在障碍物时,操作3,4,5均不可以执行。
每个操作都不可以移动到一半停下,例如操作3,不可以上跳一格后就停下。对于一个可行的操作,要么不做,要么做完。
如果我们某一次操作时,路径经过了终点B,但操作结束时玩家所在的位置不是终点B,我们认为没有到达终点
你将看到一个 的方格图,其中, #
代表障碍物, A
代表起点, B
代表终点。请输出求从起点到终点的最小操作次数。如果不可达,输出 。
对于地图:
保证地图最外圈为障碍物(减少代码量,快说谢谢出题人)。
保证只有一个起点和一个终点。
不保证一点存在从起点到终点到路径,不存在请输出-1。
输入格式
第一行,两个整数 。
接下来有 行,每行 个字符,代表地图。
第 行,第 个为 。
输出格式
一个整数,表示最小操作次数。
输入样例
输出样例
评测数据规模
对于所有评测数据: ,