问题描述

　　X星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。

　　X星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。

　　如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。

　　*WWWBBB

　　其中，W字母表示白色青蛙，B表示黑色青蛙，*表示空杯子。

　　X星的青蛙很有些癖好，它们只做3个动作之一：

　　. 跳到相邻的空杯子里。

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

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

　　对于上图的局面，只要1步，就可跳成下图局面：

　　WWW*BBB

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

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

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

样例输入

*WWBB

WWBB*

样例输出

样例输入

WWW*BBB

BBB*WWW

样例输出

数据规模和约定

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

　　资源约定：

　　峰值内存消耗（含虚拟机） < 256M

　　CPU消耗 < 1000ms

　　请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

　　所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

　　不要使用package语句。不要使用jdk1.7及以上版本的特性。

　　主类的名字必须是：Main，否则按无效代码处理。

　　----------------------------

　　笨笨有话说：

　　我梦见自己是一棵大树，

　　青蛙跳跃，

　　我就发出新的枝条，

　　春风拂动那第  层的新枝,

　　哦，我已是枝繁叶茂。

 #include <bits/stdc++.h>

 using namespace std;

 struct node

 {

     string s;    //排列类型

     int step;    //步数

     node(string s,int step):s(s),step(step)

     {}

 };

 string s1,s2;

 int ans;

 map<string,int> mp;

 void bfs()

 {

     int dir[] = {-,-,-,,,,};    //青蛙可以移动的方向

     queue<node> q;

     q.push(node(s1,));

     while (!q.empty())

     {

         node t = q.front();

         q.pop();

         if (t.s == s2)//检索到目标排列，打印步数并退出

         {

             cout << t.step;

             return ;

         }

         int k = t.s.size();

         for (int i= ; i<k ; i++) //遍历所有青蛙

         {

             for (int j= ; j< ; j++) //遍历可能移动的方向

             {

                 int n = i+dir[j];

                 string tmp = t.s;

                 if (n>= && n<=k && tmp[n]=='*')//合法范围内，且为空杯子可跳

                 {

                     swap(tmp[n],tmp[i]);        //交换青蛙和空杯的位置

                     if (mp[tmp] == )    //将本次的排列类型存储

                     {

                         mp[tmp] = ;

                         q.push(node(tmp,t.step+));

                     }

                 }

             }

         }

     }

     return ;

 }

 int main(void)

 {

     cin >> s1 >> s2;

     bfs();

     return ;

 }