青蛙跳杯子 [详解] X星球的流行宠物是青蛙,一般有两种颜色:白色和黑色。X星球的居民喜欢把它们放在一排茶杯里,这样可以观察它们跳来跳去。

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

*WWWBBB

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

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

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

WWW*BBB

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

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

例如:
输入:
WWBB WWBB

则程序应该输出:
2

再例如,
输入:
WWWBBB BBBWWW

则程序应该输出:
10

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

解题思路:
我用的是暴解,但是超时了,最后发现有重复的.这就好办了,直接利用集合特性进行存储,简化了代码.
通过题目可以清楚的知道,这是广搜,
题目是青蛙跳来跳去,但实际真正跳的是空杯子,如果咱们把空杯子当作主角,你会发现巨简单,
题目是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);
}
}

分享到:
赞(0) 打赏

评论 5

评论前必须登录!

 

  1. #1

    以后多发点哦

    奋斗6个月前 (03-27)
  2. #2

    记住这个网站了

    笨鸟先飞6个月前 (03-28)
  3. #3

    还可以

    笔记本4个月前 (05-26)
  4. #4

    给你点赞

    笔记本4个月前 (05-26)
  5. #5

    我给你点赞了

    沥青4个月前 (05-26)

觉得文章有用就打赏一下弟弟吧

支付宝扫一扫打赏

微信扫一扫打赏

Vieu4.5主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。
正在播放:

作者想对您说:

累了就停下来听首歌吧

听完后会给您一个好心情

最后

等到您不容易

还希望您能多待一会儿

      00:00/00:00