推箱子问题之分支界限法

码头仓库是划分为n×m个格子的矩形阵列。有公共边的格子是相邻格子。当前仓库中有的格子是空闲的（没有存放任何货物）；有的格子上则已经堆放了沉重的货物。堆放的货物太重了，单凭仓库管理员的力量是无法移动的。现在仓库管理员有一项任务，要将一个小箱子推到指定的格子上去。管理员可以在仓库中移动，但不得跨过沉重的不可移动的货物和箱子。当管理员站在与箱子相邻的格子上时，可以做一次推动，把箱子推到另一个相邻的格子

/*
算法实现题6-20 推箱子问题 

  问题描述： 
码头仓库是划分为n×m个格子的矩形阵列。有公共边的格子是相邻格子。当前仓库中
有的格子是空闲的；有的格子则已经堆放了沉重的货物。由于堆放的货物很重，单凭仓库管
理员的力量是无法移动的。仓库管理员有一项任务，要将一个小箱子推到指定的格子上去。
管理员可以在仓库中移动，但不能跨过已经堆放了货物的格子。管理员站在与箱子相对的空
闲格子上时，可以做一次推动，把箱子推到另一相邻的空闲格子。推箱时只能向管理员的对
面方向推。由于要推动的箱子很重，仓库管理员想尽量减少推箱子的次数。 

  编程任务： 
对于给定的仓库布局，以及仓库管理员在仓库中的位置和箱子的开始位置和目标位置，
设计一个解推箱子问题的分支限界法，计算出仓库管理员将箱子从开始位置推到目标位置所
需的最少推动次数。 

  数据输入： 
由文件input.txt提供输入数据。输入文件第 1 行有 2个正整数 n和 m（1<=nm<=100），
表示仓库是n×m个格子的矩形阵列。接下来有 n行，每行有 m个字符，表示格子的状态。 
S 表示格子上放了不可移动的沉重货物； 
w 表示格子空闲； 
M 表示仓库管理员的初始位置； 
P 表示箱子的初始位置； 
K 表示箱子的目标位置。 

  结果输出: 
将计算出的最少推动次数输出到文件 output.txt。如果仓库管理员无法将箱子从开始位
置推到目标位置则输出“No solution！”。 
输入文件示例  输出文件示例 
input.txt  output.txt 
10 12  7 
SSSSSSSSSSSS 
SwwwwwwwSSSS 
SwSSSSwwSSSS 
SwSSSSwwSKSS 
SwSSSSwwSwSS 
SwwwwwPw

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        147  2008-09-08 14:43  inpu4.txt

     文件        231  2008-09-08 15:28  input9.txt

     文件        147  2008-09-08 15:30  input.txt

     文件         12  2008-09-10 15:03  output.txt

     文件       8752  2009-06-08 10:38  push.cpp

     文件      73366  2008-09-05 16:38  push.pdf

----------- ---------  ---------- -----  ----

                82655                    6