标题：青蛙跳杯子 [详解] X星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。X星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。 如下图，有一排杯子，左边的一个是空着的
标题：青蛙跳杯子[详解]
X星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。 X星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。 如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。 123
*WWWBBB
其中，W字母表示白色青蛙，B表示黑色青蛙，*表示空杯子。 X星的青蛙很有些癖好，它们只做3个动作之一： 1. 跳到相邻的空杯子里。 2. 隔着1只其它的青蛙（随便什么颜色）跳到空杯子里。 3. 隔着2只其它的青蛙（随便什么颜色）跳到空杯子里。 对于上图的局面，只要1步，就可跳成下图局面： 12345678
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); } }
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354相关知识
【蓝桥杯】历届试题 青蛙跳杯子（广度优先搜索bfs）
头带天坑的茶杯体球体小博美，体型只有杯子大小
宠物“作死”大赛, 它们到底吃过什么东西, 医生用X光告诉你！
从狗狗大便的颜色形状来判断健康状况，宠物粪便里的知识！
杯子里面的宠物狗
辟谣！猫咪的视觉很敏锐？有夜视能力不代表它们视力好
可以吃的鼠有哪几个品种
白色的宠物鸟有哪些 爱问知识人
虎皮鹦鹉作为人们极其喜欢的宠物，它们的生活是否快乐？
人类为何奔跑：那些动物教会我的跑步和生活之道
网址: 标题：青蛙跳杯子 [详解] X星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。X星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。 如下图，有一排杯子，左边的一个是空着的 https://m.mcbbbk.com/newsview552524.html
| 上一篇: 我问个冷门的问题：猎人模型最小的 |
下一篇: 暗月马戏团超级观赏宠物青蛙小加布 |
