maze.cpp

设计一个算法

#include <fstream>
using namespace std;
class list;
class map;
class Node
{
	friend list;
	friend map;
private:
	long x,y;
	long x1,y1;
	long f,g,h;
	Node *next;
} ;
class list
{
private:
	long n;
	Node *head;
public:
	list():n(0),head(0) {}
	list & Insert(Node *);
	int process(Node *);
	Node *GetNextNode(Node *);
	Node *GetHead();
	bool empty();
	~list();
};

list::~list ()
{
	Node * current;
	while(head)
	{
		current=head->next;
		delete head;
		head=current;
	}
}
list& list::Insert(Node *p)
{
	Node *current=head,*q=head;
	if(!head)
	{
		head=p;
		n++;
		return *this;
	}
	while(current && current->f < p->f ) 
	{
		q=current;
		current=current->next ;
	}
	if(current==head)
	{
		head=p;
		p->next = current;
	}
	else if(current)
	{
		p->next = current;
		q->next = p;
	}
	else
	{
		q->next=p;
		p->next=0;
	}
	n++;
	return *this;
}

int list::process (Node *p)    
{
	Node *current=head,*q=head;
	if(!head)
		return 1;
	while(current&&(current->x !=p->x ||current->y !=p->y ))
	{
		q=current;
		current=current->next;
	}
	if(!current)
		return 1;
	if(current->f >p->f )       
	{
		if(current==q)
		{
			head=q->next;
		}
		q->next=current->next;
		delete current;
		n--;
		return 2;
	}
	return 3;
}
Node *list::GetNextNode (Node * p)
{
	Node *current=head;
	while(current&&(p->x1!=current->x||p->y1!=current->y))
		current=current->next;
	return current;
}

Node * list::GetHead()
{
	Node * p;
	p=head;
	head=head->next;
	n--;
	return p;
}
bool list::empty()
{
	return !n;
}


class map
{
public:
	map(ifstream &);
	void init();
	bool search();
	void display(ofstream &);
	~map();
private:
	long di[4][2];
	list open,close;
	long m;
	bool **a;
	long p,q;
	long r,s;
};
map::map(ifstream &in)
{
	di[0][0]=-1,di[0][1]=0,di[1][0]=0,di[1][1]=1,
	di[2][0]=1,di[2][1]=0,di[3][0]=0,di[3][1]=-1;
	long i,k,x,y;
	in>>m>>k;
	a=new bool *[m];
	for(i=0;i<m;i++)
		a[i]=new bool[m];
	for(long j=0;j<m;j++)
		for(i=0;i<m;i++)
			a[j][i]=true;
	for(i=0;i<k;i++)
	{
		in>>x>>y;
		a[x-1][y-1]=false;
	}
	in>>p>>q>>r>>s;
}
void map::init()
{
	Node *pn=new Node;
	pn->g=0;
	pn->f=pn->h=abs(p-r)+abs(q-s);
	pn->next =0;
	pn->x=p;
	pn->y=q;
	pn->x1=0;
	pn->y1=0;
	open.Insert(pn);
}
bool map::search()
{
	Node *current,*next;
	long i;
	int result;
	while(!open.empty ())
	{
		current=open.GetHead();
		for(i=0;i<4;i++)
		{
			next=new Node;
			next->x=current->x+di[i][0];
			next->y=current->y+di[i][1];
			if(next->x < 1||next->x > m||next->y  < 1 ||next->y > m)
			{
				delete next;
				continue;
			}
			if(!a[next->x-1][next->y-1])
			{
				delete next;
				continue;
			}
			next->x1=current->x;
			next->y1=current->y;
			next->g =current->g +1;
			next->h =abs(next->x - r)+abs(next->y - s);
			next->f =next->g + next->h ;
			next->next =0;
			if(next->x==r&&next->y==s)
			{
				open.Insert (next);
				close.Insert (current);
				return true;
			}
			result=open.process(next);
			if(result==3)
			{
				delete next;
				continue;
			}
			if(result==2)
			{
				open.Insert(next);
				continue;
			}
			if(result==1)
			{
				result=close.process(next);
				if(result==1)
				{
					open.Insert(next);
					continue;
				}
				if(result==2)
				{
					close.Insert(next);
					continue;
				}
				delete next;
			}
		}
		close.Insert (current);
	}
	return false;
}
void map::display(ofstream & out)
{
	Node *node=new Node,*next;
	node->x1=r;
	node->y1=s;
	next=open.GetNextNode(node);
	while(next&&(next->x!=p||next->y!=q))
	{
		out<<next->x<<" "<<next->y<<endl;
		node->x1=next->x1;
		node->y1=next->y1;
		next=open.GetNextNode(node); 
		if(!next)
			next=close.GetNextNode(node);
	}
	out<<p<<" "<<q;
}
map::~map ()
{
	long i=0;
	for(;i<m;i++)
		delete [] a[i];
	delete[] a;
}
void main()
{
	ifstream in("input.txt");
	ofstream out("output.txt");
	map m(in);
	m.init ();
	if(m.search())
		m.display(out);
	else 
		out<<"No Solution!"<<endl;
}