wire.cpp

设计一个算法

#include<iostream>
#include<fstream>
using namespace std;
class Position
{
public:
	bool FindPath();
private:
   	  int row;
	  int col;
};
class Node{
	friend class Queue;
	private:
		Position data;
		Node *next;
};
class Queue{
	public:
		friend class Position ;
		Queue() {front=rear=0;}
		~Queue();
		bool Empty()
		{return((front)?false:true);}
		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;
	}
}
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)
{
	x=front->data;
	Node *p=front;
	front=front->next;
	delete p;
	return *this;
}
bool Position::FindPath()
{
	Position start,finish;
    int PathLen,a,b;
	ifstream in("input.txt");
	ofstream out("output.txt");
	if(!in.is_open())
	{
        out<<"error"<<endl;
        exit(1);
    }
    int m,k;
	in>>m>>k;
	int **grid=new int*[m+2];
	for(int p=0;p<m+2;p++)
		grid[p]=new int[m+2];
	for(int i=0;i<m;i++)
	  for(int j=0;j<m;j++)
		grid[i][j]=0;
	for(int t=0;t<k;t++)
	{
		in>>a>>b;
		grid[a][b]=1;
	}
	
	in>>start.row>>start.col;
	in>>finish.row>>finish.col;
    if((start.row ==finish.row )&&
		(start.col ==finish.col ))
	{PathLen=0;return true;}
	for(int c=0;c<=m+1;c++)
		grid[0][c]=grid[m+1][c]=1;
	for(int f=0;f<=m+1;f++)
		grid[f][0]=grid[f][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;
	Queue 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 false;
		}
		Q.DeQueue(here);
	} while(true);
	PathLen=grid[finish.row][finish.col]-2;
	out<<PathLen<<endl;
	Position * 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<<start.row <<" "<<start.col <<endl;
	for(int r=0;r<PathLen;r++)
		out<<path[r].row <<" "<<path[r].col<<endl;
	delete[]path;
	for(i=0;i<m+2;i++)
		delete []grid[i];
	delete[] grid;
    in.close();
    out.close();
	return true;
}
int main()
{
    Position wire;
	wire.FindPath();
	return 0;
}