[蓝桥杯2017初赛]青蛙跳杯子

[蓝桥杯2017初赛]青蛙跳杯子

题目描述
X星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。
X星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。
如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。
*WWWBBB
其中，W字母表示白色青蛙，B表示黑色青蛙，*表示空杯子。
X星的青蛙很有些癖好，它们只做3个动作之一

1. 跳到相邻的空杯子里。
2. 隔着1只其它的青蛙（随便什么颜色）跳到空杯子里。
3. 隔着2只其它的青蛙（随便什么颜色）跳到空杯子里。
   对于上图的局面，只要1步，就可跳成该局面：WWWBBB
   本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。
   输入
   输入存在多组测试数据，对于每组测试数据：
   输入为2行，2个串，表示初始局面和目标局面。输入的串的长度不超过15
   输出
   对于每组测试数据：输出要求为一个整数，表示至少需要多少步的青蛙跳。
   样例输入 Copy
   WWBB
   WWBB
   WWWBBB
   BBB*WWW
   样例输出 Copy
   2
   10

package pro;
import java.util.*;
public class Main {
static int flag = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int arr[]={1,2,3,-1,-2,-3};
while(in.hasNext()) {
String s1 = in.next();
String s2 = in.next();
Queue<Node> queue = new LinkedList<>();
for(int i = 0; i < s1.length(); i++) {
if(s1.charAt(i)=='*') {
queue.add(new Node(i,0,s1));
break;
}
}
Map<String,Integer> map = new HashMap<>();
map.put(s1, 1);
while(!queue.isEmpty()) {
Node node = queue.poll();
for(int i = 0; i < 6; i++) {
char[] ch1 = node.s.toCharArray();
int idx = node.index + arr[i];
if(idx >= 0 && idx < s1.length()) {
char ch = ch1[idx];
ch1[idx] = ch1[node.index];
ch1[node.index] = ch;
String string = String.valueOf(ch1);
if(map.containsKey(String.valueOf(ch1)))
continue;
map.put(string, 1);
Node n = new Node(idx,node.cnt+1,string);
if(string.compareTo(s2)==0) {
System.out.println(n.cnt);
return;
}
queue.add(n);
}
}
}
}
}
}
class Node{
int index;
int cnt;
String s;
public Node(int index, int cnt, String s) {
super();
this.index = index;
this.cnt = cnt;
this.s = s;
}
}

bfs+map用于去重,交换string中的字符时,需将string转为char数组,因为char数组是引用类型,所以不使用char数组存储字符串

最后

以上就是斯文朋友为你收集整理的[蓝桥杯2017初赛]青蛙跳杯子的全部内容，希望文章能够帮你解决[蓝桥杯2017初赛]青蛙跳杯子所遇到的程序开发问题。

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