Constraints

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

Description

題目和A題相同，在這里我們把數(shù)據(jù)范圍擴(kuò)大：N可能超過10。

Input

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

第一行步數(shù)N，表示最多容許的步數(shù)。

第二、第三行表示目標(biāo)狀態(tài)，按照魔板的形狀，顏色用1到8的表示。

Output

對于每一個要求解的魔板，輸出一行。

首先是一個整數(shù)M，表示你找到解答所需要的步數(shù)。接著若干個空格之后，從第一步開始按順序給出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或者給出的操作不正確均不能得分。康托展開式：一種排列的狀態(tài)和排列所在字典序之間的映射關(guān)系：
int factorial[8] = {5040,720,120,24,6,2,1,1};//7~0的階乘結(jié)果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;}數(shù)據(jù)結(jié)構(gòu)：
struct Node{	int up, down;	string oper;	//記錄到當(dāng)前排序狀態(tài)所需要的操作，初始狀態(tài)操作為空字符串 };思路：1. 將初始排列狀態(tài)節(jié)點(diǎn)壓入隊(duì)列。           2.記錄top為隊(duì)列首端節(jié)點(diǎn)，并將隊(duì)列頂端首端元素pop。           3.循環(huán)對top進(jìn)行ABC處理，處理結(jié)果用tmp記錄，若其用康托展開式計算的位置未出現(xiàn)過，將其壓入隊(duì)列，否則棄之。           4.當(dāng)隊(duì)列非空時繼續(xù)進(jìn)行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)); // 設(shè)置所以排列狀態(tài)為為訪問狀態(tài)	return n;}main函數(shù)：
int main(){	while(cin>>N && N>-1){		bool successful = false;	// 是否搜到結(jié)果的標(biāo)記		Node tmp, top;		top = init();		input();		QQ.push(top) ;		int pos;		while(!qq.empty() ){			top = qq.front() ;			qq.pop() ;			if(top.oper.size() > N){	// 當(dāng)oper長度大于給定長度時，不在將其壓入隊(duì)列之中，沒有這里會爆內(nèi)存				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]){	// 判斷重復(fù)！！ 關(guān)鍵						visited_n[pos] = 1;	// 為出現(xiàn)時標(biāo)記						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（為什么下面加不上？）