问题描述 X星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。 X星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。 如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。 WWWBBB 其中，W字母表示白色青蛙，B表示黑色青蛙，表示空杯子。 X星的青蛙很有些癖好，它们只做3个动作之一： 1. 跳到相邻的空杯子里。 2. 隔着1只其它的青蛙（随便什么颜色）跳到空杯子里。 3. 隔着2只其它的青蛙（随便什么颜色）跳到空杯子里。 对于上图的局面，只要1步，就可跳成下图局面： WWWBBB 本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。 输入为2行，2个串，表示初始局面和目标局面。 输出要求为一个整数，表示至少需要多少步的青蛙跳。 样例输入 WWBB WWBB 样例输出 2 样例输入 WWWBBB BBB*WWW 样例输出 10 数据规模和约定 我们约定，输入的串的长度不超过15 资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms 1.BFS搜索→队列queue 2.map:记录状态 杯子与青蛙进行交换，最多有六种可能。
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<map> #include<queue> using namespace std; map<string,int>mp; //字符串到整数的映射 //map:记录状态 queue<string>q; //BFS-队列 string a,b; int bfs(){ while(!q.empty()){ string now=q.front();//front():返回队列的第一个元素的值 q.pop();//pop():删除第一个元素 if(now==b) return mp[now]; int pos; for(int i=0;i<now.length();i++){ if(now[i]=='*'){ pos=i;break; } } if(pos+1<now.length()){ string nt=now; swap(nt[pos],nt[pos+1]); if(!mp[nt]){ mp[nt]=mp[now]+1; q.push(nt); } } if(pos+2<now.length()){ string nt=now; swap(nt[pos],nt[pos+2]); if(!mp[nt]){ mp[nt]=mp[now]+1; q.push(nt); } } if(pos+3<now.length()){ string nt=now; swap(nt[pos],nt[pos+3]); if(!mp[nt]){ mp[nt]=mp[now]+1; q.push(nt); } } if(pos-1>=0){ string nt=now; swap(nt[pos],nt[pos-1]); if(!mp[nt]){ mp[nt]=mp[now]+1; q.push(nt); } } if(pos-2>=0){ string nt=now; swap(nt[pos],nt[pos-2]); if(!mp[nt]){ mp[nt]=mp[now]+1; q.push(nt); } } if(pos-3>=0){ string nt=now; swap(nt[pos],nt[pos-3]); if(!mp[nt]){ mp[nt]=mp[now]+1; q.push(nt); } } } } int main(){ cin>>a>>b; mp[a]=0; q.push(a);//push()就是从已有元素后面增加元素，将其插入队列中 int ans=bfs(); cout<<ans<<endl; return 0; }