wire.cpp

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

#include <iostream>
#include<fstream>
using namespace std;
  ifstream  in("input.txt");
  ofstream  out("output.txt");
class  Position{
public :
   int 	row,col;

  	  Position&EnPosition(int r,int c)
	 {row=r;col=c;return *this;}
       
};


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 Empty()const
		{return ((front)? false:true);}
        bool Full()const;
        T First()const;
        T Last()const;
        Queue<T>&EnQueue(const T&x);
        Queue<T>&DeQueue(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>
bool Queue<T>::Full()const
{
	Node<T>*p;
	try {p=new Node<T>;
	delete p;return false;}
	catch(NoMem){return true;}
}

template<class T>
T Queue<T>::First()const
{
	if(Empty())throw 0;
	return front->data;
}

template<class T>
T Queue<T>::Last()const 
{
	 if(Empty())throw 0;
	 reurn rear->data;
}

template<class T>
Queue <T>&Queue<T>::EnQueue(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>::DeQueue(T&x)
{
	if(Empty())throw 0;
	x=front->data;
	Node<T>*p=front;
	front=front->next;
	delete p;
	return *this;
}

int main()
{
	int m,k,PathLen;
    

	int **grid;
	Position start,finish;
  	in>>m>>k;
    Position  *B;
	B=new  Position[k];
 
	for(int i=0;i<k;i++)
	{
        int R,C;
		in>>R>>C;
	    B[i].EnPosition(R,C);
	}
	 int M,N;
    in>>M>>N;
	start.EnPosition(M,N);
    int O,P;
	in>>O>>P;
     finish.EnPosition(O,P);
   
	 if((start.row==finish.row)&&(start.col==finish.col))
	 { PathLen=0;
	    out<< PathLen<<endl;
	     return  0;}
	

    grid=new int * [m+2];
    for(int y=0;y<=m+1;y++)
     grid[y]=new int [m+2]; 
        for(int t=0;t<=m+1;t++)
			for(int f=0;f<=m+1;f++)
				grid[t][f]=0;

	 for(int c=0;c<=m+1;c++)
		 grid[0][c]=grid[m+1][c]=1;
	  for(int b=0;b<=m+1;b++)
		  grid[b][0]=grid[m+1][b]=1;
	  for(int a=0;a<k;a++)
		  grid[B[a].row][B[a].col]=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;
  int NumOfNbrs=4;
  Position here,nbr;
  here.row=start.row;
  here.col=start.col;
  grid[start.row][start.col]=2;
  Queue<Position> Q;
  do{
	  for(int i=0;i<NumOfNbrs;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))break;
		Q.EnQueue(nbr);}
	  }
	if((nbr.row==finish.row)&&(nbr.col==finish.col))break;
  
 if(Q.Empty()) {out<< "No Solution!";return 0;}
  Q.DeQueue(here);
  }while(1);
  PathLen=grid[finish.row][finish.col]-2;
  Position *path;
  path=new Position[PathLen];
  here=finish;
  for(int j=PathLen-1;j>=0;j--){
	  path[j]=here;
  for(int i=0;i<NumOfNbrs;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;
  }
  out<<PathLen<<endl;
  out<<start.row<<' '<<start.col<<endl;
  for(int d=0;d<PathLen;d++)
  out<<path[d].row<<' '<<path[d].col<<endl;
  return 0;
}