蓝桥杯真题：青蛙跳杯子

问题描述
X 星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。
X 星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。
如下所示，有一排杯子。左边的一个是空着的，右边的杯子，每个里边有一只青蛙。
∗ W W W B B B *WWWBBB
∗WWWBBB

其中，W 表示杯子里是一只白色青蛙，B 表示杯子里是一只黑色青蛙，∗ *∗ 表示空杯子。
X 星的青蛙很有些癖好，它们只做 3 个动作之一：

跳到相邻的空杯子里。
隔着1只其它的青蛙（随便什么颜色）跳到空杯子里。
隔着2只其它的青蛙（随便什么颜色）跳到空杯子里。

对于上述局面，只要 1 步，就可跳成以下局面：
W W W ∗ B B B WWW*BBB
WWW∗BBB

本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。

输入数据
输入为 2 行，2 个串，分别表示初始局面和目标局面。

输出数据
输出要求为一个整数，表示至少需要多少步的青蛙跳。

样例输入
*WWBB
WWBB*

样例输出
2

样例输入
WWW*BBB
BBB*WWW

样例输出
10

数据规模和约定
我们约定，输入的串的长度不超过 15。

思路：暴力求最少方法的话，用bfs，求方法数采用dfs，但因为很久没写bfs了，一时间竟忘了两者的区别，还是看题解才想起来bfs该怎么做的，刚开始我也想用map记录得到过的字符串，这样就不存在重复走的情况了，但是当时觉得数量会有15！，会爆，其实也不会，因为整个字符串就三样字符，重复的字符串会频繁出现。代码如下：

#include<bits/stdc++.h>

using namespace std;

map<string,long long>vis;

int a[6]= {-3,-2,-1,1,2,3};

string Begin,End;

long long bfs() {

queue<string>q;

q.push(Begin);

int cnt=0;

while(!q.empty()) {

string s=q.front();

q.pop();

string olds=s;

if(s==End)return vis[s];

int pos=s.find('*');

for(int i=0; i<6; i++) {

int x=pos+a[i];

if(x>=0&&x<s.length()) {

swap(s[pos],s[x]);

if(vis[s]==0) {

q.push(s);

vis[s]=vis[olds]+1;

}

swap(s[pos],s[x]);

}

}

}

return 0;

}

int main() {

cin>>Begin>>End;

cout<<bfs()<<endl;

}

相关知识

蓝桥杯2017年第八届真题
【蓝桥杯】历届试题 青蛙跳杯子（广度优先搜索bfs）
第十一届蓝桥杯青少组C++竞赛规则及样题.pdf.pdf
标题：青蛙跳杯子 [详解] X星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。X星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。 如下图，有一排杯子，左边的一个是空着的
第八届蓝桥杯全国总决赛真题解析
蓝桥杯攻略！省一经验+考试全流程+技巧分享
2024年十五届蓝桥杯省赛大学B组真题（Java残缺版）
蓝桥杯 算法训练 字符串编辑
京东青蛙跳宠物保健品店推出宠芝灵鹿角灵芝保健品胶囊
蓝桥杯大赛——视觉艺术设计赛

网址: 蓝桥杯真题：青蛙跳杯子 https://www.mcbbbk.com/newsview564408.html