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 \times M grid of tiles (1 \le N, M \le 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.

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

#3943 upload 2 done 1 how_to_reg 1

Bessie's Dream timer 2s memory 512MB

#3943

Bessie's Dream 2s 512MB