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

2年前 (2019-12-27) 383次浏览 已收录 5个评论
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. 以后多发点哦
    奋斗2020-03-27 14:17
  2. 记住这个网站了
    笨鸟先飞2020-03-28 17:33
  3. 还可以
    笔记本2020-05-26 09:14
  4. 给你点赞
    笔记本2020-05-26 09:41
  5. 我给你点赞了
    沥青2020-05-26 10:27