Constraints

Time Limit: 1 secs, Memory Limit: 32 MB , Special Judge

Description

题目和A题相同，在这里我们把数据范围扩大：N可能超过10。

Input

输入包括多个要求解的魔板，每个魔板用三行描述。

第一行步数N，表示最多容许的步数。

第二、第三行表示目标状态，按照魔板的形状，颜色用1到8的表示。

Output

对于每一个要求解的魔板，输出一行。

首先是一个整数M，表示你找到解答所需要的步数。接着若干个空格之后，从第一步开始按顺序给出M步操作（每一步是A、B或C），相邻两个操作之间没有任何空格。

Sample Input

45 8 7 64 1 2 338 7 6 51 2 3 4-1
Sample Output
2  AB1  A评分：M超过N或者给出的操作不正确均不能得分。康托展开式：一种排列的状态和排列所在字典序之间的映射关系：
int factorial[8] = {5040,720,120,24,6,2,1,1};//7~0的阶乘结果int cantor(Node n, int length){	int x = n.up*pow(10,length) + n.down ;//cout << "x = " << x << endl;	int a[2*length];	for(int i=2*length-1; i>=0; i--)	{		a[i] = x%10; //cout << "i= " << i << "----" << a[i] << endl;		x /= 10;	}		int cnt, sum=0;	for(int i=0; i<2*length; i++)	{		cnt = 0;		for(int j=i+1; j<2*length; j++){			if(a[i] > a[j])				cnt++ ;		}		sum += cnt*factorial[i];	}		return sum;}数据结构：
struct Node{	int up, down;	string oper;	//记录到当前排序状态所需要的操作，初始状态操作为空字符串 };思路：1. 将初始排列状态节点压入队列。           2.记录top为队列首端节点，并将队列顶端首端元素pop。           3.循环对top进行ABC处理，处理结果用tmp记录，若其用康托展开式计算的位置未出现过，将其压入队列，否则弃之。           4.当队列非空时继续进行2，否则停止搜索。
Node Opera(Node n){	swap(n.up , n.down );	return n;				// notice return ! }Node operB(Node n){	n.up = n.up/10 + n.up%10*1000;	n.down = n.down/10 + n.down%10*1000;	return n;}Node operC(Node n){	int a = n.up/100%10, b = n.up/10%10;	int c = n.down/100%10, d = n.down/10%10;	n.up = n.up/1000*1000 + n.up%10 + c*100 + a*10;	n.down = n.down/1000*1000 + n.down%10 + d*100 + b*10;	return n;}Node oper(Node n,int op){	if(op==0)return operA(n);	else if(op==1) return operB(n);	return operC(n);}初始化和输入：
void input() // input des{	int a[8];	des.up = des.down = 0;	for(int i=0; i<8; i++)		scanf("%d", &a[i]);	for(int i=0; i<4; i++)	{		des.up = 10*des.up + a[i];		des.down = 10*des.down + a[i+4];	}}Node init(){	Node n;	n.up = 1234;	n.down = 5678;	memset(visited_n, 0, sizeof(visited_n)); // 设置所以排列状态为为访问状态	return n;}main函数：
int main(){	while(cin>>N && N>-1){		bool successful = false;	// 是否搜到结果的标记		Node tmp, top;		top = init();		input();		QQ.push(top) ;		int pos;		while(!qq.empty() ){			top = qq.front() ;			qq.pop() ;			if(top.oper.size() > N){	// 当oper长度大于给定长度时，不在将其压入队列之中，没有这里会爆内存				continue;			}			if(top.up == des.up && top.down == des.down ){				cout << top.oper.size();				if(top.oper.size() > 0)					cout << " " << top.oper << endl;				else cout << endl; // 注意输出格式， 提交时没换行符				successful = true;				break;			}			else{				for(int i=0; i<3; i++){					tmp = oper(top,i);					pos = cantor(tmp,4) ;						if(!visited_n[pos]){	// 判断重复！！ 关键						visited_n[pos] = 1;	// 为出现时标记						tmp.oper += (i+'A');						qq.push(tmp) ;					}				}			}		}		while(!qq.empty() ) qq.pop() ;		if(successful == false) 			cout << -1 << endl;	}	return 0;}参考的康托展开式：http://blog.csdn.net/zhongkeli/article/details/6966805?winzoom=1（为什么下面加不上？）