push.cpp

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

#include<fstream.h>
#include<ctype.h>
#include<limits.h>
#include<memory.h>

class Position {
public:
	operator int() const
		{
		return row;
		}
	int row,col,dir;
};

int op[4]={1,0,3,2};
int m,n,totm,markr;
int **grid,**reach,**mark,**low,**totr,***comp;
long ***ans;
Position start,finish,man;
Position offset[4];

int min(int,int);
void put(int,int,int,int);
void Prepro();
void fill(int,int);
int connect(int,int,int,int);
void dfs(int,int);
void FIFOBB();
bool ok(int,int);
void Out();
////////////////////////////////////////////////////////////////
char* OutOfBounds()
{
	char * s = "OutOfBounds()";
	return s;
}

template<class T> class Queue;

template<class T> class Node 
{
	friend Queue<T>;
	private:
		T data;
		Node<T> *next;
}; 

template<class T> class Queue
{
	public:
		Queue()
			{
			front=rear=0;
			}
		~Queue();
		bool IsEmpty() const
			{
			return((front)?false:true);
			}
		Queue<T> &Add(const T&x);
		Queue<T> &Delete(T&x);
	private:
		Node<T> *front;
		Node<T> *rear;
}; 

template<class T> Queue<T>::~Queue()
{
	Node<T> *next;
	while(front)
	{
		next=front->next;
		delete front;
		front=next;
	}
}

template<class T> Queue<T>&Queue<T>::Add(const T&x)
{
	Node<T> *p=new Node<T>;
	p->data=x;
	p->next=0;
	if(front)
		rear->next=p;
	else 
		front=p;
	rear=p;
	return *this;
} 

template<class T> Queue<T>&Queue<T>::Delete(T&x)
{
	if(IsEmpty()) throw OutOfBounds();
	x=front->data;
	Node<T> *p=front;
	front=front->next;
	delete p;
	return *this;
} 
/////////////////////////////////////////////////////////////////////
template <class T>
void Make2DArray(T** &x,int row,int col)
{
	x= new T* [row];
	for(int i=0;i<row;i++)
		x[i]=new T[col];
}

template <class T>
void Make3DArray(T*** &p,int h,int row,int col)
{
	p=new T** [h];
	int i,j;
	for (i=0; i<h; i++)
		p[i] = new T* [row];
	for (i=0; i<h; i++)
		for (j=0; j<row;j++)
			p[i][j]=new T[col];
}

int min(int a, int b)
{
	if(a>=b)
		return b;
	else
		return a;
} 

