#include
#include
#include
using?namespace?std;

struct?direction??//存儲可以擴展的方向的數(shù)據(jù)結(jié)構(gòu)
{
public:
	bool?uprightdownleft;
	bool?closed;???//用來記錄是否是closed集中
	direction（）{};
	direction（int?aint?bint?cint?d）
	{
		up=a;
		right=b;
		down=c;
		left=d;
		closed=0;
	}
	
};
class?point
{
public:
	int?xygvalue;
	point*?father;
	point（）{value=INT_MAX;};
	point（int?aint?b）
	{
		x=a;y=b;
		value=INT_MAX;
	};
	bool?operator?	{
		return?value	};
	void?f（point?a）;
};

void?point::f（point?a）????//計算f值，使用形參為了可以使終點可自由改變
{
	value=g+abs（a.x-x）+abs（a.y-y）;
}

void?main（）
{
	direction?rule[5][5];????????????????//為了便于理解就浪費點空間吧……
	queue?result;???//即closed集，也就是結(jié)果路徑。
	list?open;

	//規(guī)則集//////////////////////////////////////////////////////////////
	rule[1][1]=direction（1000）;
	rule[1][2]=direction（1010）;
	rule[1][3]=direction（0110）;
	rule[1][4]=direction（0100）;
	rule[2][1]=direction（1100）;
	rule[2][2]=direction（1110）;
	rule[2][3]=direction（1011）;
	rule[2][4]=direction（0111）;
	rule[3][1]=direction（1101）;
	rule[3][2]=direction（1011）;
	rule[3][3]=direction（1110）;
	rule[3][4]=direction（0011）;
	rule[4][1]=direction（1001）;
	rule[4][2]=direction（1010）;
	rule[4][3]=direction（1011）;
	rule[4][4]=direction（0010）;
	////////////////////////////////////////////////////////////////////////
	point?temp;
	direction?d_temp;
	point?s（11）;
	point?terminal（44）;
	s.g=0;
	s.father=NULL;
	s.f（terminal）;
	open.push_back（s）;
	while（!（open.empty（）|（temp.x==terminal.x&&temp.y==terminal.y）））
	{
		open.sort（）;
		temp=open.front（）;
		result.push（open.front（））;
		rule[open.front（）.x][open.front（）.y].closed=1;//表明此結(jié)點已加入closed集
		d_temp=rule[temp.x][temp.y];
		open.pop_front（）;
		if（d_temp.up）
		{
			point?t（temp.xtemp.y+1）;
			t.g=temp.g+1;
			t.f（terminal）;
			if（!rule[t.x][t.y].closed）??//判斷結(jié)點是否在closed集中
			{
				open.push_front（t）;				
			}
		}
		if（d_temp.right）
		{
			point?t（temp.x+1temp.y）;			
			t.g=temp.g+1;
			t.f（terminal）;
			if（!rule[t.x][t.y].closed）
			{
				open.push_front（t）;				
			}
		}
		if（d_temp.down）
		{
			point?t（temp.xtemp.y-1）;
			t.g=temp.g+1;
			t.f（terminal）;
			if（!rule[t.x][t.y].closed）
			{
				open.push_front（t）;			
			}
		}
		if（d_temp.left）
		{
			point?t（temp.x-1temp.y）;
			t.g=temp.g+1;
			t.f（terminal）;
			if（!rule[t.x][t.y].closed）
			{
				open.push_front（t）;				
			}
		}
	}
	if（open.empty（））??cout<<“沒有路徑！“<	else
	{
		cout<<“最短路徑：“<		while（!result.empty（））
		{
			cout<<“（“<“;
			result.pop（）;
		}
		cout<<“\b\b“<<“??“<	}
	getchar（）;
	getchar（）;
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件????????2977??2018-11-23?15:06??maze.cpp