wire.cpp

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

// wire.cpp : Defines the entry point for the console application.
//
#include<iostream.h>
#include<fstream.h>
template<class T> class Queue;
template<class T> class Node;
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()) {cout<<"OutOfBounds"<<endl;}
	return front->data;
}


template<class T>
T Queue<T>::Last() const
{
	if(Empty()) {cout<<"OutOfBounds"<<endl;}
	return 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()) {cout<<"OutOfBounds"<<endl;}
	x=front->data;
	Node<T> *p=front;
	front=front->next;
	delete p;
	return *this;
}
//=============================================================================================

class Position
{
private:
	int row; //所在行
	int col; //所在列
public:
    bool FindPath();
};

void main()
{
    Position P;
	P.FindPath();
	
}


bool Position::FindPath()
{
	ifstream input("input.txt"); 
	ofstream output("output.txt"); 
	int grid[500][500];
    Position start;
	Position finish;
    int i,j,t,m,k,PathLen,a,b;
	input>>m>>k;
	for(i=0;i<m;i++)
	{
		for(j=0;j<m;j++)
		{
			grid[i][j]=0;
		}
	}
	for(t=0;t<k;t++)
	{
		input>>a>>b;
		grid[a][b]=1;
	}
	input>>start.row>>start.col;
	input>>finish.row>>finish.col;
	if((start.row==finish.row)&&(start.col==finish.col))
	{PathLen=0;return true;} // start=finish
	//设置方格阵列“围墙”
	for(i=0;i<=m+1;i++)
	{grid[0][i]=grid[m+1][i]=1;} //顶部和底部
	for(i=0;i<=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;    //上
	int NumOfNbrs=4;    //相邻方格数
	Position here,nbr;
	here.row=start.row;
	here.col=start.col;
	grid[start.row][start.col]=2; //block
	//标记可达方格位置
	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);
			}
		}
		//是否到达目标位置finish?
		if((nbr.row==finish.row)&&(nbr.col==finish.col)) break;//完成布线
		//待考察方格队列是否非空
		if(Q.Empty()) {output<<"No Solution!"<<endl;return false;}//无解
		Q.DeQueue(here);//取下一个考察方格
	}while(true);
	//构造最短布线路径
	PathLen=grid[finish.row][finish.col]-2;
    output<<PathLen<<endl;
    Position *path=new Position[PathLen];
	//从目标位置finish开始向起始位置回溯
	here=finish;
	for(j=PathLen-1;j>=0;j--)
	{
		path[j]=here;//找前驱位置
		for(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;//向前移动
	}
    output<<start.row<<" "<<start.col <<endl;
	for(i=0;i<PathLen;i++)
	{output<<path[i].row<<" "<<path[i].col<<endl;}
	return true;
}