算法(A*)
1:暴力求出有没有解(逆序对)
2:估价函数
对于一个状态st,我们可以把f(st)的值定义为目标位置(设为end)的曼哈顿距离之和。
就是求st->end的曼哈顿距离
3:A*
就是优先队列BFS+估价函数f()
代码(C++)
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,string>
int f(string s){//估价函数f()
int cnt=0;
for(int i=0;i<9;i++){
if(s[i]=='x'){
continue;
}
int k=s[i]-'1';
cnt=cnt+abs(i/3-k/3)+abs(i%3-k%3);
}
return cnt;
}
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
string bfs(string st){//A*
string End="12345678x";
unordered_map<string,int> dist;
priority_queue<PII,vector<PII >,greater<PII > > q;
unordered_map<string,pair<string,char> > la;
q.push({f(st),st});
dist[st]=0;
char my[]="UDLR";
while(q.size()){
auto k=q.top();
q.pop();
string s=k.second;
if(s==End){
break;
}
int x,y;
for(int i=0;i<9;i++){//找空格
if(s[i]=='x'){
x=i/3;
y=i%3;
break;
}
}
string r=s;
for(int i=0;i<4;i++){
int xx=x+dx[i],yy=y+dy[i];
if(xx<0||xx>=3||yy<0||yy>=3){
continue;
}
swap(s[xx*3+yy],s[x*3+y]);
if(!dist.count(s)||dist[s]>dist[r]+1){//剪枝
dist[s]=dist[r]+1;
q.push({f(s)+dist[s],s});
la[s]={r,my[i]};
}
s=r;
}
}
string ans="";
while(End!=st){
ans+=(la[End].second+32);
End=la[End].first;
}
reverse(ans.begin(),ans.end());//记得翻转
return ans;
}
int main(){
string st="",x="",c="";
while(cin>>c){//输入
st+=c;
if(c!="x"){
x+=c;
}
}
int ans=0;
for(int i=0;i<8;i++){//求逆序对
for(int j=i+1;j<8;j++){
if(x[i]>x[j]){
ans++;
}
}
}
if(ans%2==1){//有没有解
printf("unsolvable\n");
}else{
cout<<bfs(st)<<endl;
}
return 0;
}