Bessie's Dream

题目描述

在 Farmer John 的厨房里吃了太多水果后，奶牛 Bessie 做起了一些非常奇怪的梦！在她最近的一个梦里，她被困在一个形状为 $N \times M$ 的方格迷宫中（$1 \le N, M \le 1,000$）。她从左上角的格子出发，想要到达右下角的格子。当她站在一个格子上时，她可以尝试向上下左右四个方向移动到相邻的格子。

但是等等！每个格子都有一种颜色，而每种颜色都有不同的性质！Bessie 一想到这些就头疼： 如果一个格子是 red ，那么它不可通过。 如果一个格子是 pink ，那么它可以正常行走。 如果一个格子是 orange ，那么它可以正常行走，但会让 Bessie 身上带有橘子味。 如果一个格子是 blue ，那么里面有食人鱼，只有当 Bessie 身上有橘子味时才允许她通过。 如果一个格子是 purple ，那么 Bessie 会在该方向上滑到下一个格子（除非她无法穿过它）。如果下一个格子仍然是 purple，那么 Bessie 会继续滑行，直到她停在一个非 purple 的格子上，或撞到一个不可通过的格子为止。滑过一个格子也算作一次移动。 Purple 格子还会消除 Bessie 身上的气味。 （如果你对 purple 格子感到困惑，样例会展示它们的用法。）

请帮助 Bessie 用尽可能少的移动次数从左上角到达右下角。

输入格式

第一行包含两个整数 $N$ 和 $M$，表示迷宫的行数和列数。 接下来 $N$ 行每行包含 $M$ 个整数，表示迷宫： 整数 '0' 表示 red 格子 整数 '1' 表示 pink 格子 整数 '2' 表示 orange 格子 整数 '3' 表示 blue 格子 整数 '4' 表示 purple 格子 左上角与右下角的整数一定为 '1'。

输出格式

输出一个整数，表示 Bessie 穿过迷宫所需的最少移动次数；如果无法做到则输出 -1。

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

10

提示

在这个例子中，Bessie 先向下走一格，再向右走两格（然后再向右滑动一格）。她向上走一格、向左走一格、向下走一格（向下再滑动两格），最后再向右走一格结束。这一共是 10 次移动（DRRRULDDDR）。 题目鸣谢：Nathan Pinsker，灵感来自游戏 "Undertale"。

标签: USACO|2015|Gold

来源

USACO|2015|Gold