蓝桥杯 历届试题 青蛙跳杯子(c++)
问题描述
X星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。
X星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。
如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。
*WWWBBB
其中，W字母表示白色青蛙，B表示黑色青蛙，*表示空杯子。
X星的青蛙很有些癖好，它们只做3个动作之一：
1. 跳到相邻的空杯子里。
2. 隔着1只其它的青蛙（随便什么颜色）跳到空杯子里。
3. 隔着2只其它的青蛙（随便什么颜色）跳到空杯子里。
对于上图的局面，只要1步，就可跳成下图局面：
WWW*BBB
本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。
输入为2行，2个串，表示初始局面和目标局面。
输出要求为一个整数，表示至少需要多少步的青蛙跳。
样例输入
WWBB
WWBB
样例输出
2
样例输入
WWWBBB
BBBWWW
样例输出
10
数据规模和约定
我们约定，输入的串的长度不超过15
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
思路：
队列、BFS
如果看作青蛙跳杯子，将比较复杂，但是如果反过来杯子与青蛙进行交换，每次最多有六种可能
#include <iostream> #include <string> #include <map> #include <queue> using namespace std; struct Que {string s;int count;int flag;Que(string S,int Count,int Flag){s=S;count=Count;flag=Flag;} }; int main() {string a;string b;int i;map<string,int> state;queue<Que> que;cin>>a>>b;if(a == b)cout<<"0";else{Que q = Que(a,0,a.find('*'));que.push(q);state[a]=1;while(!que.empty()){q=que.front();que.pop();for(i=q.flag-3;i<=q.flag+3;i++){if(i>=0&&i<q.s.size()&&i!=q.flag){string ss = q.s;char temp = ss[i];ss[i]=ss[q.flag];ss[q.flag]=temp;if(ss==b){cout<<q.count+1;return 0;}else if(state[ss]!=1){state[ss]=1;Que q1=Que(ss,q.count+1,i);que.push(q1);}}}}}return 0; }
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061相关知识
【蓝桥杯】历届试题 青蛙跳杯子（广度优先搜索bfs）
第十一届蓝桥杯青少组C++竞赛规则及样题.pdf.pdf
蓝桥杯2017年第八届真题
标题：青蛙跳杯子 [详解] X星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。X星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。 如下图，有一排杯子，左边的一个是空着的
蓝桥杯攻略！省一经验+考试全流程+技巧分享
蓝桥杯 算法训练 字符串编辑
京东青蛙跳宠物保健品店推出宠芝灵鹿角灵芝保健品胶囊
蓝桥杯大赛——视觉艺术设计赛
第八届蓝桥杯全国总决赛真题解析
（2017年电大）历届电大社交礼仪试题作业答案.doc
网址: 蓝桥杯 历届试题 青蛙跳杯子(c++) https://m.mcbbbk.com/newsview564413.html
| 上一篇: 如何养殖青蛙作为宠物?全面解析青 |
下一篇: 蓝桥杯 |
