[BFS][哈希]Magic Squares 魔板

本文主要是介绍[BFS][哈希]Magic Squares 魔板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述
在成功地发明了魔方之后，拉比克先生发明了它的二维版本，称作魔板。这是一张有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
　　对于每种可能的状态，这三种基本操作都可以使用。
　　你要编程计算用最少的基本操作完成基本状态到目标状态的转换，输出基本操作序列。

Input

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

Output

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

分析
此题是一个非常好的BFS用哈希优化减时间的典范。。
因为所有组合为8！所以可以计算出数组至少需要40320.
然后哈希表按照惯例开大点节省时间（五六万的素数就行了）
接着BFS，当判断有无出现时，哈希判断即可
其实这题我是有自己的想法的。。
但是频繁的错误让我以为是我程序的错。。看了看标程，即使是功能没有区别的我也换了，还是错。。
结果最后发现是题目没有写到当无法达成的时候要输出NO。。。
然后TLE。哈希表要开大，这是血的教训。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
int tail,head,r[3][8],i,p=53713,len,f[40320];
string state[40321],h[53713],s;
char c[40320],q;
void pre()
{r[0][0]=8;r[0][1]=7;r[0][2]=6;r[0][3]=5;r[0][4]=4;r[0][5]=3;r[0][6]=2;r[0][7]=1;r[1][0]=4;r[1][1]=1;r[1][2]=2;r[1][3]=3;r[1][4]=6;r[1][5]=7;r[1][6]=8;r[1][7]=5;r[2][0]=1;r[2][1]=7;r[2][2]=2;r[2][3]=4;r[2][4]=5;r[2][5]=3;r[2][6]=6;r[2][7]=8;
}
int locate(string x)
{int i=0,l;l=atoi(x.c_str());while (h[(i+l)%p]!=""&&h[(i+l)%p]!=x)i++;return (l+i)%p;
}
bool hash(string x)
{int i=locate(x);if (h[i]=="")h[i]=x;else return true;return false;
}
void print(int x)
{if (f[x]==0) return;len++;print(f[x]);s+=c[x];
}
void bfs()
{int i,j;state[1]="12345678";h[12345678%p]=state[1];tail=1;if (state[1]==state[0])return;do{head++;for (i=0;i<3;i++){tail++;c[tail]=65+i;f[tail]=head;state[tail]=state[head];for (j=0;j<8;j++) state[tail][j]=state[head][r[i][j]-1];if (hash(state[tail])) tail--;if (state[tail]==state[0]){print(tail);tail=0;return;}}}while (head<=tail);
}
int main()
{pre();for (i=0;i<8;i++){cin>>c;state[0]+=c;}bfs();if (head==tail) cout<<"NO"<<endl;else cout<<len<<endl;cout<<s<<endl;
}