BFSUSACOMagicSquares(魔板)

BFS - USACO - Magic Squares(魔板)

Rubik 先生在发明了风靡全球的魔方之后&＃xff0c;又发明了它的二维版本——魔板。

这是一张有 8 个大小相同的格子的魔板&＃xff1a;

1 2 3 4
8 7 6 5


我们知道魔板的每一个方格都有一种颜色。

这 8 种颜色用前 8 个正整数来表示。

可以用颜色的序列来表示一种魔板状态&＃xff0c;规定从魔板的左上角开始&＃xff0c;沿顺时针方向依次取出整数&＃xff0c;构成一个颜色序列。

对于上图的魔板状态&＃xff0c;我们用序列 (1,2,3,4,5,6,7,8) 来表示&＃xff0c;这是基本状态。

这里提供三种基本操作&＃xff0c;分别用大写字母 A&＃xff0c;B&＃xff0c;C 来表示&＃xff08;可以通过这些操作改变魔板的状态&＃xff09;&＃xff1a;

A&＃xff1a;交换上下两行&＃xff1b;
B&＃xff1a;将最右边的一列插入到最左边&＃xff1b;
C&＃xff1a;魔板中央对的4个数作顺时针旋转。

下面是对基本状态进行操作的示范&＃xff1a;

A&＃xff1a;

8 7 6 5
1 2 3 4


B&＃xff1a;

4 1 2 3
5 8 7 6


C&＃xff1a;

1 7 2 4
8 6 3 5


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

你要编程计算用最少的基本操作完成基本状态到特殊状态的转换&＃xff0c;输出基本操作序列。

**注意&＃xff1a;**数据保证一定有解。

输入格式
输入仅一行&＃xff0c;包括 8 个整数&＃xff0c;用空格分开&＃xff0c;表示目标状态。

输出格式
输出文件的第一行包括一个整数&＃xff0c;表示最短操作序列的长度。

如果操作序列的长度大于0&＃xff0c;则在第二行输出字典序最小的操作序列。

数据范围
输入数据中的所有数字均为 1 到 8 之间的整数。

输入样例&＃xff1a;

2 6 8 4 5 7 3 1


输出样例&＃xff1a;

7
BCABCCB


分析&＃xff1a;

$要求操作步数最少\&＃xff0c;字典序尽量小。$

$$\begin{gathered} 要字典序小\&＃xff0c;就按照A、B、C的顺序进行操作\&＃xff0c;用哈希表d存储每一种状态与初始状态之间的距离(操作次数)\&＃xff0c; \\ pre存储每一种状态是由哪一种状态转移而来的\&＃xff0c;是以何种操作转移而来的。 \end{gathered}$$

$$\begin{gathered} 需要注意的是\&＃xff0c;本题是按照顺时针的顺序来表示状态的\&＃xff0c;为了与我们习惯一致\&＃xff0c;set函数来对第二列的数进行翻转操作。 \\ 即将12345678转化为12348765。 \end{gathered}$$

$BFS求出最小步数后\&＃xff0c;再通过pre表反推具体操作。$

代码&＃xff1a;

#include
#include
#include
#include
#includeusing namespace std;const int N &＃61; 1e6;string set(string u)
{string v;for(int i&＃61;0;i<4;i&＃43;&＃43;) v&＃43;&＃61;u[i];for(int i&＃61;7;i>&＃61;4;i--) v&＃43;&＃61;u[i];return v;
}string A(string t)
{t&＃61;set(t);for(int j&＃61;0;j<4;j&＃43;&＃43;) swap(t[j],t[j&＃43;4]);return set(t);
}string B(string t)
{t&＃61;set(t);char u&＃61;t[3],v&＃61;t[7];for(int i&＃61;3;i>&＃61;1;i--){t[i]&＃61;t[i-1];t[i&＃43;4]&＃61;t[i&＃43;4-1];}t[0]&＃61;u,t[4]&＃61;v;return set(t);
}string C(string t)
{t&＃61;set(t);char u&＃61;t[1];t[1]&＃61;t[5];t[5]&＃61;t[6];t[6]&＃61;t[2];t[2]&＃61;u;return set(t);
}string S&＃61;"12345678",E;
string q[N];
unordered_map<string,int> d;
unordered_map<string,pair<char,string>> pre;void bfs()
{int hh&＃61;0,tt&＃61;-1;q[&＃43;&＃43;tt]&＃61;S;d[S]&＃61;0;while(hh<&＃61;tt){string t&＃61;q[hh&＃43;&＃43;];if(t&＃61;&＃61;E) return ;string u[3];u[0]&＃61;A(t);u[1]&＃61;B(t);u[2]&＃61;C(t);for(int i&＃61;0;i<3;i&＃43;&＃43;)if(!d.count(u[i])){d[u[i]]&＃61;d[t]&＃43;1;pre[u[i]]&＃61;{char(&＃39;A&＃39;&＃43;i),t};q[&＃43;&＃43;tt]&＃61;u[i];}}
}int main()
{char c;for(int i&＃61;0;i<8;i&＃43;&＃43;){cin>>c;E&＃43;&＃61;c;}bfs();int step&＃61;d[E];cout<<step<<endl;string ans;while(E!&＃61;S){ans&＃43;&＃61;pre[E].first;E&＃61;pre[E].second;}reverse(ans.begin(),ans.end());if(step) cout<<ans<<endl;return 0;
}