题目描述

After eating too much fruit in Farmer John's kitchen, Bessie the cow is getting some very strange dreams! In her most recent dream, she is trapped in a maze in the shape of an $N×M$ grid of tiles $(1≤N,M≤1,000)$. She starts on the top-left tile and wants to get to the bottom-right tile. When she is standing on a tile, she can potentially move to the adjacent tiles in any of the four cardinal directions.

But wait! Each tile has a color, and each color has a different property! Bessie's head hurts just thinking about it:

• If a tile is red, then it is impassable.

• If a tile is pink, then it can be walked on normally.

• If a tile is orange, then it can be walked on normally, but will make Bessie smell like oranges.

• If a tile is blue, then it contains piranhas that will only let Bessie pass if she smells like oranges.

• If a tile is purple, then Bessie will slide to the next tile in that direction (unless she is unable to cross it). If this tile is also a purple tile, then Bessie will continue to slide until she lands on a non-purple tile or hits an impassable tile. Sliding through a tile counts as a move. Purple tiles will also remove Bessie's smell.

(If you're confused about purple tiles, the example will illustrate their use.)

Please help Bessie get from the top-left to the bottom-right in as few moves as possible.

输入格式

The first line has two integers $N$ and $M$, representing the number of rows and columns of the maze.

The next $N$ lines have $M$ integers each, representing the maze:

• The integer '0' is a red tile

• The integer '1' is a pink tile

• The integer '2' is an orange tile

• The integer '3' is a blue tile

• The integer '4' is a purple tile

The top-left and bottom-right integers will always be '1'.

输出格式

A single integer, representing the minimum number of moves Bessie must use to cross the maze, or -1 if it is impossible to do so.

题目大意

有一个 $N\times M$ 的棋盘，Bessie 开始时在左上角的格子，她要移动到右下角的格子上。当 Bessie 位于一个格子上时，她只能移动到与之有公共边的相邻格子。棋盘上的格子按照颜色可分为红、粉、橙、绿、紫五类。

• 红色格子：不能通过。
• 粉色格子：可以自由通过。
• 橙色格子：可以自由通过，但 Bessie 通过橙色格子后会沾上橙子味。
• 绿色格子：当且仅当 Bessie 身上有橙子味时，Bessie才能通过绿色格子。
• 紫色格子：Bessie 会在上面漂移（除非她漂移的方向上有一个不能通过的格子），并且 Bessie 身上的橙子味会消失。举个例子，如果 Bessie 从紫色格子左边的格子移动到紫色格子上，

• 如果右边是粉/橙色格子：Bessie 会滑到右边。
• 如果右边是红/绿色格子，或者右边是边界：Bessie 会停在当前紫色格子上。
• 如果右边仍然是紫色格子：Bessie 会滑到右边，然后继续根据这一规定来漂移。

请问 Bessie 最少需要移动多少步。

Translated by @Planet6174

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

10

提示

In this example, Bessie walks one square down and two squares to the right (and then slides one more square to the right). She walks one square up, one square left, and one square down (sliding two more squares down) and finishes by walking one more square right. This is a total of 10 moves (DRRRULDDDR).

Problem credits: Nathan Pinsker, inspired by the game "Undertale".