＃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
=root->title;
root=root->father;
}
paths=-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>0; ++i)
{
map[paths]='*';
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;
}
