该题可作为一道练习广搜bfs的例题~

题目来源：
青蛙跳杯子

问题描述
　　X星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。
　　X星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。
　　如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。
　　WWWBBB
　　其中，W字母表示白色青蛙，B表示黑色青蛙，表示空杯子。
　　X星的青蛙很有些癖好，它们只做3个动作之一：
　　1. 跳到相邻的空杯子里。
　　2. 隔着1只其它的青蛙（随便什么颜色）跳到空杯子里。
　　3. 隔着2只其它的青蛙（随便什么颜色）跳到空杯子里。
　　对于上图的局面，只要1步，就可跳成下图局面：
　　WWWBBB
　　本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。
　　输入为2行，2个串，表示初始局面和目标局面。
　　输出要求为一个整数，表示至少需要多少步的青蛙跳。
样例输入
*WWBB
WWBB
样例输出
2
样例输入
WWWBBB
BBBWWW
样例输出
10
数据规模和约定
　　我们约定，输入的串的长度不超过15
　　资源约定：
　　峰值内存消耗（含虚拟机） < 256M
　　CPU消耗 < 1000ms

题目分析

1. 数据规模不大，大胆启用广搜；
2. 值得注意的是，搜索的过程需要记录字符串的状态，涉及到更改字符的位置，所以使用char[]方便一些；
   bfs更改状态，每一步最多生成6种结果；
   如 WWWBBB
   跳一步的结果可能有： WWWBBB、WWWBBB、WWWBBB、WWWBBB、WWWBB*B、WWWBBB
3. 显然这里记录的状态要用结构体或者类来定义；
   另外后续一旦有重复的出现，一定要剪枝；
   C++中map、set都实现去重（亲测map效率更高），集合中存放结构体需要重载一下运算符；

所以一个bfs实现起来真是有需要注意的地方，用Java实现似乎代码量小一些，后续再更新吧~

————————————————————完整代码————————————————————

#include <iostream>
#include <cstring>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

struct state{
	char a[18];
	int level;//搜索树的深度
	int pos;//“*”所在的位置
	bool operator < (const state &b) const{
		return strcmp(a, b.a)<0;
	}//涉及到集合如map、set存储结构体时需要重载一下运算符
};
char s[18], ss[18];
int n, k;//记录串的长度，“*”所在位置
queue<struct state> q;
map<struct state, int> mp;
void copy(char c[], char x[]){//copy x[] to c[]
	for(int i = 0; i < n; ++i)
		c[i] = x[i];
}
void swap(char s[], int x, int y){//更新char[]数组
	char ch = s[x];
	s[x] = s[y];
	s[y] = ch;
}
void bfs(){
	struct state que;
	copy(que.a, s);
	que.level = 0;
	que.pos = k;
	q.push(que);
	while(!q.empty()){
		struct state front = q.front();
		char b[18];
		copy(b, front.a);
		int level = front.level;
		int pos = front.pos;
		q.pop();
		if(!strcmp(b, ss)){//一旦bfs出一组可行解，退出程序
			printf("%d\n", level);
			break;
		}	
		for(int i = -3; i <= 3; ++i){//对于一个字符串，
			char c[18];
			if(i == 0)
				continue;
			if(i+pos>=0 && i+pos<n){
				copy(c, b);
				swap(c, pos, pos+i);
				copy(front.a, c);
				front.level = level+1; front.pos = pos+i;
				if(mp[front]!=1){
					mp[front] = 1;
					q.push(front);
				}	
			}
			
		}
	}
} 
int main(){
	scanf("%s", s);
	scanf("%s", ss);
	n = strlen(s);
	for(int i = 0; i < n; ++i){
		if(s[i] == '*')
			k = i;
	}
	bfs();
	return 0;
}