标题：青蛙跳杯子
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 层的新枝,
哦，我已是枝繁叶茂。
解析：
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.TreeSet;
//WWW*BBBWWWBBBW
//BBB*WWWBBBWWWW
//结果：20，用于测试执行速度
class MyNode
{
String str; //字符串
int step; //字符串变化中的步骤是第几步
public MyNode(String str,int step)
{
this.str = str;
this.step = step;
}
}
public class T09
{
//存储所有跳杯子过程中的字符串,用于循环中查重，剪枝
//此处不能使用ArrayList或LinkedList,执行效率会很低下。
static TreeSet<String> set = new TreeSet<String>();
public static void main(String[] args)
{
Scanner input = new Scanner(System.in);
String strStart = input.next();
String strEnd = input.next();
jump(strStart,strEnd);
}
public static void jump(String strStart,String strEnd)
{
Queue<MyNode> queue = new LinkedList<MyNode>();
queue.add(new MyNode(strStart,0)); //队列中添加第一个元素
set.add(strStart); //set中添加第一个元素
while(queue.size() != 0)
{
MyNode myNode = queue.poll(); //队列取出第一个元素并且删除第一个元素
//System.out.println("------"+myNode.str );
if(myNode.str.equals(strEnd)) //如果当前队列内容和目标内容相同，则程序结束
{
System.out.println(myNode.step);
break;
}
char[] arrCh = myNode.str.toCharArray(); //字符串转字符数组
int index = myNode.str.indexOf("*"); //确定*的位置
//确定交换的开始和结束位置
int start = index-3; //与*交换的开始位置
int end = index + 3; //与*交换的结束位置
if(start <= 0) start = 0;
if(end >= arrCh.length - 1) end = arrCh.length-1;
//循环计算当前节点下所有跳杯后的结果
for (int i = start; i <=end; i++)
{
if(arrCh[i] == '*') //自己和自己不用交换
continue;
swap(arrCh,i,index); //交换跳杯
//判断当前交换后的字符串在原始的set中是否存在，不存在则需要添加到队列,存在则不需要添加
if(set.contains(String.valueOf(arrCh)) == false)
{
MyNode tempNode = new MyNode(String.valueOf(arrCh), myNode.step+1);
queue.add(tempNode);
set.add(tempNode.str);
//System.out.println(tempNode.str + "," + tempNode.step);
}
swap(arrCh,i,index); //还原交换跳杯
}
}
}
public static void swap(char[] arr,int i,int j)
{
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
备注：
（1）此题思路为用队列Queue存储第一个自定义节点MyNode，节点字符串为题目输入开始字符串，step为0，
（2）然后取出Queue队列的每个元素，并且删除该元素，将该元素可以移动成为的所有字符串在添加到Queue队列中，并且将其step赋值当前节点的step+1.（此处如果交换计算得出的字符串在TreeSet中已经存在则不添加，实现模拟剪枝操作）。
（3）在不停的取Queue队列每个元素过程中，判断当前节点的字符串是否和目标字符串相等，相等则打印step结果。
（4）此题中step的变化一定是从小到大的，也就是说一定是将step=1的所有字符串处理完成后才会处理step=2的情况，所以只要出现相等情况，则step就是最小值。
（5）此题存储历史字符串集合，不用使用List接口下的LinkedList或ArrayList，会超过时间，需要使用TreeSet。
网友评论