林灵艺

用户名：runningboy001

访问量：1648

签　名：

向大佬们学习

等　　级
排　　名	625
经　　验	4115
参赛次数	26
文章发表	2
年　　龄	0
在职情况	学生
学　　校	怀化学院
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法训练VIP-青蛙跳杯子看完包会的（BFS）
浏览：428

蓝桥杯VIP算法训练-数字三角形-看完秒懂的（动态规划）
浏览：672

你可能喜欢

蓝桥杯算法训练VIP-青蛙跳杯子看完包会的（BFS）

　　作者: 林灵艺　　　　发表时间：2022-03-12 11:09:35 浏览：428　|　评论：0　

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

**1.看题找算法**:典型BFS题目
**2思路分析：**输入时即输入2个字符串，我们要通过变换让2个字符串相等.即找到空的杯子，以空杯子为原点bfs，交换空杯子与青蛙不断生成新 的字符串，同时要注意保存步数，所以我们可以建立一个结构体.

**2.注意事项:**要注意去重，采用map容器来判断我们交换过后的字符串是否出现过；

**3.参考代码:**

# include<iostream>
	# include<queue>
	# include<map>
	using namespace std;
	map<string,int>p;
	struct ss//建立结构体
	{
   	//x：空杯子所在位置
   	int x,step;//step：步数（原字符串到此字符串需要变换的次数）
   	string path;
   	ss(int xx,int stepp,string pathh)
	   {
	   	x=xx,step=stepp,path=pathh;
	    }ss(){};
	};//标准结构体的建立
	int bfs(string a,string b)//开始BFS
	{
	   int i,j;
	   int dx[]={-3,-2,-1,1,2,3};//变化的方向正负表示，左右值表示几步
	   queue<ss>q;
	   int k=a.find('*');//找到空杯子的位置
	   q.push({k,0,a});
	   while(q.size())//标准BFS查找
   	{
		   ss s1=q.front();
		   q.pop();
		   if(s1.path==b)//判断现在这个字符串是否是题目所要求的那个
		  {
			  return s1.step;//如果是直接返回步数就行
		  }
		string st=s1.path;//如果不是则继续BFS
		int k1=st.find('*');//找到空杯子的位置
		for(i=0;i<=5;i++)
		{
			int xx=k1+dx[i];
			if(xx>=0&&xx<st.length())
			{
				swap(st[k1],st[xx]);
				ss s2={xx,s1.step+1,st};
				p[st]++;//查重
				if(p[st]==1)//如果该字符串之前没出现过那么可以插入容器
				{
					q.push(s2);
				}
				swap(st[k1],st[xx]);//复原现场
			}
		}
	}
	}
	   int main()
	  {
	     string a,b;
	    cin>>a>>b;
	    cout<<bfs(a,b)<<endl;
	    return 0;
       }

0.0分

8 人评分

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

林灵艺

TA的其他文章

你可能喜欢

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

C二级辅导-阶乘数列（C++代码）

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

C语言训练-角谷猜想（C++代码）（3N+1问题）

C语言考试练习题_一元二次方程（C语言代码）

蓝桥杯算法训练VIP-青蛙跳杯子看完包会的（BFS）

评论区

精彩推荐

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

WU-输入输出格式练习（C++代码）

三角形（C++代码）递推

关于C语言变量位置的问题

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

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

1162答案错误，为什么

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

C语言训练-列出最简真分数序列* （C语言代码）

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

林灵艺

TA的其他文章

你可能喜欢

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

C二级辅导-阶乘数列 （C++代码）

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

C语言训练-角谷猜想 （C++代码）（3N+1问题）

C语言考试练习题_一元二次方程 （C语言代码）

蓝桥杯算法训练VIP-青蛙跳杯子看完包会的（BFS）

评论区

精彩推荐

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

WU-输入输出格式练习 （C++代码）

三角形 （C++代码）递推

关于C语言变量位置的问题

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

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

1162答案错误，为什么

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

C语言训练-列出最简真分数序列* （C语言代码）

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

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

C二级辅导-阶乘数列（C++代码）

C语言训练-角谷猜想（C++代码）（3N+1问题）

C语言考试练习题_一元二次方程（C语言代码）

　　评论区

WU-输入输出格式练习（C++代码）

三角形（C++代码）递推