题目描述

VRX 今天又开颓了。

VRX 在颓一个走迷宫游戏。游戏给了一个 $n\times m$ 的迷宫，每次只能往上、下、左、右四个位置之一走。VRX 需要从左上角走到右下角。

但如果仅仅如此肯定难不住 X 大队长，这个迷宫上的每个位置都有一个颜色，走迷宫时必须保证下一步的颜色和当前位置的颜色一样才行。

请你帮 X 大队长算算最快多少步才能从左上角走到右下角吧！

比如对于下面这个例子：

123123
111112
122212
311111
212222
111111

从左上角走到右下角最快路径如下（用X标注）

X23123
XXXXX2
1222X2
3XXXX1
2X2222
1XXXXX

输入格式

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

接下来 $n$ 行，每行是一个长度为 $m$ 的字符串。表示了迷宫的地图（每个位置的颜色用数字字符表示）。

输出格式

一行一个整数，表示最快多少步才能从左上角走到右下角。

6 6
123123
111112
122212
311111
212222
111111

16

数据规模与约定

• 对于 $10\%$ 的数据，每个位置的颜色都一样。
• 对于 $100\%$ 的数据，$1 < n,m \le 200$，题目保证至少有一种方式可以从起点走到终点。