题面
给定一个矩阵
1 2 3 4
8 7 6 5
我们用1 2 3 4 5 6 7 8表示这个矩阵
有三个操作
A：交换上下两行；
B：将最右边的一列插入到最左边；
C：魔板*对的4个数作顺时针旋转。
下面是对基本状态进行操作的示范：
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
对于每种可能的状态，这三种基本操作都可以使用。
要求求出从12345678到目标状态的最小操作数，并且输出字典序最小的答案
输入样例：
2 6 8 4 5 7 3 1
输出样例：
7
BCABCCB
思路
这是一道比较有趣的搜索题，我们主要思路就是用起始状态进行BFS，每次求出三个状态，以ABC的顺序进行BFS
每个状态记录其前驱状态及其操作的字符
并且转移我们的操作数(前驱状态操作数+1)
这两点都用map来实现就很方便
其他就没有太多的难点，这题主要难在代码量比较大，属于模拟+搜索，码农题
代码
#include<bits/stdc++.h>
using namespace std;
unordered_map<string,int> dis;
unordered_map<string,pair<char,string> > pre;
string move1(string t)
{
string res="";
for(int i=7;i>=4;i--) res+=t[i];
for(int i=3;i>=0;i--) res+=t[i];
return res;
}
string move2(string t)
{
string res="";
res+=t[3];
for(int i=0;i<3;i++) res+=t[i];
for(int i=5;i<8;i++) res+=t[i];
res+=t[4];
return res;
}
string move3(string t)
{
string res=t;
swap(res[5],res[6]);
swap(res[1],res[2]);
swap(res[1],res[5]);
return res;
}
int bfs(string start,string end)
{
if (start==end) return 0;
queue<string> q;
q.push(start);
dis[start]=0;
while(q.size())
{
auto t=q.front();
q.pop();
string str[3];
//计算出三种目标状态的字符串，顺序必须是ABC
str[0]=move1(t);
str[1]=move2(t);
str[2]=move3(t);
for(int i=0;i<3;i++)
{
if (dis.count(str[i])==0)//没有在dis里出现过就代表是合法的
{
dis[str[i]]=dis[t]+1;
pre[str[i]]={char(i+‘A‘),t};
if (str[i]==end) return dis[str[i]];
q.push(str[i]);
}
}
}
}
int main(){
string start="12345678",end="";//初始状态为1234578
for(int i=0;i<8;i++)
{
int x;
cin>>x;
end+=char(‘0‘+x);//处理字符
}
int step=bfs(start,end);//bfs
cout<<step<<endl;
string res="";
while(end!=start)//因为记录的是前驱，所以要如同并查集一样
{
res+=pre[end].first;
end=pre[end].second;
}
reverse(res.begin(),res.end());//答案是倒着的，要reverse
if (step>0) cout<<res<<endl;
return 0;
}