AcWing 1107 魔板

字符串\(Hash\)，宽搜

三种变化需要点心思，不过还好，用心模拟一下。

#include 

using namespace std;
const int N = 1e5 + 10;                        //开小了会WA
unordered_map dist;               //记录某个字符串，走没有走过，如果走过，那么是走了几步到达的
unordered_map> pre; //记录某个字符串，它的前序操作符是ABC中的哪一个，它的前序字符串是什么
string start = "12345678";                     //起始态
string ed;                                     //目标态,需要输入进来
string q[N];                                   //队列

string A(string t) {
    // 交换上下两行；
    /* 1 2 3 4        8 7 6 5
                ==>
       8 7 6 5        1 2 3 4
    */
    // 1234 5678---> 8765 4321
    for (int i = 0; i < 4; i++) swap(t[i], t[7 - i]);
    return t;
}

string B(string t) {
    //将最右边的一列插入到最左边
    /*
    1 2 3 4     4 1 2 3
            ==>
    8 7 6 5     5 8 7 6
    */
    // 1234 5678 ---> 4123 6785
    // 4向上冒泡,5向后冒泡
    for (int i = 3; i > 0; i--) swap(t[i], t[i - 1]);
    for (int i = 4; i < 7; i++) swap(t[i], t[i + 1]);
    return t;
}

string C(string t) {
    //魔板中央对的4个数作顺时针旋转
    /*
      1 2 3 4     1 7 2 4
              ==>
      8 7 6 5     8 6 3 5
    */
    // 1234 5678 ---> 1724 5368
    /*
    swap(t[1], t[2])   1234 5678  -> 1324 5678  把第一个不匹配的数字放到合适位置上
    swap(t[5], t[6])   1324 5678  -> 1324 5768  把第二个不匹配的数字放到合适位置上
    swap(t[1], t[5])   1324 5768  -> 1724 5368  回到头，再把第一个不匹配的数字放到合适位置上
    */
    swap(t[1], t[2]), swap(t[5], t[6]), swap(t[1], t[5]);
    return t;
}

void bfs() {
    int hh = 0, tt = -1;
    q[++tt] = start;
    while (hh <= tt) {
        string t = q[hh++];
        if (t == ed) return; //找到即停止

        string m[3];
        m[0] = A(t);
        m[1] = B(t);
        m[2] = C(t);
        for (int i = 0; i < 3; i++) {
            string x = m[i];
            if (!dist.count(x)) { //是不是走过？
                q[++tt] = x;
                dist[x] = dist[t] + 1;
                pre[x] = {'A' + i, t}; // x的前序：t,是通过'A'+i方式转化过来的
            }
        }
    }
}

int main() {
    char x;
    for (int i = 0; i < 8; i++) cin >> x, ed += x;

    //广搜
    bfs();

    //输出距离
    cout << dist[ed] << endl;

    //输出路径
    string res;
    //如果操作序列的长度大于0，则在第二行输出字典序最小的操作序列。
    if (dist[ed]) {
        while (ed != start) {
            res += pre[ed].first; //前序操作符，拼接路径，是反的,因为从最后的状态出发，找前序
            ed = pre[ed].second;  //前序字符串
        }
        reverse(res.begin(), res.end()); //翻过来
        cout << res << endl;
    }
    return 0;
}