首页 > 分享 > 【蓝桥杯】历届试题青蛙跳杯子（广度优先搜索bfs）

【蓝桥杯】历届试题青蛙跳杯子（广度优先搜索bfs）

萌宠菠菠乐园
2024-10-29 14:55

历届试题青蛙跳杯子

问题描述

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*

样例输出

样例输入

WWW*BBB
BBB*WWW

样例输出

数据规模和约定

我们约定，输入的串的长度不超过 15。

—— 众里寻她 ——

首先对本题进行一个解读：青蛙们排成一排，对于每个青蛙而言其都能往自身以左或右跳 1、2 和 3 格的距离，但是青蛙只能往空位置跳（空位置用 *号表示）。显然，当青蛙跳到某个空位置后，其原来所在的位置就成为了新的空位，宏观上看来就是发生了交换。而本题的任务就是给一个初始状态和一个目标状态，问最少需要多少步能完成从初始到目标状态的转变。

看完题的第一感觉是不知道从何下手。

这类题目往往需要我们转变思维，这里最关键的一个转变是：不要以青蛙为主体去对字符串中的空位进行位置交换，而是转而以空位为主体，将题目转化为 “有两个字符串例如 *WWBB 和 WWBB*，* 每次能往左或右跳 1-3 步，并与指定位置的字符交换，问最少需要多少步能从一个字符串变为另一个”。

这样对题目进行转化后对于我们理解和编程轻松了很多，但是我们如何去实现字符串的转变呢？

就拿字符串 *WWBB 来说，第一次 * 只有3个移动方案：

与第一个 ”W” 发生交换得到 ”W*WBB”。与第二个 ”W” 发生交换得到 ”WW*BB”。与第三个 ”B” 发生交换得到 ”BWW*B”。

在这三个方案中，我们发现没有任何一个转变能够变为最终的目标字符串，于是我们需要再次移动。但是很显然，此刻的移动方案是依赖于前面所处状态的。比如当选择方案 2 的结果（WW*BB）作为新的出发点时，接下来的移动方案有以下4个：

与第一个 ”W” 发生交换得到 ”*WWBB”（回到初始状态）与第二个 ”W” 发生交换得到 ”W*WBB”与第三个 ”B” 发生交换得到 ”WWB*B”与第四个 ”B” 发生交换得到 ”WWBB*”（得到目标字符串）

从上面的模拟求解过程中可以看出，* 的移动需要依赖前一次得到的状态，也就是说这是一个递归求解的过程。更准确说来，这是一个搜索过程。由于我们需要找的是最少步数，因此我们需要进行宽度优先搜索，即 bfs。

以前在解答一些求最短路径的题时，我们通常会设置一个 bool 型的 vis[ ][ ] 数组来标记某些点是否已遍历过，以防止出现自循环现象，同样地本题也是。不同的是，本题设置的就不是 vis[ ][ ] 数组了，而是一个 string 类集合。因为对于某些字符串，在 bfs 过程中可能会出现 “回到初始状态” 的情形，一方面可能会导致程序进入死循环。比如在上面模拟求解的第一个情况，在该处我们的算法得到了一个和初始状态一样的字符串，按照 bfs 算法我们会将其压入队列中。虽然在本例中出现该重复字符串不会影响最终得到目标字符串（因为在当时虽将其压入了队列，但是等到该字符串被取出前，在随后就将已经找到了目标字符串），但我们还是要对这样的情况做预防，因为在某些特定字符串下，就有可能无限循环下去；另一方面会使程序浪费大把时间去做重复且无意义的工作（因为在 bfs 中，第一次出现的某个状态，一定是步数最小的。故除了第一次遇到的状态，之后出现的都很多余）。

涉及到判重时，我们通常会采用 set（集合）这一数据结构，这是 STL 提供的模板数据结构，便捷实用。下面直接给出求解本题的完整代码：

—— 柳暗花明 ——

#include<iostream> #include<string> #include<queue> #include<set> using namespace std; int dir[]={-3,-2,-1,1,2,3};//可移动的 6种方案 struct situation{//定义结构体：形势string str;//当前形势下的字符串int step;//得到当前形势所需的步数situation(string s,int n)//构造函数{ str=s,step=n; } }; queue<situation> q; set<string> s; void bfs(string start,string target) {if(start==target){cout<<0<<endl;return;}q.push(situation(start,0));s.insert(start);while(!q.empty()){situation now=q.front();q.pop();string str=now.str;for(int i=0;i<str.length();i++){if(str[i]!='*') continue;//仅仅对空杯子的位置进行换位for(int j=0;j<6;j++){//尝试所有可以交换的方案int n=i+dir[j];if(n>=0 && n<str.length())//如果当前换位合法{swap(str[i],str[n]);//交换青蛙和空杯的位置if(str==target){//如果已经等于目标字符则输出cout<<now.step+1<<endl;return;}if(!s.count(str)){//如果当前字符串还未出现过s.insert(str);//那就标记该字符串为已走q.push(situation(str,now.step+1));}swap(str[i],str[n]);//恢复现场}}}} } int main() {string str1,str2;cin>>str1>>str2;bfs(str1,str2);return 0; }

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859