魔板

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1415 字
状态串 BFS 按 ABC 顺序扩展取字典序
一本通
例
正文

// 原题：https://oj.yecheng.tv/p/T1449
// 题意：魔板 8 个格子按顺时针编号，三种操作 A（上下两行交换）、B（最右列插到最左）、C（中间四格顺时针转），求从基本状态到目标状态的最短操作序列（并列时取字典序最早）。
// 思路：BFS 打表。
// 1. 状态用 8 个字符的串表示，从基本状态 "12345678" 出发。
// 2. 三种操作按 A、B、C 的顺序扩展，BFS 首次到达某状态时得到的就是最短且字典序最早的路径。
// 3. 状态数只有 8! = 40320，直接广搜打表即可。
// 复杂度：O(8!) 时间 / O(8!) 空间
// 易错点：状态的排列顺序是「上行从左到右，再下行从右到左」，搞反了操作函数就全错。
// 易错点：要按 A、B、C 的顺序扩展才能得到字典序最早的解，改成 C、B、A 会得到另一个等长解。
#include <bits/stdc++.h>
using namespace std;
string moveA(string s){
    reverse(s.begin(), s.end());
    return s;
}
string moveB(string s){
    return string({s[3], s[0], s[1], s[2], s[5], s[6], s[7], s[4]});
}
string moveC(string s){
    return string({s[0], s[6], s[1], s[3], s[4], s[2], s[5], s[7]});
}
int main(){
    string target;
    for(int i = 0; i < 8; i++){
        int x;
        if(!(cin >> x)) return 0;
        target += char('0' + x);
    }
    map<string, string> dis;
    queue<string> q;
    dis["12345678"] = "";
    q.push("12345678");
    while(!q.empty()){
        string s = q.front();
        q.pop();
        string nxt[3] = {moveA(s), moveB(s), moveC(s)};
        char name[3] = {'A', 'B', 'C'};
        for(int k = 0; k < 3; k++){
            if(dis.count(nxt[k])) continue;
            dis[nxt[k]] = dis[s] + name[k];
            q.push(nxt[k]);
        }
    }
    string ans = dis[target];
    cout << ans.size();
    if(!ans.empty()) cout << " " << ans;
    cout << "\n";
    return 0;
}
魔板

正文

一本通·提高篇的其它内容
