The goal is to move Large Red Tile to the middle of the right side.
Hopefully we'll add here interactive game in javascript later...
The initial idea to think about problem with sliding blocks came from Radovan Markus in this forum post - thanks a lot!
The game of "Klotski" is an evolution of 15 puzzle: we have rectangular box with rectangular tiles sliding inside. The goal is to move one of the blocks to certain place at opposite side. Read more in wikipedia. You'll easily find the game for Windows, Linux or Android (probably the same for other OSes) - and web-based - so feel free to have some practice.
We will describe the game position with latin letters: the same letter is for squares of the same tile. The empty squares are marked with dots. Here are two examples:
ABBC FDAI ABBC DAFC
DBBE FECI ABBC DAFC
FGHI => J..M DEEF => EEGH
FJKI GBBH DGHF JBB.
L..M LBBK I..J IBB.
In both the largest 2x2 tile (marked with "B") is initially in the middle of the top side.
And the goal in both cases is to move it to the middle of the bottom side. However the first variant (actually,
the same represented by animation above, though rotated 90 degrees clockwise) has 2 tiles of 2x1 size and 10
single-square tiles, so it is easy. The second has only 4 single-square tiles and 5 doubles - and due to their
orientation it is much more difficult.
Obviously for every variant is an "optimal" solution - the one with the smallest number of moves. We count as
single move any move of single tile, even if it travels more than 1 square, even if not in straigt line. The
"easy" variant could be solved in 17 moves, while "hard" variant - in 81. It is difficult to solve, but to
find optimal solution may be even much harder!
Problem Statement
So in this problem we are given several variants of the puzzle and need to determine the "length" (i.e. moves count) for optimal solution.
Input data
The first line contains N - the number of testcases.
Then testcases follow, each starting with description line, which gives size of field (width by height) and the
goal (letter of the block and the X:Y coordinate of its top-left corner in the final position).
Then the field is given in the format shown above.
Output data
Just N values, telling the move count of optimal solution for each testcase (space separated).
Example:
input data:
2
field 4 by 5 ; move B to 1 : 3
ABBC
DBBE
FGHI
FJKI
L..M
field 5 by 4 ; move B to 3 : 1
AADDI
BBEG.
BBEH.
CCFFJ
expected answer:
17 81
please note the format of description line - there are spaces between every element so it is easier to split and extract numbers...
P.S. for blocks which have cutout at top-left corners the goal coordinate is for the leftmost square in the topmost row. Though probably we'll avoid cases with such shapes for simplicity.