#include?
#include?
#include?“linkedQueue.h“

using?namespace?std;


const?int?size=20;

//全局變量：迷宮地圖
int?maze[size][size];
?????????????????//0-路1-墻2-起點3-終點


//四個方向：上下左右可走，若要調八方向亦可

//A*算法，找最短路徑


struct?markDot{
	int?rowcol;//行列
	int?distance;//距離
	markDot（）{
	}
	markDot（int?xint?yint?dis）{
		row=x;col=y;distance=dis;
	}
};


bool?FindPath（）{
	int?ij;
	int?sxsyexey;//起訖點坐標
	int?mark[size][size];

	//找起訖點
	for（i=0;i		for（j=0;j			if（maze[i][j]==2）{
				sx=i;
				sy=j;
			}else?if（maze[i][j]==3）{
				ex=i;
				ey=j;
			}
			mark[i][j]=-1;//未標記
		}
	}
	

	/*
	VC++6.0編譯器居然不能提示模板在外部定義的函數fuck
	bool?EnQueue（const?T?&x）;
	bool?DeQueue（T?&x）;
	bool?getFront（T?&x）const;
	*/
	markDot?start（sxsy0）;
	markDot?end（exey0）;//this?0?is?temperary
	markDot?direction[4];//這個辦法做4個方向蠻巧的，我一下還沒想到
	//0-up1-down2-left3-right

	direction[0].row=-1;direction[0].col=0;
	direction[1].row=1;direction[1].col=0;
	direction[2].row=0;direction[2].col=-1;
	direction[3].row=0;direction[3].col=1;



	linkedQueue?Q;

	Q.EnQueue（start）;
	linkNode?*now;
	//now=Q.front;
	markDot?addendpoint;
	int?tempxtempy;
	bool?markfinish=false;

	while（1）
	{
		now=Q.front;
		for（i=0;i<4;i++）
		{
			tempx=Q.front->data.row+direction[i].row;
			tempy=Q.front->data.col+direction[i].col;
			if（tempx<0?||?tempx>=size?||?tempy<0?||?tempy>=size）{
				continue;
			}


			if（mark[tempx][tempy]==-1）{
				//尚未標記
				if（maze[tempx][tempy]==0）{
					//這是路可以走
					mark[tempx][tempy]=Q.front->data.distance+1;//標記為到起點距離
					add.row=tempx;add.col=tempy;add.distance=mark[tempx][tempy];
					Q.EnQueue（add）;
				}else?if（maze[tempx][tempy]==3）{
					//找到終點
					mark[tempx][tempy]=Q.front->data.distance+1;//標記為到起點距離
					add.row=tempx;add.col=tempy;add.distance=mark[tempx][tempy];
					Q.EnQueue（add）;
					endpoint=add;
					markfinish=true;
					//break;
				}else?if（maze[tempx][tempy]==1）{
					mark[tempx][tempy]=-2;//此路不通
				}else{
					//標記過的路
					continue;
				}
			}




		}
		//4個方向遍歷完
		
		Q.DeQueue（add）;//刪
		if（Q.IsEmpty（））{
			return?false;
		}
		if（markfinish）{
			break;
		}
		




	}

	int?pathlen=endpoint.distance;
	markDot?*path;
	path=new?markDot[pathlen+1];


	int?txty;
	tempx=ex;tempy=ey;
	path[pathlen].row=ex;?path[pathlen].col=ey;?path[pathlen].distance=pathlen;
	for（j=pathlen-1;j>=0;j--）{
		for（i=0;i<4;i++）{
			tx=tempx+direction[i].row;?ty=tempy+direction[i].col;
			if（tx<0?||?tx>=size?||?ty<0?||?ty>=size）{
				continue;
			}
			if（j==mark[tx][ty]）{
				path[j].row=tx;
				path[j].col=ty;
				path[j].distance=j;
				tempx=tx;tempy=ty;
				break;
			}
		}
	}

	//draw?the?map;
	int?l;
	bool?isroute=false;
	cout<	for（i=0;i		for（j=0;j

			isroute=false;
			for（l=0;l<=pathlen;l++）{
				if（i==path[l].row?&&?j==path[l].col）{
				

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件?????299101??2012-10-12?15:21??A星迷宮\Debug\maze.obj

?????文件??????82944??2012-10-12?15:21??A星迷宮\Debug\vc60.idb

?????文件?????110592??2012-10-12?15:21??A星迷宮\Debug\vc60.pdb

?????文件?????565303??2012-10-12?15:21??A星迷宮\Debug\迷宮.exe

?????文件?????810764??2012-10-12?15:21??A星迷宮\Debug\迷宮.ilk

?????文件????2129332??2012-10-11?21:36??A星迷宮\Debug\迷宮.pch

?????文件????1123328??2012-10-12?15:21??A星迷宮\Debug\迷宮.pdb

?????文件???????2113??2012-10-11?21:04??A星迷宮\linkedQueue.h

?????文件???????4055??2012-10-12?15:21??A星迷宮\maze.cpp

?????文件????????818??2012-10-11?21:33??A星迷宮\maze.txt

?????文件????????818??2012-10-11?21:33??A星迷宮\maze20展示最短路.txt

?????文件????????136??2012-10-11?21:12??A星迷宮\maze8.txt

?????文件???????4320??2012-10-10?19:35??A星迷宮\迷宮.dsp

?????文件????????533??2012-10-10?19:12??A星迷宮\迷宮.dsw

?????文件??????50176??2012-10-12?15:21??A星迷宮\迷宮.ncb

?????文件??????49664??2012-10-12?15:21??A星迷宮\迷宮.opt

?????文件???????1250??2012-10-12?15:21??A星迷宮\迷宮.plg

?????目錄??????????0??2012-10-12?15:21??A星迷宮\Debug

?????目錄??????????0??2012-10-12?15:21??A星迷宮

-----------?---------??----------?-----??----

??????????????5235247????????????????????19