题目描述

卢卡斯被困在了一个二维迷宫中。

这个二维迷宫可以看成一个 $n$ 行 $m$ 列的网格。我们用 $(i, j)$ 表示迷宫中第 $i$ 行第 $j$ 列的那个格子。

格子包含以下两种类型：

• A：表示一种类型可以通行的格子；
• B：表示另一种类型可以通行的格子；
• #：表示不能通行的墙壁。

卢卡斯初始时在迷宫的左上角 $(1,1)$ 位置，它需要移动到迷宫的右下角 $(n,m)$ 位置，那里是迷宫的出口。

每次移动，卢卡斯可以从当前格子移动到上、下、左、右相邻的格子，但是不能移动到不可通行的墙壁，也不能移动到迷宫外。

移动到相同类型的格子（即：从格子 A 移动到格子 A，或从格子 B 移动到格子 B）的代价是 $1$；

移动到不同类型的格子（即：从格子 A 移动到格子 B，或从格子 B 移动到格子 A）的代价是 $2$；

求：卢卡斯从迷宫的左上角移动到迷宫的右下角的最小总代价。

输入格式

第一行，两个整数 $n$ 和 $m$，以空格分隔，表示迷宫的行和列。

接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，表示这个二维迷宫。

输出格式

如果卢卡斯不存在任何可行的方案，输出一行 $-1$。

否则，输出一个整数，表示卢卡斯从迷宫的左上角移动到迷宫的右下角的最小总代价。

样例

2 3
AA#
#AB

4

5 5
ABABA
B#A#B
BA#AB
A##B#
BA#AB

19

4 3
A##
BBB
AA#
A#B

-1

说明/提示

数据规模与约定

• 对于 $10\%$ 的数据，$n,m \le 5$
• 对于 $30\%$ 的数据，$n,m \le 50$
• 对于 $100\%$ 的数据，$2 \le n,m \le 500$，起点 $(1, 1)$ 是可通行的格子。