HDU - 1043 Eight（康托展开）

传送门

分析：

将每一种状态映射到一个数字，类似于 map a[370000]
初始：12345678#，将#看成9，初始状态对应0，总共是A9的全排列，大概是36w多，一维数组还是可以接受的

#include using namespace std;struct Node
{int cant,num;int p[11];
};
struct Node2
{char way;int fath;
}e[370005];
int fac[11];
void cntfac()//算阶乘
{fac[0]=1;for(int i=1;i<=8;i++) fac[i]=fac[i-1]*i;
}int cantor(int p[])//康托展开
{int ans=0;for(int i=1;i<=9;i++){int k=0;for(int j=i+1;j<=9;j++){if(p[i] > p[j]) k++;}ans+=k*fac[9-i];}return ans;
}
int dy[5]={1,-1,0,0};
int dx[5]={0,0,1,-1};
void bfs()
{queue <Node> q;Node u;for(int i=1;i<=9;i++) u.p[i]=i;// 最后的结果，由最后的结果向前推回去u.num=9; u.cant=0;// 初始为0e[u.cant].fath=0;// 初始父亲也为0q.push(u);while(!q.empty()){u=q.front(); q.pop();for(int i=0;i<4;i++){int x=(u.num-1)/3+1+dx[i], y=(u.num-1)%3+1+dy[i];if(x && x<=3 && y && y<=3){Node v = u;v.num = (x-1)*3+y;swap(v.p[u.num],v.p[v.num]); // 移动一步v.cant = cantor(v.p); // v的康托值if(e[v.cant].fath==-1) // 相当于vis标记{e[v.cant].fath=u.cant; // 更新父亲if(i==0) e[v.cant].way='l'; // 注意这里由于是倒推，所以从后往前是r，则从前向后便为l，ud亦然if(i==1) e[v.cant].way='r';if(i==2) e[v.cant].way='u';if(i==3) e[v.cant].way='d';q.push(v);}}}}
}int main()
{for(int i=1;i<=370000;i++) e[i].fath=-1; // 初始化，不能为0，0是康托的一种状态，已被占用cntfac();bfs();char s[11];while(cin>>s[0]){for(int i=1;i<=8;i++) cin>>s[i];int a[9];for(int i=0;i<9;i++){if(s[i]=='x') a[i+1]=9;else a[i+1]=s[i]-'0';}int u=cantor(a);if(e[u].fath==-1){printf("unsolvable\n");continue;}while(u){cout<<e[u].way;u=e[u].fath;}cout<<endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！