求A*算法走迷宫的原程序
想找一个A*算法走迷宫的程序看看，不知那位有原程序借来读一读。谢谢！

[解决办法]
＃i nclude <iostream>
＃i nclude <set>
＃i nclude <algorithm>
＃i nclude <iterator>
＃i nclude <vector>
＃i nclude <ctime>
＃i nclude <windows.h>
using namespace std;
class node
{
public:
int title;
int h; //深度
int f; //代价
node*father;
node(int title=0,int h=0,int f=0,node*father=NULL):
title(title),h(h),f(f),father(father){};
friend bool operator <(const node&s,const node&st)
{
if(s.f <st.f)return true;
if(s.f==st.f)return true;
return false;
}
};
multiset <node> open;
vector <node> close;
int map_w, map_h;
unsigned int*map;
unsigned int*dis_map;
int startx,starty,endx,endy;
inline int title_num(int x,int y){return map_w*x+y;}
inline int title_y(int n){return n%map_w;}
inline int title_x(int n){return n/map_w;}
void maps()
{
int in1;
int in2;
cout < < "请输入随机地图的宽度: ";
cin> > in1;
map_w=in1+2;
cout < < "请输入随机地图的高度: ";
cin> > in2;
map_h=in2+2;
cout < <endl;
cout < < "请输入地图的入口坐标x[ " < <1 < < ", " < <in1 < < "] " < < ",y[ " < <1 < < ", " < <in2 < < "]\nx= ";
cin> > endy;
while(endy <1||endy> in1)
{
cin.clear();
while(cin.get()!= '\n ')continue;
cout < < "输入错误,请重新输入\nx= ";
cin> > endy;
}
cout < < "y= ";
cin> > endx;
while(endx <1||endx> in2)
{
cin.clear();
while(cin.get()!= '\n ')continue;
cout < < "输入错误,请重新输入\ny= ";
cin> > endx;
}
cout < <endl;
cout < < "请输入地图的出口坐标x[ " < <1 < < ", " < <in1 < < "] " < < ",y[ " < <1 < < ", " < <in2 < < "]\nx= ";
cin> > starty;
while(starty <1||starty> in1)
{
cin.clear();
while(cin.get()!= '\n ')continue;
cout < < "输入错误,请重新输入\nx= ";
cin> > starty;
}
cout < < "y= ";
cin> > startx;
while(startx <1||startx> in2)
{
cin.clear();
while(cin.get()!= '\n ')continue;
cout < < "输入错误,请重新输入\ny= ";
cin> > startx;
}
cout < <endl;
map=new unsigned int[map_w*map_h];
dis_map=new unsigned int[map_w*map_h*sizeof(dis_map)];
memset(dis_map,0xff,map_h*map_w*sizeof(*dis_map));
int i=0,j=0,direc=2;
int ran;
for(i=0;i <map_h;i++)
for(j=0;j <map_w;j++)
map[map_w*i+j]=1;
srand(time(0));
for(i=0;i <map_h;i++)
for(j=0;j <map_w;j++)
if(map[map_w*i+j]==1){
ran=(int)rand()%10;
if(ran <3)map[map_w*i+j]=0;
}
map[title_num(startx,starty)]=1;
map[title_num(endx,endy)]=1;
for(i=0;i <map_h;++i)
{
for(j=0;j <map_w;++j)
{
if(i==0||j==0)map[title_num(i,j)]=0;
if(i==map_h-1||j==map_w-1)map[title_num(i,j)]=0;
}
}
}
int testing(int x,int y)
{
return abs(endx-x)+abs(endy-y);
}
int trytest(int x,int y,node*priot)

