python/TangDou/AcWing/MinimalStep/1107.md

## [$AcWing$ $1107$ 魔板](https://www.acwing.com/problem/content/1109/)


### 一、题目描述
$Rubik$ 先生在发明了风靡全球的魔方之后，又发明了它的二维版本——**魔板**。

这是一张有 $8$ 个大小相同的格子的魔板：
```c++
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$：
```c++
8 7 6 5
1 2 3 4
```

$B$：
```c++
4 1 2 3
5 8 7 6
```

$C$：
```c++
1 7 2 4
8 6 3 5
```
对于每种可能的状态，这三种基本操作都可以使用。

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

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

**输入格式**
输入仅一行，包括 $8$ 个整数，用空格分开，表示目标状态。

**输出格式**
输出文件的第一行包括一个整数，表示最短操作序列的长度。

如果操作序列的长度大于$0$，则在第二行输出字典序最小的操作序列。

**数据范围**
输入数据中的所有数字均为 $1$ 到 $8$ 之间的整数。

**输入样例**：
```cpp {.line-numbers}
2 6 8 4 5 7 3 1
```

**输出样例**：
```cpp {.line-numbers}
7
BCABCCB
```

### 二、题目解析
字符串$Hash$，宽搜

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

```cpp {.line-numbers}
// 交换上下两行
string A(string t) {
    // 1234 5678---> 8765 4321
    // 使用瞪眼大法，发现开始位置与终止位置是关于中线对称的，即0<->7,1<->6,2<->5,3<->4,这样就简单了，直接i<->7-i
    for (int i = 0; i < 4; i++) swap(t[i], t[7 - i]);
    return t;
}

// 将最右边的一列插入到最左边
string B(string t) {
    // 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;
}

// 魔板中央对的4个数作顺时针旋转
string C(string t) {
    // 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;
}
```


### 三、实现代码[带路径数组]
```cpp {.line-numbers}
#include <bits/stdc++.h>

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

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

// 将最右边的一列插入到最左边
string B(string t) {
    // 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;
}

// 魔板中央的4个数作顺时针旋转
string C(string t) {
    // 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] = {A(t), B(t), C(t)}; // 按ABC操作后产生的三种字符串
        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 (true) {
            if (ed == start) break;
            res += pre[ed].first; // 前序操作符，拼接路径，是反的,因为从最后的状态出发，找前序
            ed = pre[ed].second;  // 前序字符串
        }
        for (int i = res.size() - 1; i >= 0; i--) cout << res[i];
    }
    return 0;
}
```

### 四、实现代码 [不带路径数组]
记录路径的题，不需要记录每步骤的距离，因为，最终路径的长度就是最短距离，这样可以省一个变量数组，少维护一个。

```cpp {.line-numbers}
#include <bits/stdc++.h>

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

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

// 将最右边的一列插入到最左边
string B(string t) {
    // 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;
}

// 魔板中央的4个数作顺时针旋转
string C(string t) {
    // 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] = {A(t), B(t), C(t)}; // 按ABC操作后产生的三种字符串,按ABC顺序保证字典序最小
        for (int i = 0; i < 3; i++) {
            string x = m[i];
            if (!pre.count(x)) { // 没有走过
                q[++tt] = x;
                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();

    // 输出路径
    string res;
    // 如果操作序列的长度大于0，则在第二行输出字典序最小的操作序列。
    while (true) {
        if (ed == start) break;
        res += pre[ed].first; // 前序操作符，拼接路径，是反的,因为从最后的状态出发，找前序
        ed = pre[ed].second;  // 前序字符串
    }
    printf("%d\n", res.size());
    // 倒着输出
    for (int i = res.size() - 1; i >= 0; i--) printf("%c", res[i]);
    return 0;
}
```