void Init()
{
	char c;
	ifstream input("input.txt");
	input>>n>>m;
	Make2DArray<int>(grid,n+2,m+2);
	Make2DArray<int>(reach,n+1,m+1);
	Make2DArray<int>(mark,n+1,m+1);
	Make2DArray<int>(low,n+1,m+1);
	Make2DArray<int>(totr,n+1,m+1);
	Make3DArray<long>(ans,n+1,m+1,4);
	Make3DArray<int>(comp,n+1,m+1,10);
	for(int i=0;i<n+2;i++)
		for(int j=0;j<m+2;j++)
			grid[i][j]=0;
	for(i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			input>>c;
			while(!isupper(c)&&!islower(c))
				input>>c;
			if(c=='M') man.row=i,man.col=j;
			if(c=='P') start.row=i,start.col=j;
			if(c=='K') finish.row=i,finish.col=j;
			if(c=='S') grid[i][j]=1;
		}
	for(i=0;i<=m+1;i++)
		grid[0][i]=grid[n+1][i]=1;
	for(i=0;i<=n+1;i++)
		grid[i][0]=grid[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;
	Prepro();
	for(i=0;i<=n;i++)
		for(int j=0;j<=m;j++)
		{
			reach[i][j]=0;
			for(int k=0;k<4;k++) ans[i][j][k]=LONG_MAX;
		}
	dfs(man.row,man.col);
}

void Prepro()
{
	totm=0;
	markr=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			mark[i][j]=-1;
			low[i][j]=INT_MAX;
			totr[i][j]=0;
			reach[i][j]=-1;
		}
	for(i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(grid[i][j]==0&&mark[i][j]==-1)
				fill(i,j);
}

void put(int x,int y,int a,int b)
{
	if(x==a&&y==b) return;
	if(reach[x][y]==2) return;
	comp[x][y][totr[x][y]]=markr;
	totr[x][y]++;
	reach[x][y]=2;
	for(int i=0;i<4;i++)
	{
		int x1=x+offset[i].row,y1=y+offset[i].col;
		if(grid[x1][y1]==0)
			put(x1,y1,a,b);
	}
}

void fill(int x,int y)
{
	for(int i=0;i<4;i++)
	{
		int x1=x+offset[i].row,y1=y+offset[i].col;
		if(grid[x1][y1]==0)
		{
			if(mark[x1][y1]==-1)
			{
				mark[x1][y1]=totm;
				totm++;
				fill(x1,y1);
				low[x][y]=min(low[x][y],low[x1][y1]);
				if(low[x1][y1]>=mark[x][y])
				{
					markr++;
					put(x1,y1,x,y);
					comp[x][y][totr[x][y]]=markr;
					totr[x][y]++;
					reach[x][y]=1;
				}
			}
		else
			low[x][y]=min(low[x][y],mark[x1][y1]);
		}
	}
}

int connect(int x1,int y1,int x2,int y2)
{
	for(int i=0;i<totr[x1][y1];i++)
		for(int j=0;j<totr[x2][y2];j++)
			if(comp[x1][y1][i]==comp[x2][y2][j])
				return 1;
	return 0;
}

void dfs(int x,int y)
{
	if(reach[x][y]==1) return;
	reach[x][y]=1;
	for(int i=0;i<4;i++)
	{
		int x1=x+offset[i].row,y1=y+offset[i].col;
		if(grid[x1][y1]==0&&(x1!=start.row||y1!=start.col))
			dfs(x1,y1);
	}
}

void FIFOBB()
{
	Queue<Position> Q;
	Position here,nbr;
	for(int i=0;i<4;i++)
	{
		nbr.row=start.row;
		nbr.col=start.col;
		nbr.dir=i;
		if(ok(start.row+offset[i].row,start.col+offset[i].col))
		{
			ans[start.row][start.col][i]=0;
			Q.Add(nbr);
		}
	}
	while(!Q.IsEmpty())
	{
		Q.Delete(here);
		int d=here.dir,x=here.row+offset[op[d]].row,y=here.col+offset[op[d]].col;
		if(grid[x][y]==0&&ans[x][y][d]>ans[here.row][here.col][d]+1)
		{
			ans[x][y][d]=ans[here.row][here.col][d]+1;
			nbr.row=x;
			nbr.col=y;
			nbr.dir=d;
			Q.Add(nbr);
			for(i=0;i<4;i++)
				if(i!=d)
					{
					int x1=x+offset[i].row,y1=y+offset[i].col;
					if(grid[x1][y1]==0&&connect(x1,y1,here.row,here.col)&&ans[x][y][i]>ans[x][y][d])
						{
						ans[x][y][i]=ans[x][y][d];
						nbr.row=x;
						nbr.col=y;
						nbr.dir=i;
						Q.Add(nbr);
						}
					}
		}
	}
}

bool ok(int a,int b)
{
	return grid[a][b]==0&&reach[a][b]==1;
}

int main()
{
	Init();
	FIFOBB();
	Out();
	return 0;
}

void Out()
{
	ofstream output("output.txt");
	for(long min=ans[finish.row][finish.col][0],i=1;i<4;i++)
		if(ans[finish.row][finish.col][i]<min) 
			min=ans[finish.row][finish.col][i];
	if(min==LONG_MAX) 
		output<<"NO Solution!";
	else
		output<<min;
}