wire.cpp

这是一个关于小白鼠迷宫的问题

#include<iostream.h>
#include<fstream.h>
#include<iomanip.h>
ifstream in("input.txt");
ofstream out("output.txt");
class OutOfBounds
{
public:
	OutOfBounds()
	{   cout<<"OutOfBounds!"<<endl;   }
};
class NoMem
{
public:
	NoMem()
	{   cout<<"NoMem!"<<endl;   }
};
template<class T>
class Queue
{
	private:
		int front;
		int rear;
		int MaxSize;
		T * queue;
	public:
		Queue(int Max=100)
		{
			MaxSize=Max+1;
			queue=new T[MaxSize];
			front=rear=0;
		}
		~Queue(){  delete [] queue;  }
		bool Empty() const {return front==rear;  }
		bool Full() const {return (((rear+1)%MaxSize==front)?1:0);}
		T First() const
		{
			if(Empty())
				throw OutOfBounds();
			return queue[(front+1)%MaxSize];
		}
		T Last() const
		{
			if(Empty())
				throw OutOfBounds();
			return queue[rear];
		}
		Queue<T> & EnQueue(const T &x)
		{
			if(Full()) throw NoMem();
			rear=(rear+1)%MaxSize;
			queue[rear]=x;
			return * this;
		}
		Queue<T> & DeQueue(T & x)
		{
			if(Empty())
				throw OutOfBounds();
			front=(front+1)%MaxSize;
			x=queue[front];
			return * this;
		}
};
class Position
{
public:
	int row,col;
};

bool FindPath(int m,Position start,Position finish,int & PathLen,Position * &path,int **grid)
{
	if((start.row==finish.row)&&(start.col==finish.col))
	{PathLen=0;return true;}
	for(int i=0;i<=m+1;i++)
		grid[0][i]=grid[m+1][i]=grid[i][0]=grid[i][m+1]=1;
	Position offset[4];
	offset[0].row=0;offset[0].col=1;
	offset[1].row=1;offset[1].col=0;
	offset[2].row=0;offset[2].col=-1;
	offset[3].row=-1;offset[3].col=0;
	Position here,nbr;
	here.row=start.row;
	here.col=start.col;
	grid[start.row][start.col]=2;
	Queue<Position> Q((m+2)*(m+2));
	do
	{
		int flag=0;
		for(int i=0;i<4;i++)
		{
			nbr.row=here.row+offset[i].row;
			nbr.col=here.col+offset[i].col;
			if(grid[nbr.row][nbr.col]==0)
			{
				grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;
				if((nbr.row==finish.row)&&(nbr.col==finish.col))
				{    flag=1;  break;    }
				try{Q.EnQueue(nbr);}catch(NoMem){};
			}
		}
		if(flag)
			break;
		if(Q.Empty()) return false;
		try{Q.DeQueue(here);}catch(OutOfBounds){};
	}while(true);
	
/*	for(i=0;i<m+2;i++)
	{
		for(int j=0;j<m+2;j++)
			cout<<setw(2)<<grid[i][j]<<"  ";
		cout<<endl;
	}
*/

	PathLen=grid[finish.row][finish.col]-2;
	path=new Position[PathLen];
	here=finish;
	for(int j=PathLen-1;j>=0;j--)
	{
		path[j]=here;
		for(int i=0;i<4;i++)
		{
			nbr.row=here.row+offset[i].row;
			nbr.col=here.col+offset[i].col;
			if(grid[nbr.row][nbr.col]==j+2)
				break;
		}
		here=nbr;
	}
	return true;
}

int main()
{
	int i,j,m,k,a,b,**grid,PathLen;
	Position * path;
	in>>m>>k;
	grid=new int * [m+2];
	for(i=0;i<m+2;i++)
		grid[i]=new int [m+2];
	for(i=0;i<m+2;i++)
		for(j=0;j<m+2;j++)
			grid[i][j]=0;
	for(i=0;i<k;i++)
	{
		in>>a>>b;
		grid[a][b]=1;
	}
	Position start,finish;
	in>>start.row>>start.col>>finish.row>>finish.col;
	if(FindPath(m,start,finish,PathLen,path,grid))
	{
		out<<PathLen<<endl;
		out<<start.row<<" "<<start.col<<" "<<endl;
		for(i=0;i<PathLen;i++)
			out<<path[i].row<<" "<<path[i].col<<" "<<endl;
	}
	else
		out<<"No Solution!"<<endl;
	return 0;
}