wire.cpp

FZU 大二 的数据结构与算法 老师出的题目的优秀作业 第2到第5章

#include<iostream>
#include<fstream>
#include<ctime>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
class Position
{
public:
	Position(){row=col=0;}
	bool FindPath();
	void Print();
private:
	int row;
	int col;
};
class Node
{
	friend class Queue;
private:
	Position data;
	Node *next;
};
class Queue
{
	friend class Position;
public:
	Queue(){front=rear=0;}
	~Queue();
	bool Empty(){return ((front)? false:true);}
	Position First();
	Position Last();
	Queue &EnQueue(Position x);
	Queue &DeQueue(Position &x);
private:
	Node *front;
	Node *rear;
};
Queue::~Queue()
{
	Node *next;
	while(front)
	{
		next=front->next;
		delete front;
		front=next;
	}
}

Position Queue::First()
{
	if(Empty())
	throw;
	return front->data;
}
Position Queue::Last()
{
	if(Empty())
		throw;
	return rear->data;
}
Queue &Queue::EnQueue(Position x)
{
	Node *p=new Node;
	p->data=x;
	p->next=0;
	if(front)
		rear->next=p;
	else 
		front=p;
	rear=p;
	return *this;
}
Queue &Queue::DeQueue(Position &x)
{
	if(Empty())
		throw;
	x=front->data;
	Node *p=front;
	front=front->next;
	delete p;
	return *this;
}
void Position::Print()
{
	out<<row<<" "<<col<<endl;
}
bool Position::FindPath()
{
	if(in.fail())
	{
		cout<<"the input.txt is not exist!";
		exit(1);
	}
	int m,n;
	in>>m;
	int **grid=new int *[m+2];
	for(int i=0;i<m+2;i++)
		grid[i]=new int[m+2];
	for(i=1;i<m+1;i++)
		for(int j=1;j<m+1;j++)
			grid[i][j]=0;
	int x,y;
	in>>n; 
	for(i=0;i<=n-1;i++)
	{
		in>>x>>y;
		grid[x][y]=1;
	}
	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; 
	int PathLen=0;	
	Position start,finish;
	in>>start.row>>start.col>>finish.row>>finish.col;
	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;
	if((start.row==finish.row)&&(start.col==finish.col))
	{
		PathLen=0;
		out<<PathLen<<endl;
		out<<row<<' '<<col<<endl;
		return true; 
	}
	Position here,nbr;
	here.row=start.row;
	here.col=start.col;
	grid[start.row][start.col]=2;
	Queue Q;
	do
	{
		for(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))
					break;
				Q.EnQueue(nbr);
			}
		}
		if((nbr.row==finish.row)&&(nbr.col==finish.col))
			break; 
		if(Q.Empty())
			return false; 
		Q.DeQueue(here);
	}while(true);
	PathLen=grid[finish.row][finish.col]-2;
	out<<PathLen<<endl;
	Position *path=new Position[PathLen+1];
	here=finish;
	for(int j=PathLen;j>=0;j--)
	{
		path[j]=here;
		for(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+1)
				break;
		}
		here=nbr;
	}
	for(i=0;i<=PathLen;i++)
		path[i].Print();
	return true;
}

int main()
{

	clock_t start,finish;
	start=clock();
	Position obj;
	obj.FindPath();
	finish=clock();
	out<<double(finish-start)/CLOCKS_PER_SEC<<"ms";
	return 0;
}