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

标题：青蛙跳杯子[详解]

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

*WWWBBB

其中，W字母表示白色青蛙，B表示黑色青蛙，*表示空杯子。X星的青蛙很有些癖好，它们只做3个动作之一：
1. 跳到相邻的空杯子里。
2. 隔着1只其它的青蛙（随便什么颜色）跳到空杯子里。
3. 隔着2只其它的青蛙（随便什么颜色）跳到空杯子里。对于上图的局面，只要1步，就可跳成下图局面：

WWW*BBB

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

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

解题思路:
做这个首先我想到的是直接暴解,但是最后超时了,然后最后debug了下,发现有重复的.这就好办了,直接利用集合特性进行存储,简化了代码.
通过题目可以清楚的知道,这是广搜,
题目是青蛙跳来跳去,但实际真正跳的是空杯子,如果咱们把空杯子当作主角,你会发现巨简单,
题目是3种跳法,所以每一次有6种步数.
我定义了一个试探类,功能是对传过来的状态进行6种移动,每一种的成功移动的状态存储到集合中,然后下一次搜索的基础就是迭代这个集合中的状态.
最后每一次成功移动且得出的状态存入集合后,要把打乱的状态给还原过去,以便下一次移动的准确性.

package eight;
import java.util.*;
public class 蓝桥杯_青蛙跳杯子 {static int sum;static void bfs(Set test, String over) {if(test.contains(over)) {System.out.println(sum);return;}Set s2=new HashSet();for(Object ob : test) {String str=String.valueOf(ob);Set s1=shitan(str);		s2.addAll(s1);}sum++;bfs(s2,over);}static Set shitan(String s) {Set st=new HashSet();char[]c=s.toCharArray();move(-3,c,st);move(-2,c,st);move(-1,c,st);move(1,c,st);move(2,c,st);move(3,c,st);return st;/}static void move(int i,char[] c2,Set st) {int lo=(String.valueOf(c2)).indexOf("*");if((lo+i) >= String.valueOf(c2).length() || (lo+i) <0)return;//System.out.println(String.valueOf(c2).length()+"####1:"+lo+"-------2:"+(lo+i));c2[lo]=c2[lo+i];c2[lo+i]='*';st.add(new String(c2));//c2[lo+i]=c2[lo];c2[lo]='*';}
public static void main(String[] args) {Scanner shu = new Scanner(System.in);String from=shu.next();String over=shu.next();Set test=new HashSet();test.add(from);bfs(test,over);
}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！