最小步数模型 AcWing 1107. 魔板-蒲公英云

最小步数模型 AcWing 1107. 魔板

原题链接

AcWing 1107. 魔板

算法标签

BFS

思路

如何求最少的基本操作完成基本状态到特殊状态的转换

即求步数采用BFS
原因
在这里插入图片描述

对于状态存储

采用康拓扩展
采用hash法存储（C++ 采用map C++11 建议采用unorderer_map存储）

在这里插入图片描述

如何输出字典序最小的操作序列

若前缀序列一致，则按照先A再B再C扩展可以得到最小的操作序列

在这里插入图片描述

代码

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>=b;--i)
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1005;
char g[2][4];
// 存储从转移至该状态的上一个状态
// 同时存储操作选择为 A or B or C
unordered_map<string, pair<char, string>> pre;
// 存储每个状态的步数
unordered_map<string, int> d;
inline int rd(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
// 将当前字符串放入g中,对于所有move操作对g操作
void set0(string s){
    rep(i, 0, 4){
        g[0][i]=s[i];
    }
    for(int i=7, j=0; j<4; --i, ++j){
        g[1][j]=s[i];
    }
}
// 将g放入当前字符串中,对于所有move操作返回g操作后的s字符串
string get0(){
    string s;
    rep(i, 0, 4){
        s+=g[0][i];
    }
    Rep(i, 3, 0){
        s+=g[1][i];
    }
    return s;
}
string move0(string s){
    set0(s);
    rep(i, 0, 4){
        swap(g[0][i], g[1][i]);
    }
    return get0();
}
string move1(string s){
    set0(s);
    int v0=g[0][3], v1=g[1][3];
    Rep(i, 3, 0){
        g[0][i]=g[0][i-1];
        g[1][i]=g[1][i-1];
    }
    g[0][0]=v0, g[1][0]=v1;
    return get0();
}
string move2(string s){
    set0(s);
    int 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 get0();
}
int bfs(string st, string end){
    if(st==end){
        return 0;
    }
    queue<string> q;
    q.push(st);
    d[st]=0;
    while(!q.empty()){
        string t=q.front();
        q.pop();
        string m[3];
        m[0]=move0(t);
        m[1]=move1(t);
        m[2]=move2(t);
        rep(i, 0, 3){
            if(!d.count(m[i])){
                d[m[i]]=d[t]+1;
                pre[m[i]]={'A'+i, t};
                q.push(m[i]);
                if(m[i]==end){
                    return d[end];
                }
            }
        }
    }
    return -1;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int x;
    string st, end;
    rep(i, 0, 8){
        x=rd();
        end+=x+'0';
    }
    rep(i, 1, 9){
        st+=i+'0';
    }
    int cnt=bfs(st, end);
    printf("%lld\n", cnt);
    string ans;
    while(end!=st){
        ans+=pre[end].x;
        end=pre[end].y;
    }
    reverse(ans.begin(), ans.end());
    if(cnt){
        printf("%s", ans.c_str());
    }
    return 0;
}