计科余定成

用户名：dotcpp0598358

访问量：15962

签　名：

孙蕾，我好喜欢你啊，为了你我要把键盘敲烂!!!

等　　级
排　　名	41
经　　验	13072
参赛次数	1
文章发表	69
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

我是余定成

TA的其他文章

图的遍历-DFS
浏览：56

求具有abcd=(ab+cd)2性质的四位数
浏览：74

[NOIP2004]合并果子
浏览：90

你可能喜欢

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

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

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

魔板（BFS+map去重）

　　作者: 计科余定成　　　　发表时间：2023-02-14 10:25:25 浏览：85　|　评论：0　

原题链接：魔板

解题思路：BFS+map去重，用map存储操作序列。
BFS算法通过对当前状态进行操作，并将所有可能的下一状态加入队列，不断扩展状态空间直到找到目标状态。哈希表用于存储操作序列，避免重复搜索相同的状态。

参考代码：
```cpp
#include<bits/stdc++.h>
using namespace std;

// 定义两个变量s和f，代表起点状态和终点状态，其值由输入读入
string s, f;

// 操作A函数，将输入状态x按照操作A的规则进行变换
string A(string x) {
	string s = x;
	for (int i = 0; i < 4; i++) {
		swap(s[i], x[7 - i]);
		swap(s[i + 4], x[3 - i]);
	}
	return s;
}

// 操作B函数，将输入状态x按照操作B的规则进行变换
string B(string x) {
	string s = x;
	s[0] = x[3], s[1] = x[0];
	s[2] = x[1], s[3] = x[2];
	s[4] = x[5], s[5] = x[6];
	s[6] = x[7], s[7] = x[4];
	return s;
}

// 操作C函数，将输入状态x按照操作C的规则进行变换
string C(string x) {
	string s = x;
	s[1] = x[6], s[2] = x[1];
	s[5] = x[2], s[6] = x[5];
	return s;
}

// 广搜函数，使用map进行去重，记录操作序列
void bfs() {
	unordered_map<string, string>mp; // 哈希表，用于存储操作序列
	queue<string>q; // 队列，用于存储待搜索状态
	q.push(s); // 将初始状态入队
	while (!q.empty()) { // 只要队列不为空，就继续搜索
		string now = q.front(); // 取出队首元素
		q.pop(); // 将队首元素出队
		if (now == f) { // 当达到终点状态，输出操作序列
			cout << mp[now] << endl;
			return; // 搜索结束
		}
		string ts; // 操作后的状态
		// 按照题目要求，A、B、C操作依次搜索，保证字典序最小
		for (int i = 0; i < 3; i++) { // 依次搜索ABC操作，保证字典序最小
			switch (i) {
				case 0: // A操作
					ts = A(now); // 对当前状态进行A操作
					if (!mp.count(ts)) { // 如果操作后的状态不在哈希表中
						q.push(ts); // 将操作后的状态入队
						mp[ts] = mp[now] + 'A'; // 更新哈希表，存储操作序列
					}
					break;
				case 1: // B操作
					ts = B(now); // 对当前状态进行B操作
					if (!mp.count(ts)) { // 如果操作后的状态不在哈希表中
						q.push(ts); // 将操作后的状态入队
						mp[ts] = mp[now] + 'B';// 更新哈希表，存储操作序列
					}
					break;
				case 2://C操作
					ts = C(now); // 对当前状态进行B操作
					if (!mp.count(ts)) { // 如果操作后的状态不在哈希表中
						q.push(ts); // 将操作后的状态入队
						mp[ts] = mp[now] + 'C';// 更新哈希表，存储操作序列
					}
					break;
			}
		}
	}
}

int main() {
	while (cin >> s >> f) {
		bfs();
	}
	return 0;
}
```

0.0分

3 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

计科余定成

TA的其他文章

你可能喜欢

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

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

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

产生数（C++代码）（大数乘法也是可以避免的么hhhh）

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

魔板（BFS+map去重）

评论区

精彩推荐

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

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

C语言训练-大、小写问题（C语言代码）

C语言训练-大、小写问题（C语言代码）

三角形（C++代码）递归（存在大量重复计算，容易出现时间超限）

WU-C语言程序设计教程（第三版）课后习题12.1 （C++代码）

printf基础练习2 （C语言代码）

小九九（C语言描述,不看要求真坑爹）

C二级辅导-同因查找（C语言代码）

妹子杀手的故事（C语言代码）

计科余定成

TA的其他文章

你可能喜欢

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

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

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

产生数 （C++代码）（大数乘法也是可以避免的么hhhh）

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

魔板（BFS+map去重）

评论区

精彩推荐

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

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

C语言训练-大、小写问题 （C语言代码）

C语言训练-大、小写问题 （C语言代码）

三角形 （C++代码）递归（存在大量重复计算，容易出现时间超限）

WU-C语言程序设计教程（第三版）课后习题12.1 （C++代码）

printf基础练习2 （C语言代码）

小九九 （C语言描述,不看要求真坑爹）

C二级辅导-同因查找 （C语言代码）

妹子杀手的故事 （C语言代码）

产生数（C++代码）（大数乘法也是可以避免的么hhhh）

　　评论区

C语言训练-大、小写问题（C语言代码）

C语言训练-大、小写问题（C语言代码）

三角形（C++代码）递归（存在大量重复计算，容易出现时间超限）

小九九（C语言描述,不看要求真坑爹）

C二级辅导-同因查找（C语言代码）

妹子杀手的故事（C语言代码）