#P27. Madeline在路上

Madeline在路上

问题描述

现在,一个手残党在玩平台跳跃游戏,你决定去帮助他。

在这个游戏中,每一次玩家可以在以下操作中选择可以执行的操作去执行。

当你下方有障碍物时,你可以选择以下操作:

1 左移一格

2 右移一格

3 上跳一格后立刻再上移一格。

4 上跳一格后立刻再上移一格,然后立刻左移一格

5 上跳一格后立刻再上移一格,然后立刻右移一格

当你下方没有障碍物时,你可以选择以下操作:

6 下落一格

7 下落一格,然后立刻左移一格

8 下落一格,然后立刻右移一格

对于操作:

当且仅当一个操作涉及的所有点均无障碍物,且满足前提条件时,我们才认为该操作可以使用。例如,当你上方第二格存在障碍物时,操作3,4,5均不可以执行。

每个操作都不可以移动到一半停下,例如操作3,不可以上跳一格后就停下。对于一个可行的操作,要么不做,要么做完。

如果我们某一次操作时,路径经过了终点B,但操作结束时玩家所在的位置不是终点B,我们认为没有到达终点

你将看到一个 n×mn \times m 的方格图,其中, # 代表障碍物, A 代表起点, B 代表终点。请输出求从起点到终点的最小操作次数。如果不可达,输出 1-1

对于地图:

保证地图最外圈为障碍物(减少代码量,快说谢谢出题人)。

保证只有一个起点和一个终点。

不保证一点存在从起点到终点到路径,不存在请输出-1。

输入格式

第一行,两个整数 n,mn, m

接下来有 nn 行,每行 mm 个字符,代表地图。

ii 行,第 jj 个为 ci,jc_{i, j}

输出格式

一个整数,表示最小操作次数。

输入样例

5 5
#####
#...#
#...#
#A.B#
#####

输出样例

评测数据规模

对于所有评测数据:1n,m1031 \le n, m \le 10^3ci,j{#,A,B} c_{i, j} \in \{ \#,A,B \}