acwing1107. 魔板

题目

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

这是一张有 8 个大小相同的格子的魔板：

1 2 3 4
8 7 6 5
我们知道魔板的每一个方格都有一种颜色。

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

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

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

这里提供三种基本操作，分别用大写字母 A，B，C 来表示（可以通过这些操作改变魔板的状态）：

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
对于每种可能的状态，这三种基本操作都可以使用。

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

注意：数据保证一定有解。

题解

利用哈希表，将每个路径的步数都存下来。由于这里要给出步骤，可以从有序走到无序，这样输出路径时只需要从end到start之间的路径即可。

注意：题目是从用最少的基本操作完成基本状态到特殊状态的转换，所以最后需要倒序输出。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_map>
#include<queue>

using namespace std;
unordered_map<string,pair<char,string>>pre;
unordered_map<string,int>dist;

char g[2][4];
void set(string state){
    for(int i=0;i<4;i++)g[0][i]=state[i];
    for(int i=7,j=0;j<4;i--,j++)g[1][j]=state[i];
}

string get(){
    string ans="";
    for(int i=0;i<4;i++)ans+=g[0][i];
    for(int i=3;i>=0;i--)ans+=g[1][i];
    return ans;
}

string move0(string state){
    set(state);
    for(int i=0;i<4;i++)swap(g[0][i],g[1][i]);
    return get();
}
string move1(string state){
    set(state);
    char t0=g[0][3],t1=g[1][3];
    for(int i=3;i>=0;i--){
        g[0][i]=g[0][i-1];
        g[1][i]=g[1][i-1];
    }
    
    g[0][0]=t0;
    g[1][0]=t1;
    return get();
}

string move2(string state){
    set(state);
    int t=g[0][1];
    g[0][1]=g[1][1];
    g[1][1]=g[1][2];
    g[1][2]=g[0][2];
    g[0][2]=t;
    return get();
    
}

int bfs(string start,string end){
    if(start==end)return 0;
    queue<string>q;
    q.push(start);
    dist[start]=0;
    while(!q.empty()){
        auto t=q.front();
        q.pop();
        string m[3];
        m[0]=move0(t);
        m[1]=move1(t);
        m[2]=move2(t);
        for(int i=0;i<3;i++){
            if(!dist.count(m[i])){
                dist[m[i]]=dist[t]+1;
                pre[m[i]]={'A'+i,t};
                q.push(m[i]);
                if(m[i]==end)return dist[end];
            }
        }
    }
    return -1;
}

int main(){
    string start,end;
    start="12345678";
    for(int i=1;i<=8;i++){
        char x;
        cin>>x;
        end+=x;
    }
    int step=bfs(start,end);
    cout<<step<<endl;
    
    string ans="";
    while(end!=start)
    {
        ans+=pre[end].first;
        end=pre[end].second;
    }
    reverse(ans.begin(),ans.end());
    
    if(step)cout<<ans<<endl;
    return 0;
}