一、题面
二、分析
该题与之前做的八数码不同，它是一个2*4的棋盘，并且没有空的区域。这样考虑的情况是很少的，依然结合康托展开，这时康托展开最多也只乘7的阶乘，完全可以BFS先预处理一遍。
这里需要注意，在处理的时候，仔细读题，他的二维变一维的顺序是顺时针一遍读过来的。
预处理完后，这里需要用一个小技巧，就是置换。
$$ \begin{pmatrix} 3 & 2 & 1 & 4 & 5 & 6 & 7 & 8\\1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \end{pmatrix} $$
上面使用的例子是$32145678$，然后相当于把它移到了和$12345678$一个起跑线上，这样做的好处就是我们预处理的答案能够适用所有情况。
假设目标状态是$87654321$，这样把目标状态置换成与上面对应的即可。
$$ \begin{pmatrix} 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1\\8 & 7 & 6 & 5 & 4 & 1 & 2 & 3 \\ \end{pmatrix} $$
这样就可以直接输出结果了。
三、AC代码
#include <cstdio>
#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
#include <algorithm> using namespace std; const int MAXN = ;
const int fac[] = {, , , , , , , , , }; //factorial
bool visit[MAXN];
struct Node
{
int m[];
int cat;
};
char op[] = "ABC";
string ans[MAXN]; void A(Node &t)
{
std::reverse(t.m , t.m+);
} void B(Node &t)
{
int temp = t.m[];
for(int i = ; i > ; i--)
{
t.m[i] = t.m[i-];
}
t.m[] = temp;
temp = t.m[];
for(int i = ; i < ; i++)
{
t.m[i] = t.m[i+];
}
t.m[] = temp;
} void C(Node &t)
{
int temp = t.m[];
t.m[] = t.m[];
t.m[] = t.m[];
t.m[] = t.m[];
t.m[] = temp;
} int Cantor(int s[])
{
int t, ans = ;
for(int i = ; i < ; i++)
{
t = ;
for(int j = i+; j < ; j++)
{
if(s[j] < s[i])
t++;
}
ans += t*fac[-i];
}
return ans;
} void bfs()
{
memset(visit, , sizeof(visit));
Node t;
for(int i = ; i < ; i++)
t.m[i] = i+;
t.cat = Cantor(t.m);
queue<Node> Q;
ans[t.cat] = "";
visit[t.cat] = ;
Q.push(t);
while(!Q.empty())
{
Node p = Q.front();
Q.pop();
for(int i = ; i < ; i++)
{
t = p;
switch(i)
{
case : A(t);break;
case : B(t);break;
case : C(t);break;
}
t.cat = Cantor(t.m);
if( !visit[t.cat] )
{ ans[t.cat] = ans[p.cat]+op[i];
visit[t.cat] = ;
Q.push(t);
}
}
} } int main()
{
//freopen("input.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
char s[];
int a[] = {}, b[] = {};
bfs();
while(scanf("%s", s)!=EOF)
{
for(int i = ; i < ; i++)
{
a[s[i] - ''] = i+;
}
scanf("%s", s);
for(int i = ; i < ; i++)
{
b[i] = a[s[i] - ''];
}
cout << ans[Cantor(b)] << endl;
}
return ;
}