zzxkj

用户名：zzxkj

访问量：2096

签　名：

等　　级
排　　名	25070
经　　验	602
参赛次数	0
文章发表	6
年　　龄	0
在职情况	学生
学　　校	河南农业大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2017年第八届真题-拉马车 -题解(C++代码)
浏览：435

蓝桥杯2017年第八届真题-青蛙跳杯子-题解(C++代码)
浏览：705

你可能喜欢

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

蓝桥杯2017年第八届真题-青蛙跳杯子-题解(C++代码)

　　作者: zzxkj　　　　发表时间：2020-04-08 11:02:05 浏览：705　|　评论：1　

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

这是一道典型的bfs，青蛙每次可以跳到相邻杯子，隔着一个、两个跳到下个杯子，那么就是每次可以越1，2，3，因为本题只有两个方向，所以在一维方向上表现为{1，2，3，-1，-2，-3}；
跳跃我们可以认为是交换两个杯子里东西，因此用空的交换最好，即把空的当作一个青蛙；
所以接下来就是每次存放跳过后的序列，因为bfs是按层遍历，此时每种序列可能重复出现，即跳过去又跳过来，我们就可以利用序列去重。

#include<iostream>
    #include<queue>
    #include<map>
    using namespace std;
    int st[6]={1,2,3,-1,-2,-3};
    int sx,ans=0;
    int sum=0;
    map<string,int>mp; //利用map判断序列是否出现过，并去重
    string s1,s2;
    struct Node{ //定义结构体存放此时坐标，此时步数，此时序列
    	int x,k;
    	string sn;
    };
    void bfs(){  //bfs常规操作
    	queue<Node>q;
    	Node node;
    	node.x=sx;
    	node.k=0;
    	node.sn=s1;
    	mp[s1]=1;
    	q.push(node);
    	while(!q.empty()){
    		Node p=q.front();		
    		for(int i=0;i<6;i++)
    		{   
    		    string s=p.sn;        
    			int xx=p.x+st[i];
    			if(xx>=0&&xx<s1.length())
    			{	
    			Node v;	
    			swap(s[p.x],s[xx]);
    			if(mp[s]==1) continue;
    			mp[s]=1;
    			v.x=xx;
    			v.k=p.k+1;
    			v.sn=s;
    			if(v.sn==s2){
    				ans=v.k;
    				return;
    			} 
    			q.push(v);
    			}
    		}
    		q.pop();
    	}	 
    }
    int main()
    {	
    	cin>>s1>>s2;	
    	for(int i=0;i<s1.length();i++)
    	{
    		if(s1[i]=='*')  //找到那个空杯子
    		{
    			sx=i;
    		}
    	}
    	bfs();
    	cout<<ans<<endl;
    	return 0;
    }

0.0分

5 人评分

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

　　评论区

零星

大佬，
有纯C的代码吗

2021-04-04 22:28:40

zzxkj

TA的其他文章

你可能喜欢

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

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

C二级辅导-计负均正（C语言代码）

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

C二级辅导-进制转换（C语言代码）

蓝桥杯2017年第八届真题-青蛙跳杯子-题解(C++代码)

评论区

精彩推荐

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

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

字符串的输入输出处理（C语言代码）

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

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

C二级辅导-计负均正（C语言代码）

输出九九乘法表（C语言代码）

矩阵转置（C语言代码）

神奇的fans （C语言代码）

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

zzxkj

TA的其他文章

你可能喜欢

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

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

C二级辅导-计负均正 （C语言代码）

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

C二级辅导-进制转换 （C语言代码）

蓝桥杯2017年第八届真题-青蛙跳杯子-题解(C++代码)

评论区

精彩推荐

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

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

字符串的输入输出处理 （C语言代码）

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

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

C二级辅导-计负均正 （C语言代码）

输出九九乘法表 （C语言代码）

矩阵转置 （C语言代码）

神奇的fans （C语言代码）

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

C二级辅导-计负均正（C语言代码）

C二级辅导-进制转换（C语言代码）

　　评论区

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

字符串的输入输出处理（C语言代码）

C二级辅导-计负均正（C语言代码）

输出九九乘法表（C语言代码）

矩阵转置（C语言代码）