Problem C
Crate Chucking
You are playing a game on a grid. You must move a 2x1x1 crate from the starting cell where it starts in an upright position, to the target cell where it must also be in an upright position. The game is played by toppling over the crate in one of the four cardinal directions on a cartesian grid. Toppling over a standing create means it will occupy the two next cells in the direction you toppled it. A crate lying down can be toppled in two ways, either such that it keeps lying on its side, or in a way that makes it stand up. Toppling a standing crate will always make it lie down. When toppling the create over, it will occupy the neighboring squares in the direction it was pushed. In the example figure there are four consecutive valid states to illustrate how the crate moves on the grid.
To make the game more interesting, the board it is played on contains obstacles. Some cells are therefore blocked, meaning the crate may never occupy those squares.
In addition to reaching the final cell in an upright position, you want to minimize the amount of energy used. To topple a standing crate over only costs one unit of energy. Toppling over a lying crate such that is still lies sideways costs two units of energy. Taking it from a lying to standing position costs 3 units of energy.
You use your keyboard’s four arrow keys to indicate in which direction you want to move the crate next. There is only one problem, your keyboard is broken! It is broken in a peculiar way where you may never press the same arrow key twice in a row. In the starting position you may assume no arrow key was the previous button press.
What is the least amount of energy you must use to reach the final position, given your faulty keyboard?
Input
The first line of input contains two numbers. $H$, which is the height of the cartesian grid, and $W$, which is the width. $H$ lines follow which are strings of W characters each. The strings contain the following characters.
-
".", indicating that the cell free to move on
-
"B", indicating that the cell is blocked and unavailable to the crate
-
"S", indicating the starting position of the crate, where it stands at the start of the game
-
"E", indicating the ending position of the crate, where it must stand at the end of the game
Output
Output the least amount of energy used to move from the starting to the ending position. If no solution exists under the given limitations you must output "impossible".
Limits
-
$1 \leq H, W \leq 200$
| Sample Input 1 | Sample Output 1 |
|---|---|
4 4 S... B... B... B..E |
16 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 3 S.. E.. |
6 |
