Klotski

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.
From Wikipedia.org

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.

There are several test cases.
For each test, the first line has three integers n,m and k, indicating that the board is n×m and there are k blocks on it. ( 0< n,m<=20, 0<=k<=10).
The following n lines describe the starting layout. Every line has m characters representing m cells. '.' represents an empty cell and ‘0’~’9’ indicates a cell covered by a block. The none-empty cells which represented by the same characters are all covered by a same block and one block can only cover cells represented by the same characters.
The next n lines describe the ending layout.
Input ends with n = 0 ,m= 0, and k=0.

For each test case you should output a line with an integer indicating the least step(s) needed to transform the starting layout into the ending layout.

5 4 10
48..
6200
6200
7311
7359
7632
7632
4811
.005
.009
0 0 0

46

About seventy percent of the test cases are of n<=10 and m<=10. There are exactly 10 test cases.

2012 Asia Hangzhou Regional Contest