Klotski game is coming again!
Klotski (from Polish klocki—wooden blocks) is a sliding block puzzle. Sometimes it only refers to the block arrangement in the right-hand-side diagram, where the largest block (in red) must be moved to the bottom middle location (marked in blue). In a more global sense, Klotski refers to a whole group of similar sliding-block puzzles where the aim is to move a specific block to some predefined location.
But today, I will re-define the game for you.
The board is a n×m grid. There are some blocks on it. A block covers one or more cells of the grid. These blocks are 4-connected. There are also some empty cells on the board. Every step you can move only one block up or down or to the left or to the right , and two blocks can never overlap.
Here the problem comes: giving you two layouts of board, calculate the least step(s) that needed to move blocks so that the board can be transferred from one layout to another.