wire.cpp

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

#include <iostream>
#include <fstream>
using namespace std;
struct Position
{
	int row,col;
	};
 	int **grid; 	
template <class T>
class Queue
{
	public:
		Queue(int Max=10);
		~Queue(){delete[] queue;}
		bool Empty() const{return front==rear;}
		bool Full()const{return((rear+1)%MaxSize==front?1:0);}
		Queue<T>&EnQueue(const T& x);
		Queue<T>& DeQueue(T& x);
	private:
		int front;
		int rear;
		int MaxSize;
		T*queue;
	};
template <class T>
Queue<T>::Queue(int Max)
	{
		MaxSize=Max-1;
		front=rear=0;
		queue=new T[MaxSize];
		}
template<class T>
Queue<T>&Queue<T>::EnQueue(const T&x)
	{
		if(Full()) throw "error";
			rear=(rear+1)%MaxSize;
			queue[rear]=x;
			return * this;
		}
template<class T>
Queue<T>&Queue<T>::DeQueue(T&x)
	{
		if(Empty()) throw "error";
		front=(front+1)%MaxSize;
		x=queue[front];
		return *this;
		}

int FindPath(Position start,Position finish,int & PathLen,Position *& path) 
//因为返回值要对PathLen 和Path做修改，所有必须使用引用，来返回地址
{
		if((start.row==finish.row)&&(start.col==finish.col))
		{PathLen=0;return 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 Num=4;
	Position here,nbr;
	here.row=start.row;
	here.col=start.col;
	grid[start.row][start.col]=2;
	Queue<Position> Q(100);
	do{
		for(int i=0;i<Num;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()) return 0;
		Q.DeQueue(here);
		}while(true);
		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<Num;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 1;
}

int main()
{   

	ifstream in("input.txt");
	if(in.fail())
	{
		cout<<"the input.txt is not exist!";
		exit(1);
	}
	ofstream out("output.txt");

	Position *path=new Position[1];//定义一个 path 数组用来存储Position点
	int i,m,j,k,row,col,PathLen,flag=0;
	in>>m>>k;
	grid=new int*[m+2];
	for(i=0;i<=m+1;i++)
		grid[i]=new int [m+2];
		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;
	for(i=1;i<=m;i++)
		for(j=1;j<=m;j++) grid[i][j]=0;
	for(i=1;i<=k;i++)
	{
		in>>row>>col;
		grid[row][col]=1;
		}
	Position start,finish;
	in>>row>>col; start.row=row;start.col=col;
	in>>row>>col; finish.row=row;finish.col=col;
	int a=FindPath(start,finish,PathLen,path);
	if(a==1){	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!";
	return 1 ;
}