宇月幸成

用户名：3350680655

访问量：15012

签　名：

题解都沉没在OJ里了..

等　　级
排　　名	401
经　　验	5075
参赛次数	1
文章发表	47
年　　龄	24
在职情况	学生
学　　校
专　　业	软件工程

　　自我简介：

刷题打发时间，没别的事做了

TA的其他文章

简洁明了的代码（C++）
浏览：602

蓝桥杯算法提高VIP-密码锁-C++超简单BFS
浏览：490

蓝桥杯算法训练VIP-FBI树C++超简单题解
浏览：323

你可能喜欢

A+B for Input-Output Practice (VII) （C语言代码）

蓝桥杯2017年第八届真题-青蛙跳杯子-C++直观BFS解法

　　作者: 宇月幸成　　　　发表时间：2020-07-15 17:55:55 浏览：229　|　评论：0　

原题链接：蓝桥杯2017年第八届真题-青蛙跳杯子

### 利用BFS枚举所有状态，注意判断出界
```cpp
#include <iostream>
#include <algorithm> 
#include <queue>
#include <map>
using namespace std;
typedef pair<string, int > PII;
string str, target;
map<string, bool > vis;
int bfs() {
	queue<PII > que;
	que.push(PII(str, 0));
	vis[str] = true;
	int sLen = str.size();
	while (que.size()) {
		PII now = que.front();que.pop();
		string ns = now.first;
		int nd = now.second;
		if (ns == target) return nd;
		for (int j = 0; j < sLen; j++) {
			if (ns[j] != '*') {
				if (j - 1 >= 0 && ns[j - 1] == '*') {
					string temp = ns;
					swap(temp[j], temp[j - 1]);
					if (!vis[temp]) que.push(PII(temp, nd + 1)), vis[temp] = true; 
				}
				if (j + 1 < sLen && ns[j + 1] == '*') {
					string temp = ns;
					swap(temp[j], temp[j + 1]);
					if (!vis[temp]) que.push(PII(temp, nd + 1)), vis[temp] = true; 
				}
				if (j - 2 >= 0 && ns[j - 2] == '*') {
					string temp = ns;
					swap(temp[j], temp[j - 2]);
					if (!vis[temp]) que.push(PII(temp, nd + 1)), vis[temp] = true; 
				}
				if (j + 2 < sLen && ns[j + 2] == '*') {
					string temp = ns;
					swap(temp[j], temp[j + 2]);
					if (!vis[temp]) que.push(PII(temp, nd + 1)), vis[temp] = true; 
				}
				if (j - 3 >= 0 && ns[j - 3] == '*') {
					string temp = ns;
					swap(temp[j], temp[j - 3]);
					if (!vis[temp]) que.push(PII(temp, nd + 1)), vis[temp] = true; 
				}
				if (j + 3 < sLen && ns[j + 3] == '*') {
					string temp = ns;
					swap(temp[j], temp[j + 3]);
					if (!vis[temp]) que.push(PII(temp, nd + 1)), vis[temp] = true; 
				}
			}
		}
	} 
	return 0;
}
int main() {
	cin >> str >> target;
	cout << bfs();
	return 0;
} 
```

0.0分

3 人评分

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

宇月幸成

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

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

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

整除问题（C语言代码）

A+B for Input-Output Practice (VII) （C语言代码）

蓝桥杯2017年第八届真题-青蛙跳杯子-C++直观BFS解法

评论区

精彩推荐

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

C语言训练-委派任务* （C语言代码）..................竟然是第一个

川哥的吩咐（C++代码）

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

【密码】（C语言代码）

上车人数（C语言代码）

Pascal三角（C语言代码）格式错误

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

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

局部变量作函数返回值的问题

宇月幸成

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

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

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

整除问题 （C语言代码）

A+B for Input-Output Practice (VII) （C语言代码）

蓝桥杯2017年第八届真题-青蛙跳杯子-C++直观BFS解法

评论区

精彩推荐

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

C语言训练-委派任务* （C语言代码）..................竟然是第一个

川哥的吩咐 （C++代码）

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

【密码】 （C语言代码）

上车人数 （C语言代码）

Pascal三角 （C语言代码）格式错误

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

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

局部变量作函数返回值的问题

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

整除问题（C语言代码）

　　评论区

川哥的吩咐（C++代码）

【密码】（C语言代码）

上车人数（C语言代码）

Pascal三角（C语言代码）格式错误