master

分支 (1)

管理

管理

master

algorithm
/
二阶魔方操作 (2).cpp

#include <iostream>
#include <string>
#include <math.h>
#include <queue>
using namespace std;


struct SecOrderRubikCube{
	char f1,f2,f3,f4;
	char l1,l2,l3,l4;
	char b1,b2,b3,b4;
	char r1,r2,r3,r4;
	char u1,u2,u3,u4;
	char d1,d2,d3,d4;


	void fw(){
		char f;
		f = f1;
		f1 = f3;
		f3 = f4;
		f4 = f2;
		f2 = f;
		f = u3;
		u3 = l4;
		l4 = d2;
		d2 = r1;
		r1 = f;
		f = u4;
		u4 = l2;
		l2 = d1;
		d1 = r3;
		r3 = f;
		return;
	}
	void fa(){
		char f;
		f = f1;
		f1 = f2;
		f2 = f4;
		f4 = f3;
		f3 = f;
		f = u3;
		u3 = r1;
		r1 = d2;
		d2 = l4;
		l4 = f;
		f = u4;
		u4 = r3;
		r3 = d1;
		d1 = l2;
		l2 = f;

		return;
	}
	void bw(){
		char f;
		f = b1;
		b1 = b3;
		b3 = b4;
		b4 = b2;
		b2 = f;
		f = u2;
		u2 = r4;
		r4 = d3;
		d3 = l1;
		l1 = f;
		f = u1;
		u1 = r2;
		r2 = d4;
		d4 = l3;
		l3 = f;
		return;
	}
	void ba(){
		char f;
		f = b1;
		b1 = b2;
		b2 = b4;
		b4 = b3;
		b3 = f;
		f = u2;
		u2 = l1;
		l1 = d3;
		d3 = r4;
		r4 = f;
		f = u1;
		u1 = l3;
		l3 = d4;
		d4 = r2;
		r2 = f;

		return;
	}
	void lw(){
		char f;
		f = l1;
		l1 = l3;
		l3 = l4;
		l4 = l2;
		l2 = f;
		f = u1;
		u1 = b4;
		b4 = d1;
		d1 = f1;
		f1 = f;
		f = u3;
		u3 = b2;
		b2 = d3;
		d3 = f3;
		f3 = f;
		return;
	}
	void la(){
		char f;
		f = l1;
		l1 = l2;
		l2 = l4;
		l4 = l3;
		l3 = f;
		f = u1;
		u1 = f1;
		f1 = d1;
		d1 = b4;
		b4 = f;
		f = u3;
		u3 =f3;
		f3 = d3;
		d3 = b2;
		b2 = f;

		return;
	}
	void rw(){
		char f;
		f = r1;
		r1 = r3;
		r3 = r4;
		r4 = r2;
		r2 = f;
		f = u4;
		u4 = f4;
		f4 = d4;
		d4 = b1;
		b1 = f;
		f = u2;
		u2 = f2;
		f2 = d2;
		d2 = b3;
		b3 = f;
		return;
	}
	void ra(){
		char f;
		f = r1;
		r1 = r2;
		r2 = r4;
		r4 = r3;
		r3 = f;
		f = u4;
		u4 = b1;
		b1 = d4;
		d4 = f4;
		f4 = f;
		f = u2;
		u2 = b3;
		b3 = d2;
		d2 = f2;
		f2 = f;

		return;
	}
	void uw(){
		char f;
		f = u1;
		u1 = u3;
		u3 = u4;
		u4 = u2;
		u2 = f;
		f = b2;
		b2 = l2;
		l2 = f2;
		f2 = r2;
		r2 = f;
		f = b1;
		b1 = l1;
		l1 = f1;
		f1 = r1;
		r1 = f;
		return;
	}
	void ua(){
		char f;
		f = u1;
		u1 = u2;
		u2 = u4;
		u4 = u3;
		u3 = f;
		f = b2;
		b2 = r2;
		r2 = f2;
		f2 = l2;
		l2 = f;
		f = b1;
		b1 = r1;
		r1 = f1;
		f1 = r1;
		r1 = f;

		return;
	}
	void dw(){
		char f ;
		f = d1;
		d1 = d3;
		d3 = d4;
		d4 = d2;
		d2 = f;
		f = f3;
		f3 = l3;
		l3 = b3;
		b3 = r3;
		r3 = f;
		f = f4;
		f4 = l4;
		l4 = b4;
		b4 = r4;
		r4 = f;
		return;
	}
	void da(){
		char f;
		f = d1;
		d1 = d2;
		d2 = d4;
		d4 = d3;
		d3 = f;
		f = f3;
		f3 = r3;
		r3 = b3;
		b3 = l3;
		l3 = f;
		f = f4;
		f4 = r4;
		r4 = b4;
		b4 = l4;
		l4 = f;

		return;
	}
	bool check(){
		if(f1 != f2  ||  f1 != f3  ||  f1 != f4)
			return false;
		if(l1 != l2  ||  l1 != l3  ||  l1 != l4)
			return false;
		if(b1 != b2  ||  b1 != b3  ||  b1 != b4)
			return false;
		if(r1 != r2  ||  r1 != r3  ||  r1 != r4)
			return false;
		if(u1 != u2  ||  u1 != u3  ||  u1 != u4)
			return false;
		if(d1 != d2  ||  d1 != d3  ||  d1 != d4)
			return false;
		return true;
	}
};

