题目背景
在成功地发明了魔方之后，鲁比克先生发明了它的二维版本，称作魔板。这是一张有 8 个大小相同的格子的魔板：
1 2 3 4
8 7 6 5
题目描述
我们知道魔板的每一个方格都有一种颜色。这 8 种颜色用前 8 个正整数来表示。可以用颜色的序列来表示一种魔板状态，规定从魔板的左上角开始，沿顺时针方向依次取出整数，构成一个颜色序列。对于上图的魔板状态，我们用序列 {1,2,3,4,5,6,7,8} 来表示。这是基本状态。
这里提供三种基本操作，分别用大写字母 A，B，C 来表示（可以通过这些操作改变魔板的状态）：
AA：交换上下两行；
BB：将最右边的一列插入最左边；
CC：魔板中央四格作顺时针旋转。
下面是对基本状态进行操作的示范：
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 个整数 a1,a2⋯a8(1≤a1,a2⋯a8≤8)，用空格分开，不换行，表示目标状态。
输出格式
第一行包括一个整数，表示最短操作序列的长度。
第二行在字典序中最早出现的操作序列，用字符串表示，除最后一行外，每行输出 60 个字符。
输入输出样例
输入
2 6 8 4 5 7 3 1
输出
7 BCABCCB
思路：
1.首先处理把输入的最终状态转成字符串和构造出起始状态的字符串，易于后续判断和比较
string start;
string end1;
for(int i=1;i<=8;i++)
{
start+=char(i+'0');
}
for(int i=0;i<8;i++)
{
cin>>x;
end1+=char(x+'0');
}2. 字符串和二维数组的转换
void set2D(string s)//字符串转二维数组
{
for(int i=0;i<4;i++)
{
g[0][i]=s[i]-'0';
}
for(int i=3,j=4;i>=0;j++,i--)
{
g[1][i]=s[j]-'0';
}
}
string returnstr()
{
string s1;
for(int i=0;i<=3;i++)
{
s1+=g[0][i]+'0';
}
for(int i=3;i>=0;i--)
{
s1+=g[1][i]+'0';
}
return s1;
}
3. A,B,C的操作
string moveA(string s)
{
set2D(s);
for(int i=0;i<4;i++)
{
swap(g[0][i],g[1][i]);
}
return returnstr();
}
string moveB(string s)
{
set2D(s);
int a=g[0][3],b=g[1][3];
for(int i=3;i>=1;i--)
{
g[0][i]=g[0][i-1];
g[1][i]=g[1][i-1];
}
g[0][0]=a,g[1][0]=b;
return returnstr();
}
string moveC(string s)
{
set2D(s);
int tmpt=g[0][1];
g[0][1]=g[1][1];
g[1][1]=g[1][2];
g[1][2]=g[0][2];
g[0][2]=tmpt;
return returnstr();
}4.用dist数组记录所需的步数，pre数组存储此次操作序号以及该字符串是由那个字符串转换过来的，确保最后可以输出全部操作序号
5.dfs的常规思路，符合条件进队，找到目标就返回
AC code
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <unordered_map>查找数比map快
using namespace std;
typedef pair<char, string> CS;
unordered_map<string, int> dist;
unordered_map<string, CS> pre;
string q[100001];
int g[5][5];
void set2D(string s)//字符串转二维数组
{
for (int i = 0; i < 4; i++)
{
g[0][i] = s[i] - '0';
}
for (int i = 3, j = 4; i >= 0; j++, i--)
{
g[1][i] = s[j] - '0';
}
}
string returnstr()
{
string s1;
for (int i = 0; i <= 3; i++)
{
s1 += g[0][i] + '0';
}
for (int i = 3; i >= 0; i--)
{
s1 += g[1][i] + '0';
}
return s1;
}
string moveA(string s)
{
set2D(s);
for (int i = 0; i < 4; i++)
{
swap(g[0][i], g[1][i]);
}
return returnstr();
}
string moveB(string s)
{
set2D(s);
int a = g[0][3], b = g[1][3];
for (int i = 3; i >= 1; i--)
{
g[0][i] = g[0][i - 1];
g[1][i] = g[1][i - 1];
}
g[0][0] = a, g[1][0] = b;
return returnstr();
}
string moveC(string s)
{
set2D(s);
int tmpt = g[0][1];
g[0][1] = g[1][1];
g[1][1] = g[1][2];
g[1][2] = g[0][2];
g[0][2] = tmpt;
return returnstr();
}
int dfs(string start, string end1)
{
q[0] = start;
dist[start] = 0;
int tt = 0, hh = 0;
while (hh <= tt)
{
string t = q[hh++];
if (t == end1) return dist[end1];
string m[3];
m[0] = moveA(t);
m[1] = moveB(t);
m[2] = moveC(t);
for (int i = 0; i < 3; i++)
{
string s = m[i];
if (!dist.count(s)) {
dist[s] = dist[t] + 1;
pre[s] = { char('A' + i),t };
q[++tt] = s;
}
if (s == end1) return dist[end1];
}
}
return -1;
}
int main()
{
int x;
string start;
string end1;
for (int i = 1; i <= 8; i++)
{
start += char(i + '0');
}
for (int i = 0; i < 8; i++)
{
cin >> x;
end1 += char(x + '0');
}
int c = dfs(start, end1);
cout << c << endl;
string t;
while (end1 != start)
{
t += pre[end1].first;
end1 = pre[end1].second;
}
reverse(t.begin(), t.end());
cout << t;
return 0;
}