box.cpp

由文件input.txt提供输入数据。输入文件第1 行有2个正整数n和m（1<=n,m<=100）

#include<iostream>
#include<fstream>
#include<queue>
using namespace std;

struct Position
{
	short row;
	short col;
};
struct GirdState
{
	short row;
	short col;
	int step;
	int totle;
	Position manPos;
};
struct Compare
{
public:
	bool operator() (const GirdState &x, const GirdState &y) const
	{
		return x.totle > y.totle;
	}
};


ifstream fin("input.txt");   //文件输入输出
ofstream fout("output.txt");

int n, m;  //n 行数， m列数
Position offset[4];//定义搜索四个方向	
Position start, finish, manPos, oppnboxpos; //start：箱子的初始位置；finish：箱子的目标位置；manPos：人的位置；人是在oppnboxpos把箱子往nboxpos位置推
short **menFlag ;//标志方格状态-1为障碍，0为空闲
short **temp ;//临时存放menFlag的数组
bool ***girdFlag;//标志方格的四个方向是否空闲
GirdState boxPos, nboxpos;//boxpos：箱子所在位置，nboxpos：推之后箱子的位置
priority_queue< GirdState, vector< GirdState >, Compare> Q;//可扩展结点队列，经过大小排列的队列 ?



bool CanArrive(Position &manPos, Position &oppnboxpos, GirdState &boxPos, short **menFlagtemp) //人能否到达到oppnboxpos的位置,人是在oppnboxpos把箱子往nboxpos位置推
{
	queue <Position> pos1, pos2;

	Position start = manPos, finish = oppnboxpos, from, to, temp1, temp2;

	if(start.row == finish.row && start.col == finish.col) 
		return true;
		
	from = start;
	to = finish;
	menFlagtemp[boxPos.row][boxPos.col] = -1;//箱子不动，人不能走箱子所在的位子
	menFlagtemp[from.row][from.col] = 1;     //人出发点（走过）
	menFlagtemp[to.row][to.col] = 2;         //目标点

	for(;;)
	{  
		for(int i = 0; i <4 ; i ++)    //start（manPos）和 finish（oppnboxpos）四周围可走的点入队
		{
			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()
{
	fin >> 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 ++)
	{
		girdFlag[i] = new bool* [m + 2];    //因为要判断四个方向，从而产生边界问题，于是增加4条边(第0行，n+1行，0列，m+1列)
		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 ++)     
		{
			fin >> 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')
			{
				finish.row = i;
				finish.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')
			{
				manPos.row = i;
				manPos.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;//下边
}

int excute()
{
		
	
	boxPos.row = start.row;
	boxPos.col = start.col;
	boxPos.step = 0;
	boxPos.manPos = manPos;
    
	do
	{
		  for(int i = 0; i < 4; i ++)   //搜索四个方向
		  {
			  nboxpos.row = boxPos.row + offset[i].row;    //nboxpos和oppnboxpos始终在箱子的两侧
			  nboxpos.col = boxPos.col + offset[i].col;

			  oppnboxpos.row = boxPos.row - offset[i].row;
			  oppnboxpos.col = boxPos.col - offset[i].col;
			
		  	  if(menFlag[nboxpos.row][nboxpos.col] == 0 && girdFlag[nboxpos.row][nboxpos.col][i] && menFlag[oppnboxpos.row][oppnboxpos.col] == 0)  //在i方向，人可以走到推箱子的位置并且箱子可以推向前 且此位置没人走过
			  {
				
				   for(int k = 0; k < n + 2; k ++)
					    for(int j = 0; j < m + 2; j ++)
						     temp[k][j] = menFlag[k][j];
				   
				   if(CanArrive(boxPos.manPos, oppnboxpos, boxPos, temp))   //人是否可以到达oppnboxpos的位置（人是在oppnboxpos把箱子往nboxpos位置推）
				   {
				
					    nboxpos.step = boxPos.step + 1;
					    if(nboxpos.row == finish.row && nboxpos.col == finish.col)  //箱子再推一步就达到目标终点
						{
						     fout << nboxpos.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 0;
						}

					    nboxpos.manPos.row = boxPos.row;
					    nboxpos.manPos.col = boxPos.col;

					    nboxpos.totle = nboxpos.step + abs(nboxpos.row - finish.row) + abs(nboxpos.col - finish.col);  //优先队列的优先级的定义为：当前位置与目标位置的横纵坐标差的绝对值和+箱子在该点时已经走过的步数;为了能够最快的到达目标位置,我们每次从队列中取优先级最低的值。

					    Q.push(nboxpos);

					    girdFlag[nboxpos.row][nboxpos.col][i] = false;  //此位置此方向已走过(注意并不是位置被走过)，作false标记避免重复

				   }
			  }
		  }
		
		  if(Q.empty())
		  {
			   fout << "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 0;
		  }
		
		  boxPos = Q.top();
		  Q.pop();
		  //下面一行为测试，应去掉
		  //fout << "("<<boxPos.row<<","<<boxPos.col<<")"<<"totle="<<boxPos.totle<<" man:"<<boxPos.manPos.row<<","<<boxPos.manPos.col<<"  step:"<<boxPos.step<<endl; 
	}while(true);
	return 0;

}

void main()
{

	Init();//数据初始化
	excute();//执行过程

}