int wsum=0,csum=0;


struct answer{
	string ans;
	int step;
	answer operator + (answer a){
		if(step <= a.step){
			answer output;
			output.step = step;
			output.ans = ans;
			return output;
		}
		else{
			return a;
		}
	}
};

/*
yyoo
rggg
obrr
ogbb
yyrb
wwww


rgrr
bbbb
gooo
orgg
yyyy
wwww
*/


//answer dfs(SecOrderRubikCube cube,int k){
//	if(k >= 14){
//		answer output;
//		output.step = -1;
//		output.ans = "";
//		wsum++;
//		cout<<"<find a time out answer> "<<" "<<k<<" "<<wsum<<" "<<csum<<endl;
//		return output;
//	}
//	if(cube.check()){
//		answer output;
//		output.step = k;
//		output.ans = "";
//		csum++;
//		cout<<"<find a correct answer> "<<k<<endl;
//		return output;
//	}
//	answer ans;
//	answer l;
//	ans.step = 0x7fffffff;
//	for(int i=0;i<6;i++){
//		if(i == 0){
//			cube.fw();
//			l = dfs(cube,k+1);
//			l.ans = "fw"+l.ans;
//			cube.fa();
//		}
//		else if(i == 1){
//			cube.fa();
//			l = dfs(cube,k+1);
//			l.ans = "fa"+l.ans;
//			cube.fw();
//		}
//		else if(i == 2){
//			cube.lw();
//			l = dfs(cube,k+1);
//			l.ans = "lw"+l.ans;
//			cube.la();
//		}
//		else if(i == 3){
//			cube.la();
//			l = dfs(cube,k+1);
//			l.ans = "la"+l.ans;
//			cube.lw();
//		}
//		else if(i == 4){
//			cube.uw();
//			l = dfs(cube,k+1);
//			l.ans = "uw"+l.ans;
//			cube.ua();
//		}
//		else if(i == 5){
//			cube.ua();
//			l = dfs(cube,k+1);
//			l.ans = "ua"+l.ans;
//			cube.uw();
//		}
//		if(l.step != -1)
//			ans = ans+l;
//	}
//	return ans;
//}

	queue<SecOrderRubikCube> q1;
	queue<answer> q2;

