Bessie's Dream#11162
After eating too much fruit in Farmer John's kitchen, Bessie the cow is having some very strange dreams! In her most recent dream, she is trapped in a maze in the shape of an n \times m grid of tiles. She starts on the top-left tile and wants to reach the bottom-right tile. When standing on a tile, she can potentially move to an adjacent tile 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 it makes 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 that tile is also a purple tile, then Bessie will continue to slide until she lands on a non-purple tile or reaches an impassable tile. Sliding through a tile counts as a move. Purple tiles also remove Bessie's orange smell.
Please help Bessie get from the top-left tile to the bottom-right tile in as few moves as possible.
The first line contains two integers and m~(1 \le n, m \le 1000), representing the number of rows and columns in the maze.
The next lines each contain integers representing the maze:
The integer represents a red tile.
The integer represents a pink tile.
The integer represents an orange tile.
The integer represents a blue tile.
The integer represents a purple tile.
The top-left and bottom-right tiles will always contain .
Print one integer representing the minimum number of moves Bessie must make to cross the maze, or if it is impossible to do so.
If you're confused about how purple tiles work, the example below illustrates their behavior.
In this example, Bessie walks one square down and two squares to the right, then slides one more square to the right. She then walks one square up, one square left, and one square down, sliding two more squares down. Finally, she walks one more square to the right. This takes a total of moves (DRRRULDDDR).
Example 1