【寬搜入門】魔闆

題目描述

在成功地發明了魔方之後，魯比克先生發明了它的二維版本，稱作魔闆。這是一張有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;
}