8472: Bessie's Dream

在约翰的厨房里吃了太多的水果后，贝茜做了一些非常奇怪的梦。

在她最近的梦中，她被困到了一个迷宫中，迷宫可视为 N×M 的方格矩阵。

开始时她位于左上角的格子，出口在右下角的格子。

当她位于某个格子中时，她可以沿四个基本方向中的任意一个移动至相邻格子中。

可是等等！

每个格子都有一种颜色，每种颜色都有不同的属性！

贝茜一想到这个就感到头疼：

• 如果格子是红色的，则无法进入。
• 如果格子是粉色的，则可以正常通行。
• 如果格子是橙色的，则可以正常通行，但是进入此类格子会使贝茜闻起来像橙子。
• 如果格子是蓝色的，则里面包含食人鱼，只有贝茜闻起来像橙子时，她方可进入。
• 如果格子是紫色的，则贝茜沿某方向移动到紫色格子后，会沿着该方向滑动至下一个格子中（除非她无法进入下一个格子）。如果滑动至紫色格子，则继续滑动，直至进入非紫色格子或撞到无法进入的格子为止。进入紫色格子会使得自身气味消失。

（如果你对紫色格子感到困惑，样例将说明其具体用法。）

每从一个格子移动或滑动至另一个格子，算作一次移动。

请帮助贝茜在尽可能减少移动次数的情况下，到达出口。

输入格式

第一行包含两个整数 N 和 M。

接下来 N 行每行包含 M 个整数，表示迷宫：

• 0 表示红色格子
• 1 表示粉色格子
• 2 表示橙色格子
• 3 表示蓝色格子
• 4 表示紫色格子

左上角和右下角的数字一定是 1。

输出格式

输出贝茜到达出口所需的最少移动次数。

如果无法到达出口，则输出 −1。

数据范围

1≤N,M≤1000

4 4
1 0 2 1
1 1 4 1
1 0 4 0
1 3 1 1

10

样例解释

在此样例中，贝茜向下走一个格子，向右走两个格子（然后向右滑动一个格子），向上走一个格子，向左走一个格子，向下走一个格子（向下再滑动两个格子），最后向右走一个格子。

总共 10 次移动（下右右右上左下下下右）。