问题描述

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

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

当你下方有障碍物时，你可以选择以下操作：

1 左移一格

2 右移一格

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

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

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

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

6 下落一格

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

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

对于操作：

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

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

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

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

对于地图：

保证地图最外圈为障碍物（减少代码量，快说谢谢出题人）。

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

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

输入格式

第一行，两个整数 $n, m$ 。

接下来有 $n$ 行，每行 $m$ 个字符，代表地图。

第 $i$ 行，第 $j$ 个为 $c_{i, j}$ 。

输出格式

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

输入样例

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

输出样例

2

评测数据规模

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