#1212. 「USACO 2015.12 Gold」Bessie's Dream

Bessie 在 Farmer John 的厨房暴食水果后，开始做奇怪的梦！在最近的梦境中，她被困在一个 的网格迷宫（）中。她需要从左上角的格子移动到右下角的格子。当站在某个格子时，她可以向四个基本方向移动至相邻格子。

但请注意！每个格子有不同的颜色和特殊属性：

• 红色（0）：不可通行
• 粉色（1）：可正常通行
• 橙色（2）：可正常通行，且会使 Bessie 带有橙子气味
• 蓝色（3）：仅当 Bessie 带有橙子气味时方可通行
• 紫色（4）：Bessie 将沿该方向滑动到下一个格子（除非无法通过）。若下一个格子仍是紫色，则继续滑动直至遇到非紫色格子或不可通行格子。每次滑动均计为一步移动，且紫色格子会消除 Bessie 的气味

（若对紫色格子机制有疑问，样例将帮助理解）

请帮助 Bessie 找到从左上角到右下角的最短路径步数。

第一行包含两个整数 和 ，表示迷宫的行数和列数。
接下来 行每行包含 个整数描述迷宫：

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

保证左上角和右下角的格子始终为 1。

输出一个整数，表示 Bessie 穿越迷宫所需的最少步数，若无法到达则输出 -1。

输入 #1

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

输出 #1

10

样例中，Bessie 的移动路径为：向下 1 步，向右 2 步（滑动再向右 1 步），向上 1 步，向左 1 步，向下 1 步（滑动再向下 2 步），最后向右 1 步。总计 10 步（路径表示为 DRRRULDDDR）。

题目提供者：Nathan Pinsker，灵感来自游戏《Undertale》