POJ - 1077 Eight（A?算法）

POJ - 1077 Eight（A?算法）

#include<iostream>
#include<algorithm>
#include<map>
#include<queue>#define x first
#define y secondusing namespace std;typedef pair<int,string> PIS;
typedef pair<char,string> PCS;int f(string state)
{
    int res=0;for(int i=0;i<9;i++)if (state[i]!='x'){
    int v=state[i]-'1';res+=abs(v/3-i/3)+abs(v%3-i%3);}return res;
}string bfs(string start)
{
    int dx[4] = {
    -1, 0, 1, 0}, dy[4] = {
    0, 1, 0, -1};char op[5] = "urdl";string end="12345678x";map<string,int> dist;map<string,pair<char,string> >pre;priority_queue<PIS,vector<PIS>,greater<PIS> >heap;heap.push((PIS){
    f(start), start});dist[start]=0;while(heap.size()){
    PIS t=heap.top();heap.pop();string state=t.y;if(state==end) break;int x,y;for(int i=0;i<9;i++)if(state[i]=='x'){
    x=i/3,y=i%3;break;}string source=state;for (int i=0;i<4;i++){
    int a=x+dx[i],b=y+dy[i];if(a<0||a>=3||b<0||b>=3) continue;state=source;swap(state[x*3+y],state[a*3+b]);if (dist.count(state)==0||dist[state]>dist[source]+1){
    dist[state]=dist[source]+1;pre[state] =(PCS){
    op[i],source};heap.push((PIS){
    dist[state]+f(state),state});}}}string res;while(end!=start){
    res+=pre[end].x;end=pre[end].y;}reverse(res.begin(),res.end());return res;
}int main()
{
    string start,seq,c;while(cin>>c){
    start+=c;if(c!="x") seq+=c;}int cnt=0;for(int i=0;i<8;i++)for(int j=i+1;j<8;j++)if(seq[i]>seq[j])cnt++;if(cnt%2) cout<<"unsolvable"<<endl;else cout<<bfs(start)<<endl;return 0;
}