python

8.7 KiB

Raw Permalink Blame History Unescape Escape

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

`AcWing` `1107` 魔板

一、题目描述

Rubik 先生在发明了风靡全球的魔方之后，又发明了它的二维版本——魔板。

这是一张有 8 个大小相同的格子的魔板：

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：

8 7 6 5
1 2 3 4

B：

4 1 2 3
5 8 7 6

C：

1 7 2 4
8 6 3 5

对于每种可能的状态，这三种基本操作都可以使用。

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

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

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

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

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

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

输入样例：

2 6 8 4 5 7 3 1

输出样例：

7
BCABCCB

二、题目解析

字符串Hash，宽搜

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

// 交换上下两行
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;
}

三、实现代码[带路径数组]

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

四、实现代码 [不带路径数组]

记录路径的题，不需要记录每步骤的距离，因为，最终路径的长度就是最短距离，这样可以省一个变量数组，少维护一个。

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

8.7 KiB Raw Permalink Blame History Unescape Escape

AcWing 1107 魔板