#include
#include
#include
#include
#include?
#include
#include
#include
#include
#include?
#include

using?namespace?std;


typedef??struct?point{
	int?xy;
	int?fxgxhx;
	int?pxpy;
	bool?visited;
	struct?point?*next;
}*Point;

Point?Qpath;
int?entry_xentry_y;
int?exit_xexit_y;
int?rowcol;
int?maze[200][200];
int?Visited[200][200];
char?Path[200][200];
char?PATH[200];


int?Manhattan_dis（int?x?int?y）{
	return?abs（x?-?exit_x）?+?abs（y?-?exit_y）;
}


bool?QueueEmpty（Point?Q）{
	if（Q->next?==?NULL）?return?true;
	return?false;
}

void?EnQueue（Point?QPoint?q）{
	if（QueueEmpty（Q））{
		Q->next=q;
		return;
	}
	Point?p?=?Q->next;
	while（p->next!=NULL&&p->fx?fx）
		p?=?p->next;
	q->next?=?p->next;
	p->next?=?q;
	Visited[q->x][q->y]?=?1;
}

void?EnQueue_1（Point?QPoint?q）{
	if（QueueEmpty（Q））{
		Q->next=q;
		return;
	}
	Point?p?=?Q->next;
	while（p->next!=NULL&&p->fx?>?q->fx）
		p?=?p->next;
	q->next?=?p->next;
	p->next?=?q;
}

void?DeQueue（Point?QPoint?&p）{
	p?=?Q->next;
	Q->next=p->next;
}
			
void?Build_Maze（char?*filename）{
	ifstream?in;
	string?input;
	in.open（filename）;
	int?depth?=?0;
	int?flag?=?0?m?=?-1;
	while（getline（ininput））{
		int?length?=?input.length（）;
		int?i?=?0j?=?0;
		while（i?			if（input[i]?==?‘0‘）?maze[depth][j++]?=?0;
			else?if（input[i]?==?‘1‘）?maze[depth][j++]?=?1;
			i++;
		}
		depth++;
		if（m?		if（m?>?j）?flag?=?1;
	}
	col?=?depth?-?flag;?row?=?m;
}

void?Get_entry_and_exit（）{
	int?i;
	for（i?=?0;?i?		if（maze[0][i]?==?0）{
			entry_x?=?0;
			entry_y?=?i;
		}
		if（maze[col?-?1][i]?==?0）{
			exit_x?=?col?-?1;
			exit_y?=?i;
		}
	}
	for（int?j?=?0;?j?		if（maze[j][0]?==?0）{
			entry_x?=?j;
			entry_y?=?0;
		}
		if（maze[j][row?-?1]?==?0）{
			exit_x?=?j;
			exit_y?=?row?-?1;
		}?
	}?
}

Point?Generate_Point（int?x?int?y?int?gx?int?px?int?py）{
	Point?Entry?=?（Point）malloc（sizeof（point））;
	Entry->x?=?x;Entry->y?=?y;
	Entry->px?=?px;?Entry->py?=?py;
	Entry->gx?=?gx;?Entry->hx?=?Manhattan_dis（entry_xentry_y）;Entry->fx?=?Entry->gx?+?Entry->hx;
	Entry->next?=?NULL;
	return?Entry;
}
	
void?A_STAR（）{
	Q?=?Generate_Point（-1-10-1-1）;
	path?=?Generate_Point（-1-10-1-1）;
	Point?Entry?=?Generate_Point（entry_xentry_y0-1-1）;
	EnQueue（QEntry）;
	Point?p?=?（Point）malloc（sizeof（point））;
	while（!QueueEmpty（Q））{
		DeQueue（Qp）;
		EnQueue_1（pathp）;
		if（p->x?==?exit_x?&&?p->y?==?exit_y）{
			return;
		}
		int?x?=?p->x?y?=?p->y?gx?=?p->gx;
		if（?x?+?1?			Point?q?=?Generate_Point（x?+?1?y?gx?+?1?x?y）;
			EnQueue（Qq）;
		}
		if（?y?+?1?			Point?q?=?Generate_Point（x?y?+?1?gx?+?1?x?y）;
			EnQueue（Qq）;
		}
		if（?x?-?1?>=?0?&&?maze[x-1][

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件????????4673??2019-05-12?16:41??ai_1.1.cpp
?????文件????????5707??2019-05-12?16:40??ai_1.2.cpp
?????文件???????12251??2019-06-21?17:02??ai_2.cpp
?????文件?????????916??2019-05-12?00:44??input1.txt
?????文件????????3647??2019-05-12?14:09??input2.txt
?????文件?????????122??2019-06-21?17:04??output.txt
?????文件??????????55??2019-05-12?16:31??output_astar_1.txt
?????文件?????????133??2019-05-12?16:36??output_astar_2.txt
?????文件??????????56??2019-05-12?20:16??output_ida_1.txt
?????文件?????????133??2019-05-12?16:36??output_ida_2.txt