---
title: "魔板"
created: 2025-11-28
tags:
  - 算法
---

# 魔板

## 题目 [魔板](https://www.acwing.com/problem/content/1109/)

![[image-f750d392.png]]

## 思路分析

问题主要麻烦在 这几种操作该如何表示出来 并且哈希表中怎么存储这个2\*4转变来的一维string 如何转变

如果这个考虑清楚了 那么本质还是从一个状态到另一个状态的最小步数 bfs问题

代码就不写了 一般不会考这么复杂 要真考这么复杂也多半是放弃 没时间写的

## 代码实现

```cpp
#include <cstring> // 引入cstring头文件，用于字符串操作
#include <iostream> // 引入iostream头文件，用于输入输出流操作
#include <algorithm> // 引入algorithm头文件，用于算法操作
#include <unordered_map> // 引入unordered_map头文件，用于哈希映射操作
#include <queue> // 引入queue头文件，用于队列操作

using namespace std;

char g[2][4]; // 定义一个二维字符数组g，表示状态
unordered_map<string, pair<char, string>> pre; // 定义一个哈希映射pre，存储状态的前驱和移动方式
unordered_map<string, int> dist; // 定义一个哈希映射dist，存储状态的最短距离

void set(string state)
{
    for (int i = 0; i < 4; i ++ ) g[0][i] = state[i]; // 将状态的前四个字符赋值给g的第一行
    for (int i = 7, j = 0; j < 4; i --, j ++ ) g[1][j] = state[i]; // 将状态的后四个字符赋值给g的第二行
}

string get()
{
    string res;
    for (int i = 0; i < 4; i ++ ) res += g[0][i]; // 将g的第一行字符拼接成字符串
    for (int i = 3; i >= 0; i -- ) res += g[1][i]; // 将g的第二行字符逆序拼接成字符串
    return res;
}

string move0(string state)
{
    set(state);
    for (int i = 0; i < 4; i ++ ) swap(g[0][i], g[1][i]); // 交换g的第一行和第二行的字符
    return get();
}

string move1(string state)
{
    set(state);
    int v0 = g[0][3], v1 = g[1][3]; // 保存g的第一行和第二行的最后一个字符
    for (int i = 3; i > 0; i -- )
    {
        g[0][i] = g[0][i - 1]; // 将g的第一行字符向右移动一位
        g[1][i] = g[1][i - 1]; // 将g的第二行字符向右移动一位
    }
    g[0][0] = v0, g[1][0] = v1; // 将保存的字符放到g的第一行和第二行的第一个位置
    return get();
}

string move2(string state)
{
    set(state);
    int v = g[0][1]; // 保存g的第一行的第二个字符
    g[0][1] = g[1][1]; // 将g的第二行的第二个字符赋值给g的第一行的第二个字符
    g[1][1] = g[1][2]; // 将g的第二行的第三个字符赋值给g的第二行的第二个字符
    g[1][2] = g[0][2]; // 将g的第一行的第三个字符赋值给g的第二行的第三个字符
    g[0][2] = v; // 将保存的字符放到g的第一行的第三个位置
    return get();
}

int bfs(string start, string end)
{
    if (start == end) return 0; // 如果起始状态和目标状态相同，返回0

    queue<string> q; // 定义一个队列q，用于广度优先搜索
    q.push(start); // 将起始状态加入队列
    dist[start] = 0; // 起始状态的最短距离为0

    while (!q.empty())
    {
        auto t = q.front(); // 取出队列的第一个元素
        q.pop(); // 弹出队列的第一个元素

        string m[3]; // 定义一个字符串数组m，存储移动后的状态
        m[0] = move0(t); // 将t进行move0操作得到移动后的状态m[0]
        m[1] = move1(t); // 将t进行move1操作得到移动后的状态m[1]
        m[2] = move2(t); // 将t进行move2操作得到移动后的状态m[2]

        for (int i = 0; i < 3; i ++ )
            if (!dist.count(m[i])) // 如果状态m[i]不在dist中
            {
                dist[m[i]] = dist[t] + 1; // 更新状态m[i]的最短距离
                pre[m[i]] = {'A' + i, t}; // 更新状态m[i]的前驱和移动方式
                q.push(m[i]); // 将状态m[i]加入队列
                if (m[i] == end) return dist[end]; // 如果状态m[i]等于目标状态，返回最短距离
            }
    }

    return -1; // 如果无法到达目标状态，返回-1
}

int main()
{
    int x;
    string start, end;
    for (int i = 0; i < 8; i ++ )
    {
        cin >> x; // 输入一个整数x
        end += char(x + '0'); // 将x转换为字符并添加到end字符串末尾
    }

    for (int i = 1; i <= 8; i ++ ) start += char('0' + i); // 初始化start字符串为"12345678"

    int step = bfs(start, end); // 进行广度优先搜索，得到最短步数

    cout << step << endl; // 输出最短步数

    // 有pre反推出变换序列
    string res;
    while (end != start)
    {
        res += pre[end].first; // 将当前状态的移动方式添加到res字符串末尾
        end = pre[end].second; // 更新当前状态为前驱状态
    }

    reverse(res.begin(), res.end()); // 将res字符串逆序

    if (step > 0) cout << res << endl; // 如果存在最短路径，输出移动方式

    return 0;
}

作者：Hasity
链接：https://www.acwing.com/solution/content/233056/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
```

## 同类题型

## 视频讲解

---
⬅️ [[八数码|八数码]] 🏠 [[00-冲刺国赛]] ➡️ [[树与图的存储|树与图的存储]]