answer bfs(SecOrderRubikCube cube){
	answer ans;
	SecOrderRubikCube Ccube=cube;
	ans.ans = "";
	ans.step = 0;
	q1.push(Ccube);
	q2.push(ans);
	while(!Ccube.check()){
		wsum++;
//		cout<<"<times> "<<wsum<<" "<<q2.front().step<<endl;
		printf("<times> %d %d %d\n",q2.front().step,q1.size(),wsum);
		for(int i=0;i<6;i++){
//			cout<<q1.size()<<" ";
			Ccube = q1.front();
			ans = q2.front();
			if(i == 0){
				if(ans.ans.length() >= 3 &&  ans.ans[ans.ans.length()-3] == 'f'  &&  ans.ans[ans.ans.length()-2] == 'a')
					continue;
				Ccube.fw();
				ans.ans += "fw\n";
				ans.step++;
				q1.push(Ccube);
				q2.push(ans);
			}
			else if(i == 1){
				if(ans.ans.length() >= 3 &&  ans.ans[ans.ans.length()-3] == 'f'  &&  ans.ans[ans.ans.length()-2] == 'w')
					continue;
				Ccube.fa();
				ans.ans += "fa\n";
				ans.step++;
				q1.push(Ccube);
				q2.push(ans);
			}
			else if(i == 2){
				if(ans.ans.length() >= 3 &&  ans.ans[ans.ans.length()-3] == 'l'  &&  ans.ans[ans.ans.length()-2] == 'a')
					continue;
				Ccube.lw();
				ans.ans += "lw\n";
				ans.step++;
				q1.push(Ccube);
				q2.push(ans);
			}
			else if(i == 3){
				if(ans.ans.length() >= 3 &&  ans.ans[ans.ans.length()-3] == 'l'  &&  ans.ans[ans.ans.length()-2] == 'w')
					continue;
				Ccube.la();
				ans.ans += "la\n";
				ans.step++;
				q1.push(Ccube);
				q2.push(ans);
			}
			else if(i == 4){
				if(ans.ans.length() >= 3 &&  ans.ans[ans.ans.length()-3] == 'u'  &&  ans.ans[ans.ans.length()-2] == 'a')
					continue;
				Ccube.uw();
				ans.ans += "uw\n";
				ans.step++;
				q1.push(Ccube);
				q2.push(ans);
			}
			else if(i == 5){
				if(ans.ans.length() >= 3 &&  ans.ans[ans.ans.length()-3] == 'u'  &&  ans.ans[ans.ans.length()-2] == 'w')
					continue;
				Ccube.ua();
				ans.ans += "ua\n";
				ans.step++;
				q1.push(Ccube);
				q2.push(ans);
			}
			if(Ccube.check()){
				break;
			}
		}
		q1.pop();
		q2.pop();
	}
	return ans;
}


int main(){
	SecOrderRubikCube cube;
	char a1,a2,a3,a4;
	cin>>a1>>a2>>a3>>a4;
	cube.f1 = a1;
	cube.f2 = a2;
	cube.f3 = a3;
	cube.f4 = a4;
	cin>>a1>>a2>>a3>>a4;
	cube.l1 = a1;
	cube.l2 = a2;
	cube.l3 = a3;
	cube.l4 = a4;
	cin>>a1>>a2>>a3>>a4;
	cube.b1 = a1;
	cube.b2 = a2;
	cube.b3 = a3;
	cube.b4 = a4;
	cin>>a1>>a2>>a3>>a4;
	cube.r1 = a1;
	cube.r2 = a2;
	cube.r3 = a3;
	cube.r4 = a4;
	cin>>a1>>a2>>a3>>a4;
	cube.u1 = a1;
	cube.u2 = a2;
	cube.u3 = a3;
	cube.u4 = a4;
	cin>>a1>>a2>>a3>>a4;
	cube.d1 = a1;
	cube.d2 = a2;
	cube.d3 = a3;
	cube.d4 = a4;

//	while(true){
//		char input;
//		cin>>input;
//		if(input == '1'){
//			cin>>input;
//			if(input == 'f')
//				cube.fw();
//			else if(input == 'l')
//				cube.lw();
//			else if(input == 'b')
//				cube.bw();
//			else if(input == 'r')
//				cube.rw();
//			else if(input == 'u')
//				cube.uw();
//			else if(input == 'd')
//				cube.dw();
//		}
//		else if(input == '2'){
//			cin>>input;
//			if(input == 'f')
//				cube.fa();
//			else if(input == 'l')
//				cube.la();
//			else if(input == 'b')
//				cube.ba();
//			else if(input == 'r')
//				cube.ra();
//			else if(input == 'u')
//				cube.ua();
//			else if(input == 'd')
//				cube.da();
//		}
//		else{
//			cout<<cube.check()<<endl;
//		}
//
//		cout
//		<<cube.f1<<" "<<cube.f2<<" "<<cube.f3<<" "<<cube.f4<<endl
//		<<cube.l1<<" "<<cube.l2<<" "<<cube.l3<<" "<<cube.l4<<endl
//		<<cube.b1<<" "<<cube.b2<<" "<<cube.b3<<" "<<cube.b4<<endl
//		<<cube.r1<<" "<<cube.r2<<" "<<cube.r3<<" "<<cube.r4<<endl
//		<<cube.u1<<" "<<cube.u2<<" "<<cube.u3<<" "<<cube.u4<<endl
//		<<cube.d1<<" "<<cube.d2<<" "<<cube.d3<<" "<<cube.d4<<endl;
//
//		cout<<endl;
//	}

	cout<<cube.f1<<cube.f2<<cube.f3<<cube.f4<<endl;

	answer out;
	out = bfs(cube);
	cout<<out.step<<endl;
	cout<<out.ans<<endl;
	return 0;
}