首页 > ACM题库 > HDU-杭电 > hdu 4457 Klotski待解决[解题报告]C++
2015
07-16

hdu 4457 Klotski待解决[解题报告]C++

Klotski

问题描述 :

Klotski game is coming again!

Crowd


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.

输出:

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.

样例输入:

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

样例输出:

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


  1. 有本事不要扯这些,军方直接派人到美国搞生化心理战嘛!现在还发出这种蔑视生命和人权的话不觉得自己可笑吗?我看美国的心理战没有搞垮中国,倒是某些头脑发热的人会失掉民心,那才人家正中下怀!这种智商还敢给高层出主意,我呸!