P4818 [USACO15DEC] Bessie's Dream G

Bessie 在 Farmer John 的厨房暴食水果后，开始做奇怪的梦！在最近的梦境中，她被困在一个 $N \times M$ 的网格迷宫（$1 \leq N,M \leq 1,000$）中。她需要从左上角的格子移动到右下角的格子。当站在某个格子时，她可以向四个基本方向移动至相邻格子。 但请注意！每个格子有不同的颜色和特殊属性： - **红色（0）**：不可通行 - **粉色（1）**：可正常通行 - **橙色（2）**：可正常通行，且会使 Bessie 带有橙子气味 - **蓝色（3）**：仅当 Bessie 带有橙子气味时方可通行 - **紫色（4）**：Bessie 将沿该方向滑动到下一个格子（除非无法通过）。若下一个格子仍是紫色，则继续滑动直至遇到非紫色格子或不可通行格子。**每次滑动均计为一步移动**，且**紫色格子会消除 Bessie 的气味** （若对紫色格子机制有疑问，样例将帮助理解） 请帮助 Bessie 找到从左上角到右下角的最短路径步数。

无

无

样例中，Bessie 的移动路径为：向下 1 步，向右 2 步（滑动再向右 1 步），向上 1 步，向左 1 步，向下 1 步（滑动再向下 2 步），最后向右 1 步。总计 10 步（路径表示为 DRRRULDDDR）。 题目提供者：Nathan Pinsker，灵感来自游戏《Undertale》