莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 跟八数码一样都是求最小步数，需要状态转换
2. dist需要记录到达该状态需要的步数，pre需要记录到达该状态的操作和上一步状态
3. 枚举三种状态，如果之前没有出现过，就更新dist和pre
4. 如果到达目标状态，就直接返回，否则，放入队列

可参考： 八数码

#include<bits/stdc++.h>

using namespace std;

char g[2][4];
unordered_map<string,int> dist;
unordered_map<string,pair<char,string>> pre;

//将一行变成两行
void set1(string state)
{
    for(int i=0;i<4;i++) g[0][i]=state[i];
    for(int i=3,j=4;i>=0;i--,j++) g[1][i]=state[j]; 
}

//将两行变成一行
string get()
{
    string res;
    for(int i=0;i<4;i++) res+=g[0][i];
    for(int i=3;i>=0;i--) res+=g[1][i];
    return res;
}

//交换上下两行
string moveA(string state)
{
    set1(state);
    for(int i=0;i<4;i++) swap(g[0][i],g[1][i]);
    return get();
}

//将最右边的一列插入到最左边
string moveB(string state)
{
    set1(state);
    char v0=g[0][3],v1=g[1][3];
    for(int i=3;i>0;i--)
        for(int j=0;j<2;j++)
            g[j][i]=g[j][i-1];
    g[0][0]=v0,g[1][0]=v1;
    return get();
}

//魔板中央对的4个数作顺时针旋转
string moveC(string state)
{
    set1(state);
    char v=g[0][1];
    g[0][1]=g[1][1];
    g[1][1]=g[1][2];
    g[1][2]=g[0][2];
    g[0][2]=v;
    return get();
}

void bfs(string start,string end)
{
    if(start==end) return;

    //将初始状态放入队列
    queue<string> q;
    q.push(start);

    //表示初始状态已经被记录了，且步数为0
    dist[start]=0;

    while(q.size())
    {
        //取出队头
        auto t=q.front();
        q.pop();

        //由队头转换而来的三种状态
        string str[3];
        str[0]=moveA(t);
        str[1]=moveB(t);
        str[2]=moveC(t);

        //枚举三种状态
        for(int i=0;i<3;i++)
            if(!dist.count(str[i]))
            {
                //更新步数
                dist[str[i]]=dist[t]+1;

                //记录操作和上一步状态
                pre[str[i]]={char(i+'A'),t};

                //到达目标状态
                if(str[i]==end) return;

                //符合条件，放入队列
                q.push(str[i]);
            }
    }
}

int main()
{
    string start="12345678",end;
    for(int i=0;i<8;i++)
    {
        char c;
        cin>>c;
        end+=c;
    }

    bfs(start,end);

    cout<<dist[end]<<endl;

    //推路径
    string res;
    while(start!=end)
    {
        res+=pre[end].first;
        end=pre[end].second;
    }

    //因为是从后往前推,所以要反转一下
    reverse(res.begin(),res.end());

    if(res.size()) cout<<res<<endl;

    return 0;
}