【宽搜入门】魔板

题目描述

在成功地发明了魔方之后，鲁比克先生发明了它的二维版本，称作魔板。这是一张有8个大小相同的格子的魔板： 

1 2 3 4 

8 7 6 5 

我们知道魔板的每一个方格都有一种颜色。这8种颜色用前8个正整数来表示。可以用颜色的序列来表示一种魔板状态，规定从魔板的左上角开始，沿顺时针方向依次取出整数，构成一个颜色序列。对于上图的魔板状态，我们用序列（1，2，3，4，5，6，7，8）来表示。这是基本状态。 

这里提供三种基本操作，分别用大写字母“A”，“B”，“C”来表示（可以通过这些操作改变魔板的状态）： 

“A”：交换上下两行； 

“B”：将最右边的一列插入最左边； 

“C”：魔板中央四格作顺时针旋转。 

下面是对基本状态进行操作的示范： 

A: 

8 7 6 5 

1 2 3 4 

B: 

4 1 2 3 

5 8 7 6 

C: 

1 7 2 4 

8 6 3 5 

对于每种可能的状态，这三种基本操作都可以使用。 

你要编程计算用最少的基本操作完成基本状态到目标状态的转换，输出基本操作序列。 

【输入格式】 

输入有多组测试数据 

只有一行，包括8个整数，用空格分开（这些整数在范围 1——8 之间），表示目标状态。 

【输出格式】 

Line 1: 包括一个整数，表示最短操作序列的长度。 

Line 2: 在字典序中最早出现的操作序列，用字符串表示，除最后一行外，每行输出60个字符。 

Sample Input

2 6 8 4 5 7 3 1      

Sample Output

7

BCABCCB

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

思路：

魔板由1~8个数字组成，将8位数转换成10进制，用哈希表来储存历史访问状态，设置数组flag[16777216](8的8次方)。

#include<stdio.h>
#include<queue>

using namespace std;
int final[2][4];
int start[2][4]= {{1,2,3,4},{8,7,6,5}};
int flag[16777216]= {false};

struct Node {
	int r[2][4];
	int step;       //步长
	char s[100];    //记录操作
} node;

void exchange(int &a,int &b) {
	int temp;
	temp=a;
	a=b;
	b=temp;
}

void opA(int a[2][4]) {    //A操作
	for(int i=0; i<4; i++)
		exchange(a[0][i],a[1][i]);
}
void opB(int a[2][4]) {    //B操作
	for(int i=0; i<3; i++) {
		for(int j=0; j<2; j++)
			exchange(a[j][i],a[j][3]);
	}
}
void opC(int a[2][4]) {    //C操作
	exchange(a[0][2],a[1][2]);
	exchange(a[0][1],a[0][2]);
	exchange(a[0][1],a[1][1]);
}
bool equal(int a[2][4],int r[2][4]) {    //判断是否到达终点
	for(int i=0; i<4; i++)
		for(int j=0; j<2; j++) {
			if(a[j][i]!=r[j][i])
				return false;
		}
	return true;
}

int convert(int a[2][4]){    //将当前数组转换成8进制来记录历史
	int i,num=0;
	for(i=0;i<4;i++){
		num=num*8+(a[0][i]-1);
	}
	for(i=3;i>=0;i--){
		num=num*8+(a[1][i]-1);
	}
	return num;
}

void BFS() {
	int i,j,k;
	queue<Node> q;
	for(i=0; i<2; i++)
		for(j=0; j<4; j++)
			node.r[i][j]=start[i][j];    //初始矩阵赋值
	node.step=0;
	q.push(node);
	while(!q.empty()) {
		node=q.front();
		q.pop();

		k=convert(node.r);
		if(!flag[k])   //记录该状态，如果该状态存在过则continue
			flag[k]=true;
		else
			continue;

		if(equal(node.r,final)) {
			printf("%d\n",node.step);
			for(int i=0; i<node.step; i++)
				printf("%c",node.s[i]);
			printf("\n");
			return;
		}

		for(i=0; i<3; i++) {    //进行三种操作
			if(i==0) {
				Node t1=node;
				opA(t1.r);
				t1.s[node.step]='A';
				t1.step=node.step+1;
				q.push(t1);
			}
			if(i==1) {
				Node t2=node;
				opB(t2.r);
				t2.s[node.step]='B';
				t2.step=node.step+1;
				q.push(t2);
			}
			if(i==2) {
				Node t3=node;
				opC(t3.r);
				t3.s[node.step]='C';
				t3.step=node.step+1;
				q.push(t3);
			}
		}
	}
}

int main() {
	int i,j;
	while(scanf("%d",&final[0][0])!=EOF) {
		for(i=1; i<4; i++)
			scanf("%d",&final[0][i]);
		for(i=3; i>=0; i--)
			scanf("%d",&final[1][i]);
		BFS();
	}
	return 0;
}