青蛙跳杯子问题描述

80 阅读 0 评论 53 点赞

我是靠谱客的博主殷勤毛豆，最近开发中收集的这篇文章主要介绍青蛙跳杯子问题描述，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题描述

　　X星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。
　　X星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。
　　如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。

　　*WWWBBB

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

　　X星的青蛙很有些癖好，它们只做3个动作之一：
　　1. 跳到相邻的空杯子里。
　　2. 隔着1只其它的青蛙（随便什么颜色）跳到空杯子里。
　　3. 隔着2只其它的青蛙（随便什么颜色）跳到空杯子里。

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

　　WWW*BBB

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

　　输入为2行，2个串，表示初始局面和目标局面。
　　输出要求为一个整数，表示至少需要多少步的青蛙跳。

样例输入

*WWBB
WWBB*

样例输出

样例输入

WWW*BBB
BBB*WWW

样例输出

数据规模和约定

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

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

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

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

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

　　笨笨有话说：

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

Algorithm

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

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

所以还顺便学习了广搜。

 1 /*
 2 * 我想应该是搜索杯子, 而不是青蛙
 3 * BFS
 4 */
 5 #include<iostream>
 6 #include<string>
 7 #include<queue>
 8 #include<map>
 9
10 using namespace std;
11
12 // typedef pair<string, int> P;
13 // 字典好一些 
14 typedef map<string, int> MAP;
15
16 string a, b;
17 int go[6] = {-1, -2, -3, 3, 2, 1}; // 表示6种走法 
18
19 struct node{
20
string s;
// 当前状态 
21
int step;
// 到达改状态所需的步数 
22
int loc;
// 杯子的位置 
23
node(string S, int Step, int Loc)
24 
{
25
s = S; step = Step; loc = Loc;
26 
}
27 
node(){
28 
}
29 };
30
31 void swap(string &s, int loc, int x)
32 {
33
char temp = s.at(loc);
34
s.at(loc) = s.at(x);
35
s.at(x) = temp;
36 }
37
38 void bfs()
39 {
40
queue<node> Q;
41 
MAP book;
42
int len = a.size();
43
// 找到杯子的初始位置 
44
int loc = a.find('*');
45
// 构造结构体 
46
node p = node(a, 0, loc);
47
// 将初始信息压入队列 
48 
Q.push(p);
49
// 初始状态已走过 
50
book[a] = 1;
51
while(!Q.empty())
52 
{
53
// 取出一个状态, 由它出发继续搜索下一步 
54
p = Q.front();
55 
Q.pop();
56
if(p.s == b){ // BFS找到结果一定是最优结果 
57
cout<<p.step<<'n';
58
return;
59 
}
60 
node temp;
61
for(int i=0;i<6;i++){ // 枚举 6 中走法 
62
temp.loc = p.loc + go[i]; // 下一步杯子的位置 
63
if(temp.loc < 0 || temp.loc >= len) // 越界？ 
64
continue;
65
string str = p.s;
66
// 更新状态, 上一步的位置与现在走到的位置交换 
67 
swap(str, temp.loc, p.loc);
68
temp.s = str;
69
temp.step = p.step + 1;
70
if(!book[temp.s]){ // 这个状态没有出现过就压入队列 
71 
Q.push(temp);
72
book[temp.s] = 1;
73 
}
74 
}
75 
}
76
while(!Q.empty()) Q.pop();
77 }
78
79 int main()
80 {
81
while(cin>>a>>b)
82 
{
83 
bfs();
84 
}
85
86
return 0;
87 }