-
-
Save wanggang316/eba96e29c22446a70847 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <hash_map> | |
#include <iostream> | |
#include <list> | |
#include <vector> | |
#include <algorithm> | |
using namespace std; | |
using namespace stdext; | |
int R,C;//地图行列 | |
int srcr,srcc,destr,destc;//起点 终点 | |
int map[100][100];//0是障碍1是可行 | |
struct Node | |
{ | |
int f,g,h; | |
int r,c; | |
int parent; | |
}; | |
list<Node> nowList; | |
list<Node> laterList; | |
hash_map< int , Node > cacheList; | |
vector<Node> bestList; | |
int Hfun(int r,int c) | |
{ | |
return abs(destr-r)+abs(destc-c); | |
} | |
bool Reach(int r,int c) | |
{ | |
if (!map[r][c]||r<0||c<0||r>R||c>C) | |
return false; | |
return true; | |
} | |
int GetCost(int r,int c) | |
{ | |
return 1; | |
} | |
Node child; | |
bool check(Node value) | |
{ | |
if (value.r==child.r&&value.c==child.c) | |
{ | |
return true; | |
} | |
return false; | |
} | |
bool checkhash(pair<int,Node> value) | |
{ | |
if (value.second.r==child.r&&value.second.c==child.c) | |
{ | |
return true; | |
} | |
return false; | |
} | |
int HashKey(Node& node) | |
{ | |
return (node.r<<16|node.c); | |
} | |
void Generate(Node& node,int r,int c,list<Node>& curlist) | |
{ | |
child.r=r; | |
child.c=c; | |
child.g=GetCost(r,c)+node.g; | |
child.h=Hfun(r,c); | |
child.f=child.g+child.h; | |
child.parent=node.r<<16|node.c; | |
hash_map<int,Node>::iterator posPL=find_if(cacheList.begin(),cacheList.end(),checkhash); | |
if (posPL!=cacheList.end()) | |
{ | |
if (child.g>=posPL->second.g) | |
{ | |
return; | |
} | |
} | |
list<Node>::iterator posCL=find_if(curlist.begin(),curlist.end(),check); | |
if (posCL!=curlist.end()) | |
{ | |
curlist.erase(posCL); | |
} | |
curlist.push_front(child); | |
cacheList[HashKey(child)]=child; | |
} | |
void Kuozhan(Node& node,list<Node>& curlist) | |
{ | |
if (Reach(node.r-1,node.c))// 上 | |
{ | |
Generate(node,node.r-1,node.c,curlist); | |
} | |
if (Reach(node.r,node.c+1))//右 | |
{ | |
Generate(node,node.r,node.c+1,curlist); | |
} | |
if (Reach(node.r+1,node.c))// 下 | |
{ | |
Generate(node,node.r+1,node.c,curlist); | |
} | |
if (Reach(node.r,node.c-1))// 左 | |
{ | |
Generate(node,node.r,node.c-1,curlist); | |
} | |
} | |
void BestPath(Node &best) | |
{ | |
Node mudi=best; | |
if (!bestList.empty()) | |
{ | |
bestList.clear(); | |
} | |
for (;;) | |
{ | |
bestList.push_back(mudi); | |
if (mudi.parent==-1) | |
return; | |
mudi=cacheList[mudi.parent]; | |
} | |
} | |
void FindPath(int sr,int sc,int dr,int dc) | |
{ | |
Node start; | |
start.g=0; | |
start.h=Hfun(sr,sc); | |
start.f=start.g+start.h; | |
start.r=sr; | |
start.c=sc; | |
start.parent=-1; | |
nowList.push_front(start); | |
laterList.clear(); | |
cacheList[HashKey(start)]=start; | |
int flimit=Hfun(sr,sc); | |
bool found=false; | |
list<Node>* curlist=&nowList; | |
list<Node>* nextlist=&laterList; | |
while (!found&&(!laterList.empty()||!nowList.empty())) | |
{ | |
int fmin=0x7fffffff; | |
while (!curlist->empty()) | |
{ | |
Node node=curlist->front(); | |
curlist->pop_front(); | |
if (node.f>flimit) | |
{ | |
fmin=min(node.f,fmin); | |
nextlist->push_back(node); | |
continue; | |
} | |
if (node.r==dr&&node.c==dc) | |
{ | |
found=true; | |
BestPath(node); | |
break; | |
} | |
Kuozhan(node,*curlist); | |
} | |
flimit=fmin; | |
list<Node>* tmp=curlist; | |
curlist=nextlist; | |
nextlist=tmp; | |
} | |
if (found) | |
cout<<"找到路径\n"; | |
else | |
cout<<"没有出路\n"; | |
} | |
void ShowPath() | |
{ | |
int i,j; | |
for (i=bestList.size();i>0;i--) | |
{ | |
map[bestList.back().r][bestList.back().c]=8; | |
bestList.pop_back(); | |
} | |
for (i=0;i<R;i++) | |
{ | |
for (j=0;j<C;j++) | |
{ | |
cout<<map[i][j]<<" "; | |
} | |
cout<<endl; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//test | |
int main( int argc,char* argv[] ) | |
{ | |
freopen("in.txt","r",stdin); | |
int i,j; | |
cin>>R>>C; | |
for (i=0;i<R;i++) | |
{ | |
for (j=0;j<C;j++) | |
{ | |
cin>>map[i][j]; | |
if (map[i][j]==5) | |
{ | |
srcr=i,srcc=j; | |
map[i][j]=1; | |
} | |
if (map[i][j]==6) | |
{ | |
destr=i,destc=j; | |
map[i][j]=1; | |
} | |
} | |
} | |
FindPath(srcr,srcc,destr,destc); | |
freopen("out.txt","w",stdout); | |
cout<<bestList.front().f<<endl; | |
ShowPath(); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
10 10 | |
1 1 1 1 1 0 0 0 0 0 | |
1 5 0 0 1 1 1 1 1 0 | |
1 1 1 0 1 0 0 0 1 1 | |
0 0 1 0 1 1 1 0 1 1 | |
1 1 1 0 0 0 0 1 1 1 | |
1 1 0 0 1 1 1 1 1 1 | |
1 1 1 0 1 1 1 0 0 0 | |
0 0 1 0 0 0 6 0 1 1 | |
1 1 1 1 1 0 0 0 1 1 | |
1 1 1 1 1 1 1 1 1 1 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
17 | |
1 8 8 8 8 0 0 0 0 0 | |
1 8 0 0 8 8 8 8 8 0 | |
1 1 1 0 1 0 0 0 8 1 | |
0 0 1 0 1 1 1 0 8 1 | |
1 1 1 0 0 0 0 8 8 1 | |
1 1 0 0 1 1 8 8 1 1 | |
1 1 1 0 1 1 8 0 0 0 | |
0 0 1 0 0 0 8 0 1 1 | |
1 1 1 1 1 0 0 0 1 1 | |
1 1 1 1 1 1 1 1 1 1 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment