题目传送门：

 

思路：

　　这道题如果要从现在的情况通过A B C三种操作而得到目标数阵很难找到一种有效的方法。但是考虑总共的操作不会多于10步，可以考虑将10步可能产生的所有数阵记录下来，然后在寻找目标数阵，将得到这个数阵的操作过程输出即可。由于每次有3种操作，所以我用了类似于决策树的结构，如果下一步进入左子树代表A操作，中子树代表B，右子树代表C，在每一个树的节点用一个string存入得到当前节点的全部操作,然后递归的建立这棵树。

　　在寻找某个目标数阵的时候，用一个全局变量哨兵值进行判断是否已经找到，也是用递归的方法进行寻找，由于结果不能超过n步，所以设计函数的时候把n当做参数一同传进。

 

 

代码：

1 #include
     
        2 using namespace std;  3   4   5 struct Node{  6     int numbers[8];  7     string operations;  8     Node *left,*middle,*right;  9     //constructor 10     Node(int *n,string o = "",Node *l = NULL,Node *m = NULL,Node *r = NULL){ 11         left = l; 12         middle = m; 13         right = r; 14         operations = o; 15         for(int i = 0;i < 8;i++){ 16             numbers[i] = n[i]; 17         } 18     } 19 }; 20  21 void swap(int &a,int &b); 22 int *A_change(int *numbers); 23 int *B_change(int *numbers); 24 int *C_change(int *numbers); 25 bool judge(int *a,int *b); 26 void recursive_build_tree(Node *&subroot,int level,int *n,string op); 27 void recursive_find_and_print(Node *subroot,int level,int *target); 28  29 bool finded; 30  31 int main(){ 32     int n; 33     Node *root = NULL; 34     int numbers[8] = {
   1,2,3,4,8,7,6,5}; 35     recursive_build_tree(root,11,numbers,""); 36     while(cin >> n && n!= -1){ 37         int target[8]; 38         for(int i = 0;i < 8;i++){ 39             cin >> target[i]; 40         } 41         finded = false; 42         recursive_find_and_print(root,n,target); 43         if(!finded) 44             cout << -1 << endl; 45     } 46     return 0; 47 } 48 bool judge(int *a,int *b){ 49     //Post:return true if the two arrays have the same elements. 50     for(int i = 0;i < 8;i++){ 51         if(a[i] != b[i]) 52             return false; 53     } 54     return true; 55 } 56 void swap(int &a,int &b){ 57     int temp = a; 58     a = b; 59     b = temp; 60 } 61 int *A_change(int *numbers){ 62     for(int i = 0;i < 4;i++){ 63         swap(numbers[i],numbers[i + 4]); 64     } 65     return numbers; 66 } 67 int *B_change(int *numbers){ 68     int temp = numbers[3]; 69     for(int i = 3;i >= 1;i--) 70         numbers[i] = numbers[i - 1]; 71     numbers[0] = temp; 72     temp = numbers[7]; 73     for(int i = 7;i >= 5;i--) 74         numbers[i] = numbers[i - 1]; 75     numbers[4] = temp; 76     return numbers; 77 } 78 int *C_change(int *numbers){ 79     int temp = numbers[1]; 80     numbers[1] = numbers[5]; 81     numbers[5] = numbers[6]; 82     numbers[6] = numbers[2]; 83     numbers[2] = temp; 84     return numbers; 85 } 86 void recursive_build_tree(Node *&subroot,int level,int *n,string op){ 87     subroot = new Node(n,op); 88     if(level > 1){ 89         int n1[8],n2[8]; 90         for(int i = 0;i < 8;i++){ 91             n1[i] = n2[i] = n[i]; 92         } 93         recursive_build_tree(subroot->left,level - 1,A_change(n),op + "A"); 94         recursive_build_tree(subroot->middle,level - 1,B_change(n1),op + "B"); 95         recursive_build_tree(subroot->right,level - 1,C_change(n2),op + "C"); 96     } 97 } 98 void recursive_find_and_print(Node *subroot,int level,int *target){ 99     if(!finded){100         if(judge(subroot->numbers,target)){101             finded = true;102             cout << subroot->operations.length() << ' ' << subroot->operations << endl;103             return;104         }105         if(level >= 1){106             recursive_find_and_print(subroot->left,level - 1,target);107             recursive_find_and_print(subroot->middle,level - 1,target);108             recursive_find_and_print(subroot->right,level - 1,target);109         }110     }111 }