骰子
dice.cpp/c/pas
1s/128M
【题目描述】
桌面上有两个特别的骰子。骰子的每一个面，都写了一个不同的数字。设第一个骰子上下左右前后分别为a1, a2, a3, a4, a5, a6，第二个骰子分别为b1, b2, b3, b4, b5, b6。保证每个数字在区间 [1, 6] 内，而且对于所有的i ≠ j都有ai ≠ aj, bi ≠ bj。特别地，每个骰子相对的两面数字之和都不会为7
一开始，两个骰子的摆放可能是不同的（即对应面的数字可能不同），所以Ddy想通过如下操作使两个骰子摆放变得相同
左转：以CG为轴向左转90°，使ACGE变成底部
右转：以DH为轴向右转90°，使BDHF变成底部
前转：以CD为轴向前转90°，使ABCD变成底部
后转：以GH为轴向后转90°，使EFHG变成底部
现在Ddy想知道达到目的的最小步数是多少。
【输入】
输入文件名：dice.in
多组数据，直到EOF
对于每组数据，两行，分别表示两个骰子的状态。
每行6个数分别a1, a2, …, a6和b1, b2, …, b6
【输出】
输出文件名：dice.out
对于每组数据输出一行，达到目的的最小步数。
无解则输出 -1
【输入样例】
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 5 6 4 3
1 2 3 4 5 6
1 4 2 5 3 6
【输出样例】
0
3
-1
题解：因为每个骰子只有六个面，可以将这六个面的状态表示为一个六位数。（当然也可以用七进制或者六进制）
然后广搜，每一步都有四个方向可以选择，又因为每一个骰子都只有24种状态，记忆化一下就可以了。
#include#include #include #include #include #include #include using namespace std;int ans,a[7],b[7],ok;int make(int a[]){ int cnt=0; for(int i=0;i<=5;i++)cnt=cnt*10+a[i]; return cnt;}int mmin[1000000];void bfs(){ memset(mmin,127/3,sizeof(mmin)); int r=make(a),s; queue mem;queue p; mem.push(r); p.push(0); mmin[r]=0; while(!mem.empty()) { int x=mem.front(),y=p.front();mem.pop();p.pop(); if(x==ok){ans=y;return;} s=x%100+((x/100)%10)*10000+((x/1000)%10)*100000+((x/10000)%10)*1000+(x/100000)*100; if(mmin[s]>y+1){mem.push(s);p.push(y+1);mmin[s]=y+1;} s=x%100+((x/100)%10)*100000+((x/1000)%10)*10000+((x/10000)%10)*100+(x/100000)/1000; if(mmin[s]>y+1){mem.push(s);p.push(y+1);mmin[s]=y+1;} s=(x/100)%100*100+(x%10)*100000+((x/10)%10)*10000+(x/10000)%10+(x/100000)*10; if(mmin[s]>y+1){mem.push(s);p.push(y+1);mmin[s]=y+1;} s=(x/100)%100*100+(x%10)*10000+((x/10)%10)*100000+((x/10000)%10)*10+x/100000; if(mmin[s]>y+1){mem.push(s);p.push(y+1);mmin[s]=y+1;} }}int main(){ freopen("dice.in","r",stdin); freopen("dice.out","w",stdout); int i,j; while(scanf("%d",&a[0])!=EOF) { for(i=1;i<=5;i++)scanf("%d",&a[i]); for(i=0;i<=5;i++)scanf("%d",&b[i]); ok=make(b); ans=2000000000; bfs(); if(ans!=2000000000)printf("%d\n",ans); else printf("-1\n"); } return 0;}