蓝桥杯：青蛙跳杯子

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

*WWWBBB

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

X星的青蛙很有些癖好，它们只做3个动作之一：

1. 跳到相邻的空杯子里。
2. 隔着1只其它的青蛙（随便什么颜色）跳到空杯子里。
3. 隔着2只其它的青蛙（随便什么颜色）跳到空杯子里。

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

WWW*BBB

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

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

例如：
输入：
WWBB
WWBB

则程序应该输出：
2

再例如，
输入：
WWWBBB
BBBWWW

则程序应该输出：
10

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

思路：使用广度优先搜索（dfs）

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class JumpingCup {
static String s1;
static String goal;
public static int dfs(Set<String> from, Set<String> hist) {
if(from.contains(goal)) return 0;
Set<String> from2 = new HashSet<>();
for(String key: from) {
Set<String> t = creat(key);
from2.addAll(t);
}
from2.removeAll(hist);
if(from2.isEmpty()) return -1;
hist.addAll(from2);
int r = dfs(from2, hist);
if(r<0) return -1;
return r+1;
}
public static Set<String> creat(String key) {
Set<String> set = new HashSet<>();
char[] c = key.toCharArray();
for(int i=0; i<c.length; i++) {
tryMove(c, i, -1, set);
tryMove(c, i, -2, set);
tryMove(c, i, -3, set);
tryMove(c, i, 1, set);
tryMove(c, i, 2, set);
tryMove(c, i, 3, set);
}
return set;
}
public static void tryMove(char[] c, int i, int step, Set<String> set) {
if(c[i] == '*') return;
int sum = i + step;
if(sum < 0 || sum >= c.length) return;
if(c[sum] != '*') return;
c[sum] = c[i];
c[i] = '*';
set.add(new String(c));
c[i] = c[sum];
c[sum] = '*';
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
s1 = sc.nextLine();
goal = sc.nextLine();
Set<String> from = new HashSet<>();
Set<String> hist = new HashSet<>();
from.add(s1);
hist.addAll(from);
sc.close();
System.out.println(dfs(from, hist));
}
}

最后

以上就是勤劳电灯胆为你收集整理的蓝桥杯：青蛙跳杯子的全部内容，希望文章能够帮你解决蓝桥杯：青蛙跳杯子所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。