AcWing 1107. 魔板（y总代码的基础上的一维转化）

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1107. 魔板（y总代码的基础上的一维转化）原题链接简单

作者：

Accepting , 2020-09-02 20:02:16 , 所有人可见 , 阅读 5824

92

7

鄙人不才，此中鄙陋甚多，望海涵！！！

话不多说，上代码，只是在y总代码的基础上将状态转化变成了一维，代码量会少一些！

C++ 代码

#include<iostream>
#include<unordered_map>
#include<queue>
#include<algorithm>

using namespace std;

unordered_map<string,int> dist;
unordered_map<string,pair<char,string>> pre;
string start,ed,res;

string move0(string t)
{
    for(int i=0;i<4;i++) swap(t[i],t[7-i]);
    return t;
}

string move1(string t)
{
    for(int i=0;i<3;i++) swap(t[3],t[i]);
    for(int i=4;i<7;i++) swap(t[i],t[i+1]);
    return t;
}

string move2(string t)
{
    swap(t[1],t[2]),swap(t[5],t[6]),swap(t[1],t[5]);
    return t;
}

void bfs()
{
    queue<string> q;
    q.push(start);
    while(q.size())
    {
        string t=q.front();
        q.pop();
        if(t==ed) return;
        string m[3];
        m[0]=move0(t);
        m[1]=move1(t);
        m[2]=move2(t);
        for(int i=0;i<3;i++)
        {
            if(!dist.count(m[i]))
            {
                q.push(m[i]);
                dist[m[i]]=dist[t]+1;
                pre[m[i]]={'A'+i,t};
            }
        }
    }
}

int main()
{
    for(int i=0;i<8;i++)
    {
        int x;
        cin>>x;
        ed+=char(x+'0');
        start+=char(i+'1');
    }
    bfs();
    cout<< dist[ed] <<endl;
    if(dist[ed])
    {
        while(ed!=start)
        {
            res+=pre[ed].first;
            ed=pre[ed].second;
        }
        reverse(res.begin(),res.end());
        cout<< res <<endl;
    }
    return 0;
}

创作不易，如果您觉得对您有帮助，就点个赞支持一下！您的赞就是我持续更新优质题解的动力！

29 评论

吃饱喝足不学习 2022-02-10 17:34

其实可以不用dist，pre可以实现判重，res的大小是操作步数。

Far_Rainbow 2022-02-21 18:56

这个优化确实可以，构造了一个单纯的bfs树

#include <bits/stdc++.h>
using namespace std;
unordered_map<string, pair<string, char>> pre; // pre存的是当前状态所对应的上一状态的状态和操作

inline string operA(string str) {
    for (int i = 0; i < 4; ++ i)    swap(str[i], str[7 - i]);
    return str;
}

inline string operB(string str) {
    for (int i = 0; i < 3; ++ i) swap(str[2 - i], str[3 - i]), swap(str[4 + i], str[5 + i]);
    return str;
}

inline string operC(string str) {
    swap(str[1], str[2]), swap(str[5], str[6]), swap(str[1], str[5]);
    return str;
}

void bfs(string start, string end) {
    queue<string> que;
    que.push(start);          // 必须从start向end搜索才能保证字典序最小
    while (!que.empty()) {
        string str = que.front();
        que.pop();
        if (str == end) return;
        string move[3];       // 记录下该状态可由三种操作所达到的新状态
        move[0] = operA(str), move[1] = operB(str), move[2] = operC(str);
        for (int i = 0; i < 3; ++ i) {                  // 遍历三种状态
            if (!pre.count(move[i])) {                  // 如果当前状态还没有被记录过
                que.push(move[i]);                      // 将当前状态入队
                pre[move[i]] = make_pair(str, 'A' + i); // 存下当前状态所对应的上一状态的状态和操作
            }
        }
    }
}

signed main() {
    int x;
    string start = "12345678", end, res;
    for (int i = 0; i < 8; ++ i) {
        scanf("%d", &x);
        end += char(x + '0');
    }

    bfs(start, end);
    while (end != start) {           // 从最终状态向起始状态回溯
        res = pre[end].second + res; // 注意要把前一个操作放在输出序的前面
        end = pre[end].first;
    }
    if (res.length() == 0)  printf("0");
    else    printf("%d\n%s", res.length(), res.c_str());
    return 0;
}

包子云 2022-03-04 14:13 回复了 Far_Rainbow 的评论

666

包子云 2022-03-04 14:14 回复了包子云的评论

又简化了，还有注释，可惜评论区没有点赞不然我按爆它

南笙离梦 2022-08-01 10:33 回复了 Far_Rainbow 的评论

请问为什么不reverse也可以过

理想主义者 2022-08-02 14:14 回复了南笙离梦的评论

拼接那里是拼接在前面的

南笙离梦 2022-08-02 18:09 回复了理想主义者的评论

感谢

Spectre_9 5个月前

不会实现字典序

xianyelei 2个月前

谢谢大佬，突然感觉这题能写了

Aress灬柠檬 10个月前

orz orz orz orz
tql%%% tql%%%

污秽之翼 2023-11-03 18:29

void bfs()
{
    queue<string> q;
    q.push(start);
    while(q.size())
    {
        string t=q.front();
        q.pop();
        if(t==ed) return;
        string m[3];
        m[0]=move0(t);
        m[1]=move1(t);
        m[2]=move2(t);
        for(int i=0;i<3;i++)
        {
            if(!dist.count(m[i]))
            {
                q.push(m[i]);
                dist[m[i]]=dist[t]+1;
                pre[m[i]]={'A'+i,t};
                if(m[i] == ed) return; // 可选
            }
        }
    }
}