青蛙跳杯子

问题描述

　　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

数据规模和约定

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

　　资源约定：
　　峰值内存消耗（含虚拟机） < 256M
　　CPU消耗 < 1000ms

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

　　所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
　　不要使用package语句。不要使用jdk1.7及以上版本的特性。
　　主类的名字必须是：Main，否则按无效代码处理。

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

　　笨笨有话说：

　　我梦见自己是一棵大树，
　　青蛙跳跃，
　　我就发出新的枝条，
　　春风拂动那第 5 层的新枝,
　　哦，我已是枝繁叶茂。

---

Algorithm

最近做的递归题目比较多，所以一上来就想到深搜，但是最后失败了，因为没想到怎么处理上一个状态，有可能青蛙一直跳来跳去.......

后来查了查，才明白这里要广搜，而且我居然还忽略了一段文字：

所以还顺便学习了广搜。

---

/*
* 我想应该是搜索杯子, 而不是青蛙 
* BFS
*/
#include<iostream>
#include<string>
#include<queue>
#include<map>

using namespace std;

// typedef pair<string, int> P;
// 字典好一些 
typedef map<string, int> MAP;

string a, b;
int go[6] = {-1, -2, -3, 3, 2, 1}; // 表示6种走法 

struct node{
    string s;    // 当前状态 
    int step;    // 到达改状态所需的步数 
    int loc;    // 杯子的位置 
    node(string S, int Step, int Loc)
    {
        s = S; step = Step; loc = Loc;
    }
    node(){
    }
};

void swap(string &s, int loc, int x)
{
    char temp = s.at(loc);
    s.at(loc) = s.at(x);
    s.at(x) = temp;
}

void bfs()
{
    queue<node> Q;
    MAP book;
    int len = a.size();
    // 找到杯子的初始位置 
    int loc = a.find('*');
    // 构造结构体 
    node p = node(a, 0, loc);
    // 将初始信息压入队列 
    Q.push(p);
    // 初始状态已走过 
    book[a] = 1;
    while(!Q.empty())
    {
        // 取出一个状态, 由它出发继续搜索下一步 
        p = Q.front();
        Q.pop();
        if(p.s == b){ // BFS找到结果一定是最优结果 
            cout<<p.step<<'
';
            return;
        }
        node temp;
        for(int i=0;i<6;i++){ // 枚举 6 中走法 
            temp.loc = p.loc + go[i]; // 下一步杯子的位置 
            if(temp.loc < 0 || temp.loc >= len) // 越界？ 
                continue;
            string str = p.s;
            // 更新状态, 上一步的位置与现在走到的位置交换 
            swap(str, temp.loc, p.loc);
            temp.s = str;
            temp.step = p.step + 1;
            if(!book[temp.s]){ // 这个状态没有出现过就压入队列 
                Q.push(temp);
                book[temp.s] = 1;
            }
        }
    }
    while(!Q.empty()) Q.pop();
}

int main()
{
    while(cin>>a>>b)
    {
        bfs();
    }
    
    return 0;
}

2019-02-20

14:41:23