来自"NOCOW"

这是Ural上的一个经典难题，提交次数 2000多次，AC人数目前只有 6

个，通过率不到 1% !

   首先，先分析一下这个题的数据范围，圈墙，所以实际面积最多只有 6*6，也就是说箱子的个数最多也就 35。 

       ########           ########           ######## 
       #$       $#        #....     #        #   .     # 
       #.       .#        #   $$    #        #        $# 
       #     @    #       #   $$    #        #.        # 
       #.       .#        #         #        #     @   # 
       #$       $#        #     @   #        #   $     # 
       ########           ########           ######## 

   接着是确定搜索的方法，因为是多个箱子，所以为了方便写，只好一步推 

一个箱子，直到所有的箱子都归位。但是这样很容易出现的一个局面就是死锁。

比如一个箱子推到了墙角，4个箱子相互靠在了一起，一个箱子贴在了没有目

标点的一边墙上等等。

   当然死锁远远不止这些，有些人一眼就能看出来，但电脑却不一定了，而 

且频繁地判断死锁会降低程序的效率。既然正想比较麻烦，不如反向思考，将

推箱子变成拉箱子，这样就不会出现上诉的种种死锁了，一步就解决的问题。

于是通过将推箱子变成拉箱子，第一个程序就出来了，同时，为了加速，我用

上了hash，我用他跑了一下几组数据，基本没出解，不过样例过了。而且

键部分还没出来呢。

   这里我们定义一个局面S(P，Q，pos)，P为箱子的集合，Q为目标点的 

集合，pos 为当前人的位置。因为是写迭代加深，所以自然而然的想到了估价。

通过迭代加深，我们枚举答案上限MAX，设到当前局面的代价是g，如果g

+h>MAX，便可以剪枝，从而大大提高效率。

   对于估价函数，一个较显然的结论是，点(x1，y1)到点(x2，y2)的花费 

至少是他们的曼哈顿距离|x1-x2|+|y1-y2|，那么我们设计估价h(s)为：

            h(s)=∑min{|Xi-Xj|+|Yi-Yj|，j∈Q}，i∈P 

                                                         4 
   这样的估价效果如何呢？这里我选了33组数据进行测试: 
test            生成节点                test              生成节点 

0*    3 3 3 597 5360 23115...       17    3 44 5935 5703 

1     4 4 4 185 34                  18    3 176 421 164 

2     3 43 69                       19    8 233 56 

4 打*表示最终没有跑出解来 题目保证n，m≤8，去掉外边的一