Problem B
BBBBBB
Our favourite game developer Saskia has started on a new game, called BBBBBB! In this game, you’re Captain Biryan and have to save your crew. They have been scattered around in an alternate dimension named bbbbbb.
The game consists of a number of puzzles in a 2D grid, where you are the @ symbol and have to get to the X. # represents immovable blocks, and ^ and v are deadly spikes. The player, playing Captain Biryan, can do one of three actions:

Move one tile right (if the tile does not contain a #)

Move one tile left (if the tile does not contain a #)

Flip gravity: If gravity is pulling down, it is now pulling you up instead (and vice versa)
The game logic is rather short and can be summarised by this pseudocode:
gravity_direction = down while true: if player is at the location of the 'X': return WIN if player is at the location of a '^' or 'v': return DEAD if player does not touch the ground: player_y += 1 * gravity_direction continue (restart loop from the top) if player touches the ground: perform_next_player_action()
Touching the ground is defined as being placed exactly one tile above or below a #, depending on which way gravity pulls.
To ensure that there’s a good variety of puzzles in the game, Saskia wants to implement a shortest path algorithm that finds the minimum number of gravity flips needed to solve a puzzle.
Input
The first line consists of two integers $W$ and $H$, representing the width and the
height of the 2D grid to be parsed.
Then follows $H$ lines
each consisting of a string of length $W$. Each string can only contain the
characters ‘ ’, ‘#’, ‘v’, ‘^’, ‘@’
and ‘X’.
Output
Output the minimum number of gravity flips needed to solve
the puzzle, along with the number of user actions needed. If
there are multiple solutions with the same number of gravity
flips, output the one with the least amount of user actions
needed.
If there is no valid path to the exit, output ‘impossible!’ (without the quotes).
Limits

$4 \leq W, H \leq 450$

The border of the map can only contain ‘#’, ‘v’ and ‘^’ tiles.

The grid will only contain the characters‘ ’, ‘#’, ‘v’, ‘^’, @ and X, and there will be exactly one @ and one X symbol in the grid.
Sample Input 1  Sample Output 1 

11 6 #####vv#### # # # # # # #####v # # @ X# ######^^### 
4 15 
Sample Input 2  Sample Output 2 

10 4 #^^^^^^^^# # # #@ X# ##vvvvvv## 
impossible! 