A*
dijkstra是一种特殊的A*算法，估价距离必须小于等于实际距离 八数码问题
- 把八数码写成序列，左右移动不会改变逆序对，上下移动则会变化两次或不变
- 因此有解的条件为初始和最终状态奇偶性相同(洛谷的版本保证有解，因此不需要判断)
- 估价函数为每个数字到最终位置的曼哈顿距离之和+所需的步数
cpp
string start,ed="123804765";
typedef pair<int,string> PIS;
unordered_map<string,int> dis;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int f(string s){
int ans=0;
for(int i=0;i<9;i++){
if(s[i]=='0')continue;
int x=i/3,y=i%3;
for(int j=0;j<9;j++){
if(ed[j]==s[i]){
int xx=j/3,yy=j%3;
ans+=abs(xx-x)+abs(yy-y);
break;
}
}
}
return ans;
}
void bfs(){
priority_queue<PIS,vector<PIS>,greater<PIS>> q;
q.push({f(start),start});
dis[start]=0;
while(!q.empty()){
auto [val,u]=q.top();
q.pop();
if(u==ed)break;
int x,y;
for(int i=0;i<9;i++){
if(u[i]=='0'){
x=i/3,y=i%3;
break;
}
}
for(int i=0;i<4;i++){
int tx=x+dx[i],ty=y+dy[i];
if(tx>=0&&tx<3&&ty>=0&&ty<3){
string v=u;
swap(v[tx*3+ty],v[x*3+y]);
if(dis.count(v)==0||dis[v]>dis[u]+1){
dis[v]=dis[u]+1;
q.push({dis[v]+f(v),v});
}
}
}
}
}
void solve(){
cin>>start;
bfs();
cout<<dis[ed]<<"\n";
}