{
int h;
if(0==map[title_num(x,y)])return 1;
h=priot-> h+1;
if(h> =dis_map[title_num(x,y)])return 1;
dis_map[title_num(x,y)]=h;
open.insert(node(title_num(x,y),h,h+testing(x,y),priot));
return 0;
}
int*lookup()
{
node*root=new node();
int i;
int*paths;
root-> title=title_num(startx,starty);
open.insert(*root);
for(;;)
{
int x,y,child;
root=new node();
if(open.empty())break;
root-> title=open.begin()-> title;
root-> h=open.begin()-> h;
root-> father=open.begin()-> father;
open.erase(open.begin());
close.push_back(*root);
x=title_x(root-> title );
y=title_y(root-> title );
if(x==endx&&y==endy)break;
child=1;
child&=trytest(x,y-1,root);
child&=trytest(x,y+1,root);
child&=trytest(x-1,y,root);
child&=trytest(x+1,y,root);
if(child!=0)close.erase(close.end()-1);
}
if(open.empty())return NULL;
paths=new int[root-> h+2];
for(i=0;root;++i)
{
paths[i]=root-> title;
root=root-> father;
}
paths[i]=-1;
return paths;
}
void showmap()
{
int i,j;
for(i=0;i <map_h;++i)
{
for(j=0;j <map_w;++j)
{
if(i==0||j==0||i==map_h-1||j==map_w-1)
{
cout < < "■ ";
continue;
}
if(i==startx&&j==starty)
{
cout < < "Ｅ ";
continue;
}
if(i==endx&&j==endy)
{
cout < < "Ｓ ";
continue;
}
if(map[map_w*i+j]== '* ')
{
cout < < "＊ ";
continue;
}
if(map[map_w*i+j])cout < < "□ ";
else cout < < "■ ";

}
cout < <endl;
}
Sleep(800);
}
void showpath(int *paths)
{
for(int i=0; paths[i]> 0; ++i)
{
map[paths[i]]= '* ';
system( "cls ");
showmap();
}
}
int main()
{
while(1)
{
char anyt;
int*paths;
maps();
system( "CLS ");
showmap();
system( "cls ");
showmap();
system( "PAUSE ");
paths=lookup();
if(paths==NULL)cout < < "没路 " < <endl;
if(paths)showpath(paths);
if(paths)delete [] paths;
if(dis_map)delete [] dis_map;
if(map)delete [] map;
cout < < "再来一次(Y/N)? ";
cin> > anyt;
if(anyt== 'n '||anyt== 'N ')break;
}
system( "PAUSE ");
return 0;
}


[解决办法]
#include <iostream>
#include <cassert>
#include <ctime>
#include <windows.h>
using namespace std;
const int MAXINT = 88888; //随便取个数,大于地图上任意两点间的距离
int map_w, map_h; //地图的宽,高
inline int title_num(int x,int y){return map_w*x+y;} //由坐标转化为地图块号
inline int title_y(int n){return n%map_w;}//由块号转化为x,y坐标
inline int title_x(int n){return n/map_w;}
class treenode
{
public:
int h; //节点所在的高度，表示从起始点到该节点所有的步数
int title; //该节点的位置(块数)
treenode*father; //该节点的上一步
};

class linknode //链表结点
{
public:

treenode*node;
int f;
linknode*next;
};

linknode*open_queue; // 保存没有处理的行走方法的节点
linknode*close_queue; // 保存已经处理过的节点 (搜索完后释放)

unsigned int*map; //地图数据
unsigned int*dis_map; //保存搜索路径时,中间目标地最优解

int startx,starty,endx,endy; //地点,终点坐标

void initial() // 初始化队列
{
open_queue=new linknode();
open_queue-> node=NULL;
open_queue-> f=-1;
open_queue-> next=new linknode();
open_queue-> next-> node=NULL;
open_queue-> next-> next=NULL;
open_queue-> next-> f=MAXINT;
close_queue=new linknode();
close_queue-> f=-1;
close_queue-> next=NULL;
close_queue-> node=NULL;
}

void entrance(treenode*node, int m) // 待处理节点入队列, 依*对目的地估价距离插入排序
{
linknode*p,*priot;
p=open_queue;

while(m> p-> f)
{
priot=p;
p=p-> next;
assert(p);
}

linknode*q=new linknode();
q-> next=p;
priot-> next=q;
q-> node=node;
q-> f=m;
}

treenode*receive() // 将离目的地估计最近的方案出队列
{
linknode*p=open_queue-> next;
open_queue-> next=open_queue-> next-> next;
p-> next=close_queue-> next;
close_queue-> next=p;
return p-> node;
}

void pop_stack() // 释放栈顶节点
{
linknode*p=close_queue-> next;
close_queue-> next=close_queue-> next-> next;
assert(p);
delete p-> node;
delete p;
}

void empty() // 释放申请过的所有节点
{
linknode*p;

while(open_queue)
{
p=open_queue;
delete p-> node;
open_queue=open_queue-> next;
delete p;
}

while(close_queue)
{
p=close_queue;
delete p-> node;
close_queue=close_queue-> next;
delete p;
}
}

int testing(int x,int y) // 估价函数,估价 x,y 到目的地的距离,估计值必须保证比实际值小
{
return abs(endx-x)+abs(endy-y);
}

int trytest(int x,int y,treenode* priot) //尝试下一步移动到 x,y 可行否
{
treenode*p;
int h;
if(0==map[title_num(x,y)])return 1;
h=priot-> h+1;
if(h> =dis_map[title_num(x,y)])return 1; // 如果曾经有更好的方案移动到 (x,y) 失败
dis_map[title_num(x,y)]=h; // 记录这次到 (x,y) 的距离为历史最佳距离
// 将这步方案记入待处理队列

p=new treenode();
p-> father=priot;
p-> h=priot-> h+1;
p-> title=title_num(x,y);
entrance(p, p-> h+testing(x,y));
return 0;
}

int* lookup() // 路径寻找主函数
{
treenode*root=root=new treenode();
int i;
int*paths;

memset(dis_map,0xff,map_h*map_w*sizeof(*dis_map));//填充dis_map为0XFF，表示各点未曾经过
initial();

root-> title=title_num(startx,starty);
root-> h=0;
root-> father=NULL;
entrance(root,testing(startx,starty));

for(;;)
{
int x,y,child;
root=receive();
if(NULL==root)return NULL;

x=title_x(root-> title );
y=title_y(root-> title );

if(x==endx&&y==endy)break;;// 达到目的地成功返回

child=1;
child&=trytest(x,y-1,root); //尝试4个方向
child&=trytest(x,y+1,root);
child&=trytest(x-1,y,root);
child&=trytest(x+1,y,root);
if(child!=0)pop_stack();// 如果四个方向均不能移动,释放这个死节点
}
paths=new int[root-> h+2];
assert(paths);
for(i=0;root;++i)
{
paths[i]=root-> title;
root=root-> father;
}

paths[i]=-1;

empty();
return paths;
}
void showmap();//显示地图
void showpath(int *paths) // 回溯树，将求出的最佳路径保存在 path[] 中
{
int i;

if(paths==NULL)
return;

for(i=0; paths[i]> 0; ++i)
{
cout < < "( "
< < title_x(paths[i])
< < ", "
< < title_y(paths[i])
< < ") " < < " ";
}

cout < <endl;
for(i=0; paths[i]> 0; ++i)
{
assert(paths[i]);
map[paths[i]]= '* ';
system( "cls ");
showmap();
}
}

void setmap() //申请dis_map的大小
{
dis_map=new unsigned int[map_w*map_h*sizeof(dis_map)];
assert(dis_map);
}

void showmap() //显示地图
{
int i,j;
assert(map);
for(i=0;i <map_h;++i)
{
for(j=0;j <map_w;++j)
{
if(i==0||j==0||i==map_h-1||j==map_w-1)
{
cout < < "■ ";
continue;
}
if(i==startx&&j==starty)
{
cout < < "Ｅ ";
continue;
}
if(i==endx&&j==endy)
{
cout < < "Ｓ ";
continue;
}
if(map[map_w*i+j]== '* ')
{
cout < < "＊ ";
continue;
}
if(map[map_w*i+j])cout < < "□ ";
else cout < < "■ ";

}
cout < <endl;
}
Sleep(800);
}
void maps() //生成地图
{
int in1;
int in2;
cout < < "请输入随机地图的宽度: ";
cin> > in1;
map_w=in1+2;
cout < < "请输入随机地图的高度: ";
cin> > in2;
map_h=in2+2;
cout < <endl;
cout < < "请输入地图的入口坐标x[ " < <1 < < ", " < <in1 < < "] " < < ",y[ " < <1 < < ", " < <in2 < < "]\nx= ";
cin> > endy;
while(endy <1||endy> in1)
{
cin.clear();
while(cin.get()!= '\n ')continue;
cout < < "输入错误,请重新输入\nx= ";
cin> > endy;
}
cout < < "y= ";
cin> > endx;
while(endx <1||endx> in2)
{
cin.clear();
while(cin.get()!= '\n ')continue;
cout < < "输入错误,请重新输入\ny= ";
cin> > endx;
}
cout < <endl;
cout < < "请输入地图的出口坐标x[ " < <1 < < ", " < <in1 < < "] " < < ",y[ " < <1 < < ", " < <in2 < < "]\nx= ";
cin> > starty;
while(starty <1||starty> in1)
{
cin.clear();
while(cin.get()!= '\n ')continue;
cout < < "输入错误,请重新输入\nx= ";
cin> > starty;
}
cout < < "y= ";
cin> > startx;
while(startx <1||startx> in2)
{
cin.clear();
while(cin.get()!= '\n ')continue;
cout < < "输入错误,请重新输入\ny= ";
cin> > startx;
}
cout < <endl;
map=new unsigned int[(map_w+1)*map_h];
int i=0,j=0,direc=2;
int ran;
for(i=0;i <map_h;i++)
for(j=0;j <map_w;j++)
map[map_w*i+j]=1; //初始化地图
srand(time(0));
i=j=0;
while(1){
if(i> =map_h-1&&j> =map_w-1)break;
ran=(int)rand()%4;
if(ran <1){
if(direc!=1&&i <map_h-1){

i++;
direc=3;
}
}
else if(ran <2){
if(direc!=2&&j> 0){
j--;
direc=0;
}
}
else if(ran <3){
if(direc!=3&&i> 0){
i--;
direc=1;
}
}
else {
if(direc!=0&&j <map_w-1){
j++;
direc=2;
}
}
}
for(i=0;i <map_h;i++)
for(j=0;j <map_w;j++)
if(map[map_w*i+j]==1){
ran=(int)rand()%10;
if(ran <3)map[map_w*i+j]=0;
}
map[title_num(startx,starty)]=1;
map[title_num(endx,endy)]=1;
for(i=0 <span s