推箱子
《推箱子问题的设计与实现》实验报告
班级：计本一班学号：2012020186 姓名：姚驷旭
一、问题描述
码头仓库是划分为n×m个格子的矩形阵列。有公共边的格子是相邻格子。当前仓库中有的格子是空闲的；有的格子则已经堆放了沉重的货物。由于堆放的货物很重，单凭仓库管理员的力量是无法移动的。仓库管理员有一项任务，要将一个小箱子推到指定的格子上去。管理员可以在仓库中移动，但不能跨过已经堆放了货物的格子。管理员站在与箱子相对的空闲格子上时，可以做一次推动，把箱子推到另一相邻的空闲格子。推箱时只能向管理员的对面方向推。由于要推动的箱子很重，仓库管理员想尽量减少推箱子的次数。
二、问题求解分析
对于给定的仓库布局，以及仓库管理员在仓库中的位置和箱子的开始位置和目标位置，设计一个解推箱子问题的分支限界法，计算出仓库管理员将箱子从开始位置推到目标位置所需的最少推动次数。
三、源程序关键代码
#include
#include
using namespace std;
struct Position
{
short row;
short col;
};
struct GirdS
{
short row;
short col;
int step;
int totle;
Position man_s;
};
struct Compare
{
public:
bool operator() (const GirdS &x, const GirdS &y) const
{
return x.totle >y.totle; }
};
ifstream in_f("input.txt"); ofstream out_f("output.txt");
int n, m;
//定义搜索四个方向
Position offset[4];
//start：箱子的初始位置；end：箱子的目标位置；man_s：人的位置；人是在man_t把箱子往nbox_e位置推Position start, end, man_s,
man_t;
//标志方格状态-1为障碍，0为空闲short **menFlag ;
//临时存放menFlag的数组
short **temp ;
//标志方格的四个方向是否空闲
bool ***girdFlag;
//box_s：箱子所在位置，nbox_e：
推之后箱子的位置
GirdS box_s, nbox_e;
//可扩展结点队列，经过大小排列的
队列 ?
priority_queue< GirdS, vector<
GirdS >, Compare> Q;
//人能否到达到man_t的位置,人是
在man_t把箱子往nbox_e位置推
bool CanArrive(Position &man_s,
Position &man_t, GirdS &box_s,
short **menFlagtemp)
{
queue
Position start = man_s, end =
man_t, from, to, temp1, temp2;
if(start.row == end.row &&
start.col == end.col)
return true;
from = start;
to = end;
menFlagtemp[box_s.row][box_s.col]
= -1;//箱子不动，人不能走箱子所在
的位子
menFlagtemp[from.row][from.col]
= 1; //人出发点（走过）
menFlagtemp[to.row][to.col] = 2; //目标点
for(;;)
{
for(int i = 0; i <4 ; i ++) //start（man_s）和 end（man_t）四周围可走的点入队
{
temp1.row = from.row +
offset[i].row;
temp1.col = from.col +
offset[i].col;
if(menFlagtemp[temp1.row][temp1. col] == 2) //到达目标点
return true;
if(menFlagtemp[temp1.row][temp1. col] == 0) //经过没走过的点
{
menFlagtemp[temp1.row][temp1.col] = 1; //设置人走过的标记
pos1.push(temp1);
}
temp2.row = to.row +
offset[i].row;
temp2.col = to.col +
offset[i].col;
if(menFlagtemp[temp2.row][temp2. col] == 1) //人可以走到目标点return true;
if(menFlagtemp[temp2.row][temp2. col] == 0)
{
menFlagtemp[temp2.row][temp2.col] = 2; //能走到目标点的四周，就可以走到目标点
pos2.push(temp2);
}
}
if(pos1.empty() || pos2.empty()) //如果temp1 或 temp2四周围无可走点，返回false
return false;
from = pos1.front();
pos1.pop();
to = pos2.front();
pos2.pop();
}
}
void Init()
{
in_f >> n >> m;
char c;//读入方格标志字符
menFlag = new short* [n + 2];//标
志方格状态-1为障碍，0为空闲
temp = new short* [n + 2];//临时
存放menFlag的数组 girdFlag = new bool** [n + 2];//标志方格的四
个方向是否空闲
for(int i = 0; i < n + 2; i ++)
{
//因为要判断四个方向，从而产生边
界问题，于是增加4条边(第0行，n+1行，0列，m+1列)
girdFlag[i] = new bool* [m + 2]; menFlag[i] = new short [m + 2]; temp[i] = new short [m + 2];
}
//刚开始初始化的时候是不知道周围
否是空闲，只能先给个初始化的值，
然后在后面程序中判断
for(i = 1; i < n + 1 ; i ++)
for(int j = 1; j < m + 1; j ++) {
in_f >> c;
if(c == 'S')
{
girdFlag[i][j] = 0;
menFlag[i][j] = -1; //-1表示障
碍不可走
}
else if(c == 'w')
{ menFlag[i][j] = 0; //0表示可走，尚未被人走过 girdFlag[i][j] = new bool [4]; for (int k = 0; k < 4; k ++) girdFlag[i][j][k] = true ; } else if (c == 'P') { start.row = i; start.col = j; menFlag[i][j] = 0; girdFlag[i][j] = new bool [4]; for (int k = 0; k < 4; k ++) girdFlag[i][j][k] = true ; } else if (c == 'K') { end.row = i; end.col = j; menFlag[i][j] = 0; girdFlag[i][j] = new bool [4]; for (int k = 0; k < 4; k ++) girdFlag[i][j][k] = true ; } else if (c == 'M') { man_s.row = i; man_s.col = j; menFlag[i][j] = 0; girdFlag[i][j] = new bool [4]; for (int k = 0; k < 4; k ++) girdFlag[i][j][k] = true ; } } for (i = 0; i <= m + 1; i ++) //设置上下边界障碍边：无四个方向，人不可到达 {
girdFlag[0][i] = girdFlag[n + 1][i] = 0; menFlag[0][i] = menFlag[n + 1][i] = -1; } for (i = 0; i <= n + 1; i ++) //设置左右边界障碍边：无四个方向，人不可到达 { girdFlag[i][0] = girdFlag[i][m + 1] = 0; menFlag[i][0] = menFlag[i][m + 1] = -1; } // 初始化移动的相对位置 offset[0].row = 0; offset[0].col = -1;//左边 offset[1].row = 0; offset[1].col = 1;//右边 offset[2].row = -1; offset[2].col = 0;//上边 offset[3].row = 1; offset[3].col = 0;//下边 } void main() { Init();//数据初始化 box_s.row = start.row; box_s.col = start.col; box_s.step = 0; box_s.man_s = man_s; do {
for (int i = 0; i < 4; i ++) //搜索四个方向 {
nbox_e.row =
box_s.row + offset[i].row;
//nbox_e和man_t始终在箱子的两侧 nbox_e.col =
box_s.col + offset[i].col;
man_t.row =
box_s.row - offset[i].row;
man_t.col =
box_s.col - offset[i].col;
//在i方向，人可以走到推箱子的位置并且箱子可以推向前且此位置没人走过
if(menFlag[nbox_e.row][nbox_e.co l] == 0 &&
girdFlag[nbox_e.row][nbox_e.col] [i] \
&&
menFlag[man_t.row][man_t.col] == 0)
{
for(int k = 0; k < n + 2; k ++)
for(int j = 0; j < m + 2; j ++)
temp[k][j] = menFlag[k][j];
//人是否可以到达man_t的位置（人是在man_t把箱子往nbox_e位置推）
if(CanArrive(box_s.man_s, man_t, box_s, temp))
{
nbox_e.step = box_s.step + 1;
//箱子再推一步就达到目标终点if(nbox_e.row == end.row && nbox_e.col == end.col)
out_f << nbox_e.step;
for(i = 0; i < n + 2; i ++)
{
delete [] menFlag[i];
delete [] temp[i];
}
delete menFlag;
delete temp;
for(i = 0; i < n + 2; i ++)
{
for(int j = 0; j < m + 2; j ++)
{
if(girdFlag[i][j])
delete [] girdFlag[i][j];
}
delete [] girdFlag[i];
}
delete girdFlag;
return;
}
nbox_e.man_s.row = box_s.row;
nbox_e.man_s.col = box_s.col;
/*
优先队列的优先级的定义为：当前位置与目标位置的横纵坐标差的绝对
值和+箱子在该点时已经走过的步数;为了能够最快的到达目标位置,我们
每次从队列中取优先级最低的值。*/
nbox_e.totle = nbox_e.step + abs(nbox_e.row - end.row) + \ abs(nbox_e.col - end.col); Q.push(nbox_e);
//此位置此方向已走过(注意并不是位置被走过)，作false 标记避免重复
girdFlag[nbox_e.row][nbox_e.col][i] = false ;
} } }
if (Q.empty()) {
out_f << "No solution!"
;
for (i = 0; i < n + 2; i ++)
{
delete [] menFlag[i];
delete [] temp[i];
}
delete menFlag; delete temp;
for (i = 0; i < n + 2; i ++)
{
for (int j = 0; j < m + 2; j ++) {
if (girdFlag[i][j])
delete [] girdFlag[i][j];
}
delete [] girdFlag[i]; }
delete girdFlag;
return ; }
box_s = Q.top(); Q.pop(); }while (true ); return ; }
总结
通过这次试验，我更加注重动手能力。在以后的编程中我会独立思考，争取事事
亲为。培养自己的动手能力。
五、参考文献
无