c++迷宫最短路径寻径算法

一个迷宫最短路径寻径算法，可显示迷宫，路径。可修改迷宫。

#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