问题

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

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

解决办法

  要求青蛙最少跳多少次，要bfs将本节点的所有满足条件的下一个加入队列，并将加入队列的标记，这样用比较少的循环，将所有的状态遍历一遍而有不重复。 需要解决的问题： 1.每一个节点的每一个青蛙都要完成动作 2.每一个青蛙对应3种动作，向左向右不同，一共对应6种结果 3.所有的节点只能进入队列一次，用book标记

queue

先进先出的

#include<queue>  //定义，头文件
queue<int> s;  //创建一个int类型的队列
s.push(x);  //将x进队列
s.pop();  //将队首删除
s.front();  //取队首的值
s.size();  //队列的大小
s.empty();  //队列是否为空

bfs

  利用queue这样一个数据结构，广度的进行搜索节点，当前节点对应着一种状态，遍历当前的字符串，不为空杯子将说明有青蛙，青蛙的跳跃是（-3，3）距离，青蛙每一次的跳跃代表一种新的状态的形成。那么我们就要状态记录，由于状态为string类型，用map<string,int>标记，如果该状态已经在map中，就说明该状态已经遍历过，就不需要再次遍历。

#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
using namespace std;
typedef long long ll;
typedef struct node{
    string status;
    int step;
    node(string status,int step):status(status),step(step){};
}node;
#include<queue>
#include<map>
map<string,int> book;
string s1,s2;
int ans=-1;
void bfs()
{
    queue<node> s;
    s.push(node(s1,0));
    while(!s.empty())
    {
        node a=s.front();
        s.pop();
        string status=a.status;
        int step=a.step;
        if(status==s2)
        {
            ans=step;
            return;
        }
        int n=status.size();
        for(int i=0;i<n;i++)
        {
            for(int j=-3;j<=3;j++)
            {
                string temp=status;
                if(temp[i+j]!=*||i+j<0||i+j>=n)
                    continue;
                temp[i+j]=temp[i];
                temp[i]=*;
                if(!book[temp])
                {
                    book[temp]=1;
                    s.push(node(temp, step + 1));
                }

            }
        }

    }
}

int main()
{
    cin>>s1>>s2;
    bfs();
    cout<<ans;
    return 0;
}

测试结果：

总结

  bfs，将当前的节点所有的下一节点加入队列，重复当前行为。这样做的好处是所有的节点都只遍历一遍，在找下一节点这个过程中，需要判断这个节点是否满足条件，能否加入队列，在这个题目中，需要判断的是当前是否为青蛙，青蛙的跳跃是否合理，即青蛙跳跃不能越界和跳跃的终点是否为空杯子。用bfs，创建节点结构体，利用queue这种先进先出的数据结构，完成本题的解答。