[搜索]魔板 Magic Squares

题目传送门：https://www.luogu.org/problemnew/show/P2730

----------

题目背景
在成功地发明了魔方之后，鲁比克先生发明了它的二维版本，称作魔板。这是一张有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”：魔板中央四格作顺时针旋转。

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

8 7 6 5
    1 2 3 4

4 1 2 3
    5 8 7 6

1 7 2 4
    8 6 3 5

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

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

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

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

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

----------

题解：
好久没做水题了，结果发现不会写BFS了QAQ
这道题BFS还是比较好想吧？对于每个状态，把它进行ABC操作之后的状态依次进队即可。这样就保证了字典序。
主要是记录重复状态，普通的bool数组无法开到那么大，所以，就要用到我刚学的黑科技：康托展开。
公式：$X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0!$，其中$a[i]$为当前未出现的元素中是排在第几个（从0开始）
这样就把每一个状态转化为了一个较小的数，且肯定是一一对应的。开个普通的bool数组记录下就好了。

还有就是: 
```
1 2 3 4 5 6 7 8
```
对应的是:
```
1 2 3 4
8 7 6 5
```
**而不是：**
```
1 2 3 4
5 6 7 8
```
又是一发读题杀QAQ

----------
贴上代码：
```
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<vector>
#include<cstring>
#define maxn 100005
using namespace std;
bool vis[maxn];
int ans[10],fact[10],tar;
struct node
{
	int now[10],sz;
	char ch[100];
};
queue<node> q;
int cantor(int *s)//康托展开
{
	int temp,num=s[1]*fact[7];
	for(int i=2;i<=8;i++)
	{
		temp=0;
		for(int j=1;j<i;j++)
			if(s[j]<s[i]) temp++;
		num=num+(s[i]-temp)*fact[8-i];
	}
	return num+1;
}
void op_A(int *x)
{for(int i=1;i<=4;i++) swap(x[i],x[8-i+1]);}
void op_B(int *x)
{
	for(int i=4;i>1;i--) swap(x[i],x[i-1]);
	for(int i=5;i<8;i++) swap(x[i],x[i+1]);
}
void op_C(int *x)
{swap(x[2],x[3]),swap(x[7],x[2]),swap(x[6],x[7]);}
int main()
{
	node start;
	fact[0]=1;
	for(int i=1;i<=8;i++) start.now[i]=i,fact[i]=fact[i-1]*i;
	for(int i=1;i<=8;i++) scanf("%d",&ans[i]);
	tar=cantor(ans);
	memset(start.ch,0,sizeof(start.ch)),start.sz=0;
	q.push(start);
	while(!q.empty())
	{
		node t=q.front();q.pop();
		node tmp;tmp.sz=t.sz+1;
		memcpy(tmp.ch,t.ch,sizeof(t.ch));
		int Hash=cantor(t.now);//状态与Hash值转换
		if(Hash==tar)
		{
			printf("%d\n",t.sz);
			for(int i=1;i<=t.sz;i++)
			{
				printf("%c",t.ch[i]);
				if(i%60==0) printf("\n");
			}
			return 0;
		}
		if(vis[Hash]) continue;
		vis[Hash]=1;
		//A操作，进队
		memcpy(tmp.now,t.now,sizeof(t.now));
		op_A(tmp.now);
		tmp.ch[tmp.sz]='A';
		q.push(tmp);
		//B操作，进队
		memcpy(tmp.now,t.now,sizeof(t.now));
		op_B(tmp.now);
		tmp.ch[tmp.sz]='B';
		q.push(tmp);
		//C操作，进队
		memcpy(tmp.now,t.now,sizeof(t.now));
		op_C(tmp.now);
		tmp.ch[tmp.sz]='C';
		q.push(tmp);
	}
}
```

PhantasmDragon 's Blog