本文共 2725 字，大约阅读时间需要 9 分钟。
搜索题，
每个状态能扩展出12种状态，最多进行5次旋转12^5
要用到iddfs，或者我看到网上其他人用的ida*
我也是参考了别人的代码，而且这个题vj上有点问题，我看数据看了半天，愣是没看明白第二个数据咋回事，后来才知道是vj显示的有问题
#include #include #include #include #include #include #include #include using namespace std;#define ll long long#define se second#define fi first#define oo 0x3fffffff/* 40 1 2 3 5 1 2 3// 4 5 6// 7 8 9//10 11 12 13 14 15 16 17 18 19 20 21//22 23 24 25 26 27 28 29 30 31 32 33//34 35 36 37 38 39 40 41 42 43 44 45// 46 47 48// 49 50 51// 52 53 54*/int cent[7] = { 23, 26, 29, 32, 5, 50};int face[7][10] = {{ 10,11,12,22,23,24,34,35,36},{ 13,14,15,25,26,27,37,38,39},{ 16,17,18,28,29,30,40,41,42},{ 19,20,21,31,32,33,43,44,45},{ 1,2,3,4,5,6,7,8,9},{ 46,47,48,49,50,51,52,53,54}};int change[12][23] = { { 1,4,7,13,25,37,46,49,52,21,33,45,10,11,12,24,36,35,34,22}, { 45,33,21,1,4,7,13,25,37,52,49,46,34,22,10,11,12,24,36,35}, { 7,8,9,16,28,40,48,47,46,36,24,12,13,14,15,27,39,38,37,25}, { 36,24,12,7,8,9,16,28,40,48,47,46,37,25,13,14,15,27,39,38}, { 9,6,3,19,31,43,54,51,48,39,27,15,16,17,18,30,42,41,40,28}, { 39,27,15,9,6,3,19,31,43,54,51,48,40,28,16,17,18,30,42,41}, { 42,30,18,3,2,1,10,22,34,52,53,54,19,20,21,33,45,44,43,31}, { 52,53,54,42,30,18,3,2,1,10,22,34,43,31,19,20,21,33,45,44}, { 15,14,13,12,11,10,21,20,19,18,17,16,1,2,3,6,9,8,7,4}, { 18,17,16,15,14,13,12,11,10,21,20,19,7,4,1,2,3,6,9,8}, { 37,38,39,40,41,42,43,44,45,34,35,36,46,47,48,51,54,53,52,49}, { 34,35,36,37,38,39,40,41,42,43,44,45,52,49,46,47,48,51,54,53}};char s[60];int a[10],b[10];int maxdepth;int l = 0;bool dfs(int dep);bool judge();int main(){ int t; scanf("%d",&t); while(t--) { l = 0; for(int i = 1;i <= 54; ++i) scanf(" %c",s+i); //for(int i = 1; i <= 54; ++i) // printf("%c",s[i]); for(maxdepth = 1;maxdepth <= 5; ++maxdepth) { if(dfs(0)) { if(l == 0) { printf("0\n");break; } printf("%d\n", l); for(int i = 0; i < l-1; ++i) { printf("%d %d ",a[i],b[i]); } printf("%d %d\n",a[l-1],b[l-1]); break; } } if(maxdepth == 6) printf("-1\n"); }}bool judge(){ for(int i = 0; i < 6; ++i) { for(int j = 0; j < 9; ++j) { if(s[face[i][j]] != s[cent[i]]) return false; } } return true;}bool dfs(int dep){ if(judge()) { l = dep; return true; } if(dep >= maxdepth) return false; char tmp[60]; memcpy(tmp,s,sizeof s); for(int i = 0; i < 12; ++i) { for(int j = 0; j < 20; ++j) { s[change[i][j]] = tmp[change[i^1][j]]; } /*if(dep == 0) { for(int i = 0; i < 6; ++i) for(int j = 0; j < 9; ++j) printf("%c",s[face[i][j]]); cout << " " << (i&1) << endl; cout << endl; }*/ a[dep] = i/2; b[dep] = i&1?-1:1; if(dfs(dep+1)) return true; memcpy(s,tmp,sizeof tmp); } return false;}
转载于:https://www.cnblogs.com/mltang/p/9762697.html