#include <iostream>#include <vector>#include <stack>#include <cstring>using namespace std;/*  *给定一个状态，在指定步骤内通过A、B、C操作到达目标态  *定义一个状态数组，头指针fp指向当前的父节点操作，rp  *指向子节点操作。判断是否加入子节点序列时：判重！ *此处使用哈希来判重，即用一个bool数组来记录某个值是否已经 *已经在队列中，即已经访问过了，该bool数组的下标为由 *康托展开计算得到，其为一个哈希函数，若出现重复状态则跳过，对每个父节点都有三个  *操作，符合条件的进入队列，rp依次后移，fp完成三个操作  *后也fp++    *利用康托展开记录每种状态出现的位置，即通过康托展开  *后可以知道该状态是第几大的数即可马上定位到该位置，  *位置访问信息用一个数组记录即可。  *康托展开方法（一种特殊的哈希函数）   *例如一个123的序列，求321在其全排列中排第几大的数。  *首先3, 那么第二位数可以是1或2，则有2*2! = 4个比他小的数，  *然后看第二位2，比他小的数有1，则有1*1! = 1 所以有4+1=5个  *321小的数，也就是说它是第6大的数。   */ //定义一个魔方的结构体 typedef struct mf {	int up; //魔方上行数字 	int down; //魔方下行数字 	char op; //由该操作得到该魔方 	int pre; //记录该魔方的前一个魔方，即在三叉树中的父节点在队列中的下标，用于回溯输出最短到达该目的魔方所经过的变换，此设计很关键 } MF;bool isvisited[50000]; //由于由mf.up*10000+mf.down得到的为8位数，所以根据康托展开计算公式可以知道该8位数的全排列的数目为 8！个 //康托判重(一种特殊的哈希函数)int fact[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320}; //8!的阶乘表 ，用于计算下面的康托展开值 //返回值为数字n在以下标0开始的从小到大记录数字n的各位的全排列对应的数字的数组中的下标//即数字n在该全排列中为第几大的 //康托展开函数：index =a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[2]*1!+a[1]*0![1] // 其中，a为整数，并且0<=a[i]<i(1<=i<=n)int cantor(long number) {      int a[8];    int n = 0;    int index = 0;     for (int i = 7; i >= 0; i--) {//a[7,6,5...0]为个位，十位，百位...     	a[i] = number % 10;    	number /= 10;    }    for (int i = 0; i <= 7; i++) {    	//计算比a[i]小的数字     	for (int j = i + 1; j <= 7; j++) {    		if (a[i] > a[j])    			n++;    	}    	index += n * fact[7-i];    	n = 0;    }     return index;}  //比较待插入的魔方是否已经在队列中存在 bool cmp(vector<MF> &mfs, MF mf, char op, int pre) {	//队列中不存在该魔方，插入 	if (!isvisited[cantor(mf.up * 10000 + mf.down)]) { //mf.up * 10000 + mf.down使得康托函数的输入为up和down唯一确定的一个八位整数 		isvisited[cantor(mf.up * 10000 + mf.down)] = true;		mf.pre = pre;		mf.op = op;		mfs.push_back(mf);		return true;	}	return false;}//由于一共有三种操作，所以为三叉树 //操作A 1234 8765 -> 8765 1234 通过result引用来返回进行操作后的魔方 char opA(MF mf, int pre, MF &result) {	int m = mf.up;	int n = mf.down;	mf.up = n;	mf.down = m;	result = mf;	result.pre = pre;	result.op = ‘A‘;	return ‘A‘;}//操作B 1234 8765 -> 4123 5876 char opB(MF mf, int pre, MF &result) {	int up_first = (mf.up % 10) * 1000;	int down_first = (mf.down % 10) * 1000;	int up_last = ((mf.up - (mf.up / 1000) * 1000) - ((mf.up - (mf.up / 1000) * 1000) / 100) * 100) / 10;	int down_last = ((mf.down - (mf.down / 1000) * 1000) - ((mf.down - (mf.down / 1000) * 1000) / 100) * 100) / 10;	mf.up = up_first + (mf.up / 1000) * 100 + ((mf.up - (mf.up / 1000) * 1000) / 100) * 10 + up_last;	mf.down = down_first + (mf.down / 1000) * 100 + ((mf.down - (mf.down / 1000) * 1000) / 100) * 10 + down_last;		result = mf;	result.pre = pre;	result.op = ‘B‘;	return ‘B‘;}//操作C 1234 5678 -> 1624 5738 char opC(MF mf, int pre, MF &result) {	int i1 = (mf.up - (mf.up / 1000) * 1000) / 100;	int i2 = ((mf.up - (mf.up / 1000) * 1000) - i1 * 100) / 10;	int j1 = (mf.down - (mf.down / 1000) * 1000) / 100;	int j2 = ((mf.down - (mf.down / 1000) * 1000) - j1 * 100) / 10;	mf.up = (mf.up / 1000) * 1000 + j1 * 100 + i1 * 10 + mf.up % 10;	mf.down = (mf.down / 1000) * 1000 + j2 * 100 + i2 * 10 + mf.down % 10; 	result = mf;	result.pre = pre;	result.op = ‘C‘;	return ‘C‘;}int main () {	int max;		while(cin >> max && max != -1) {		int find_length = 0;		int target[8];		int value;				memset(isvisited, false, sizeof(isvisited)); 				for (int i = 0; i < 8; i++) {			cin >> value;			target[i] = value;		}		vector<MF> mfs;		stack<char> ops;		int fp = 0, rp = 0;		bool success = false;			int up = target[0] * 1000 + target[1] * 100 + target[2] * 10 + target[3]; //目标魔方的上行 		int down = target[7] + target[6] * 10 + target[5] * 100 + target[4] * 1000; //目标魔方的下行 					MF mf;		mf.up = 1234;		mf.down = 8765;		mf.op = ‘ ‘;		mf.pre = -1;		mfs.push_back(mf);		    	//若未找到，则循环查找 		while (mfs[fp].up != up || mfs[fp].down != down) { //或者	while (mfs[fp].up != up || mfs[fp].down != down)  						//广度优先搜索 			//对魔方进行操作，头指针执行正在进行操作的魔方，尾指针执行操作后进入队列的魔方 			MF result;			char a = opA(mfs[fp], fp, result);			if (result.up == up && result.down == down) {			//发现目标魔方，则根据pre来回溯得到操作序列 							while (result.pre != -1) {					ops.push(result.op);					find_length++;					result = mfs[result.pre];//回溯 				}				success = true;				break;			} else if (cmp(mfs, result, a, fp)) {//如果队列中没有该魔方，该魔方进队 				rp++; //尾指针递增 			}						char b = opB(mfs[fp], fp, result);			if (result.up == up && result.down == down) {			//发现目标魔方，则根据pre来回溯得到操作序列 							while (result.pre != -1) {					ops.push(result.op);					find_length++;					result = mfs[result.pre];//回溯 				}				success = true;				break;			} else if (cmp(mfs, result, b, fp)) {				rp++;			}						char c = opC(mfs[fp], fp, result);			if (result.up == up && result.down == down) {			//发现目标魔方，则根据pre来回溯得到操作序列 							while (result.pre != -1) {					ops.push(result.op);					find_length++;					result = mfs[result.pre];//回溯 				}				success = true;				break;			}else if (cmp(mfs, result, c, fp)) {				rp++;			}			fp++; //头指针递增 		}        //如果不能在指定步数内找到，则输出-1 		if (find_length > max) {			cout << -1 << endl;		} else {			cout << find_length << " ";			while (!ops.empty()) { //找到输出由初态变为目标态的过程 				cout << ops.top();				ops.pop();			}			cout << endl;		}	}		return 0;}