【蓝桥杯】历届试题 青蛙跳杯子（C++）
问题描述解题思路具体代码
问题描述
题目链接：青蛙跳杯子. 问题描述 X星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。 X星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。 如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。 *WWWBBB 其中，W字母表示白色青蛙，B表示黑色青蛙，*表示空杯子。 X星的青蛙很有些癖好，它们只做3个动作之一： 1. 跳到相邻的空杯子里。 2. 隔着1只其它的青蛙（随便什么颜色）跳到空杯子里。 3. 隔着2只其它的青蛙（随便什么颜色）跳到空杯子里。 对于上图的局面，只要1步，就可跳成下图局面：
WWW*BBB 本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。 输入为2行，2个串，表示初始局面和目标局面。 输出要求为一个整数，表示至少需要多少步的青蛙跳。 样例输入：
*WWBB
WWBB* 样例输出: 2 样例输入: WWW*BBB
BBB*WWW 样例输出: 10
解题思路
广搜，思路代码借鉴：历届试题 青蛙跳杯子.
具体代码
#include
<cstdio
>
#include
<iostream
>
#include
<cstring
>
#include
<string
>
#include
<map
>
#include
<queue
>
#define
bug(x
) printf("%d***\n",x
)
typedef long long ll
;
using namespace std
;
const int inf
=0x3f3f3f3f;
map
<string
,int
>mp
;
string a
,b
;
queue
<string
> q
;
int
bfs(){
while(!q
.empty()){
string now
=q
.front();
q
.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
);
int ans
=bfs();
printf("%d\n",ans
);
return 0;
}
```
