最小步数模型 AcWing 1107. 魔板

妖狐艹你老母 2024-04-08 13:32 70阅读 0赞

## 最小步数模型 AcWing 1107. 魔板 ##

### 原题链接 ###

[AcWing 1107. 魔板][AcWing 1107.]

### 算法标签 ###

BFS

### 思路 ###

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

即求步数 采用BFS  
原因  
![在这里插入图片描述][0475e42c020f40d0836c34da447929d2.png]

##### 对于状态存储 #####

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

![在这里插入图片描述][60580dc951bc4a65904ac0b9e119d90b.png]

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

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

![在这里插入图片描述][d2b1fa467ab24ab98c45e01c1f3fff80.png]

### 代码 ###

#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;
    }

参考文献  
[AcWing 1107. 魔板（算法提高课）y总视频][AcWing 1107. _y]  
[AcWing 1107. 魔板（算法提高课）y总代码][AcWing 1107. _y]

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 1107.]: https://www.acwing.com/problem/content/1109/
[0475e42c020f40d0836c34da447929d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/b24aa47784084a109c65bdddc1002dcd.png
[60580dc951bc4a65904ac0b9e119d90b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/1753dcd2886244cc80059eaace79edc2.png
[d2b1fa467ab24ab98c45e01c1f3fff80.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/fb7e43af6b1f42fb8dc629227a69dad5.png
[AcWing 1107. _y]: https://www.acwing.com/video/452/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/9e36b12e74a342df94b6d9f8716e2fb7.png