yxy

用户名：dotcpp0787179

访问量：445

签　名：

竞赛交流论坛： blog.qzcy2.top 欢迎来撩！

等　　级
排　　名	1030
经　　验	3291
参赛次数	1
文章发表	23
年　　龄	1
在职情况	学生
学　　校	内江师范学院
专　　业	纳西妲系

　　自我简介：

我不会

TA的其他文章

[食物链] 并查集 - NOI2001 提高组
浏览：22

[金银岛]自定义排序优先'均权'最大--我看题解都太复杂辣
浏览：48

杀到这九天十地无人敢称尊,直到身边再无一人能陪我征战,叶天帝不过如此
浏览：23

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

多源bfs-[信息学奥赛一本通T1449-魔板]-洛谷绿

　　作者: yxy　　　　发表时间：2024-09-26 19:36:56 浏览：24　|　评论：0　

原题链接：信息学奥赛一本通T1449-魔板

# 多源bfs + 字典序输出
## 关于我两节课就ac了这一个题这件伤心事
###### 警示后人！为什么只过了两个数据点：
#### 本题输出样例有误（浪费我很多时间）
原输出样例 答案+空格+答案
##### 但实际应该是 答案 + 提行 + 答案 ！！

吐槽完了 接下来讲解细节：
## 难点在于 存贮每一次状态转换后的字符串 和 要求的字典序输出；
三种状态转换可以无脑的用中间变量赋值 只需要花一点时间就可以解决
###### **1.贮存每一次状态转换之后的字符串：
可以使用map工具 如果是c++11的话 推荐使用unordered_map 因为他底层是哈希表 速度更快；
使用unordered_map 可以使得每一次贮存新字符串的同时 保证他不是出现过的 有效避免了时间浪费以及计数准确
##### **2.字典序输出：
字典序 顾名思义 就是按照字典上面的字母排序A--Z 这个简单 我们根据bfs处理数据的特点 最优的方法总是第一个找到 所以我们只需要按照从A--C的状态转换方式就可以完美解决了！

###### Code：
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <queue>
#define int long long
 
using namespace std;
char g[2][4];
unordered_map<string , pair<char , string> > m;  //记录当前的字符串的同时 记录他的来源字符串以及 状态转移的方式A，B，C；
unordered_map<string , int> dist; //记录操作次数
queue<string> q;
 
void set(string state)  //将字符串转移为2*4的字符数组
{   
    for (int i = 0 ; i < 4 ; i ++ ) g[0][i] = state[i];
    for (int i = 3 , j = 4 ; i >= 0 ; i -- , j ++) g[1][i] = state[j];
 
    return ;
}
 
string get() //将2 * 4 的字符数组转换为字符串
{
    string res;
    for (int i = 0 ; i < 4 ; i ++ ) res += g[0][i];
    for (int i = 3 ; i >= 0 ; i -- ) res += g[1][i];
 
    return res;
}
 
string move0(string temp)  //第一个状态转移方式
{
    set(temp);
 
    for (int i = 0 ; i < 4 ; i ++ ) swap(g[0][i] , g[1][i]);
 
    return get();
}
 
string move1(string temp)  //第二个状态转移方式
{
    set(temp);
 
    char ch = g[0][3];
    g[0][3] = g[0][2];
    g[0][2] = g[0][1];
    g[0][1] = g[0][0];
    g[0][0] = ch;
 
    ch = g[1][3];
    g[1][3] = g[1][2];
    g[1][2] = g[1][1];
    g[1][1] = g[1][0];
    g[1][0] = ch;
 
    return get();
}
 
string move2(string temp)  //第三个状态转移方式
{
    set(temp);
 
    char s_temp = g[0][1];
    g[0][1] = g[1][1];
    g[1][1] = g[1][2];
    g[1][2] = g[0][2];
    g[0][2] = s_temp;
 
    return get();
}
 
void bfs(string start , string end)
{
    if (start == end) return ;
 
    q.push(start);
    dist[start] = 0;  //初始的操作次数为0；
 
    while (!q.empty())
    {
        auto t = q.front();
        q.pop();
         
        // cout << t << endl;
 
        string sb[3];    //记录同一个字符串分别操作三次以后的状态
 
        sb[0] = move0(t);
        sb[1] = move1(t);
        sb[2] = move2(t);
 
        // for (int i = 0 ; i < 3 ; i ++ ) cout << "->" <<sb[i] << endl;
 
        // break;
        for (int i = 0 ; i < 3 ; i ++ )
        {
            if (dist.count(sb[i]) == 0) //如果没有出现过 就进队 存起来
            {
                dist[sb[i]] = dist[t] + 1;  //操作次数加一
                m[sb[i]] = {char(i + 'A') , t};	 //记录来源以及操作方式
                if (sb[i] == end) return  ; //如果以及得到目标字符串 就直接退出
                q.push(sb[i]);
            }
        }
    }
}
 
signed main()
{
    // ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0);
    string start , end;
    int temp;
 
    for (int i = 0 ; i < 8 ; i ++ )
    {
        cin >> temp;
        end += char(temp + '0');  //用ascall码存进字符
    }
 
    for (int i = 0 ; i < 8 ; i ++ ) start += char(i + '1');  //初始字符串
 
    bfs(start , end);
 
    cout << dist[end] << endl; //输出最优操作次数
    string ans;
    while (end != start) //输出操作步骤
    {
        ans += m[end].first;
        end = m[end].second;
    }
 
    reverse(ans.begin() , ans.end());  //因为我们是倒序存的 需要反转答案
 
    if (ans.size()) cout << ans << endl; //根据题目要求 要是 初始字符串已经是目标字符串 那么我们不用输出 也就是 操作次数为0；
 
    return 0;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

yxy

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

母牛的故事（C语言代码）

【简单计算】（C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

多源bfs-[信息学奥赛一本通T1449-魔板]-洛谷绿

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

关于float，double变量的几点说明

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C二级辅导-等差数列（C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

判定字符位置（C++代码）

纪念品分组（C++代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

蛇行矩阵（C语言代码）

yxy

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

母牛的故事 （C语言代码）

【简单计算】 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

多源bfs-[信息学奥赛一本通T1449-魔板]-洛谷绿

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

关于float，double变量的几点说明

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C二级辅导-等差数列 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

判定字符位置 （C++代码）

纪念品分组 （C++代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

蛇行矩阵 （C语言代码）

母牛的故事（C语言代码）

【简单计算】（C语言代码）

　　评论区

C二级辅导-等差数列（C语言代码）

判定字符位置（C++代码）

纪念品分组（C++代码）

蛇行矩阵（C语言代码）