网站开发工作图解,女生网站开发,做网站 先备案么,网站内容建设培训通知题目描述
题目描述
X星球的流行宠物是青蛙#xff0c;一般有两种颜色#xff1a;白色和黑色。X星球的居民喜欢把它们放在一排茶杯里#xff0c;这样可以观察它们跳来跳去。如下图#xff0c;有一排杯子#xff0c;左边的一个是空着的#xff0c;右边的杯子#xff0c;每…题目描述
题目描述
X星球的流行宠物是青蛙一般有两种颜色白色和黑色。X星球的居民喜欢把它们放在一排茶杯里这样可以观察它们跳来跳去。如下图有一排杯子左边的一个是空着的右边的杯子每个里边有一只青蛙。*WWWBBB其中W字母表示白色青蛙B表示黑色青蛙*表示空杯子。X星的青蛙很有些癖好它们只做3个动作之一1. 跳到相邻的空杯子里。2. 隔着1只其它的青蛙随便什么颜色跳到空杯子里。3. 隔着2只其它的青蛙随便什么颜色跳到空杯子里。对于上图的局面只要1步就可跳成下图局面WWW*BBB本题的任务就是已知初始局面询问至少需要几步才能跳成另一个目标局面。输入为2行2个串表示初始局面和目标局面。
输出要求为一个整数表示至少需要多少步的青蛙跳。例如
输入
*WWBB
WWBB*则程序应该输出
2再例如
输入
WWW*BBB
BBB*WWW则程序应该输出
10我们约定输入的串的长度不超过15资源约定
峰值内存消耗含虚拟机 256M
CPU消耗 1000ms请严格按要求输出不要画蛇添足地打印类似“请您输入...” 的多余内容。所有代码放在同一个源文件中调试通过后拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是Main否则按无效代码处理。----------------------------笨笨有话说我梦见自己是一棵大树青蛙跳跃我就发出新的枝条春风拂动那第 5 层的新枝,哦我已是枝繁叶茂。
思路分析
bfs
代码实现
package lanqiao;import java.util.*;public class Main {private static StringBuilder start;private static StringBuilder target;static SetString allStatenew HashSetString();/*** 封装一个持有状态和层次的类*/private static class StateAndLevel{StringBuilder state;int level;int pos;//空杯子的位置public StateAndLevel(StringBuilder state, int level,int pos) {this.state state;this.level level;//走的步数this.pospos;}Overridepublic int hashCode() {return state!null?state.hashCode():0;}Overridepublic boolean equals(Object o) {if(thiso) return true;if(onull||getClass()!o.getClass()) return false;StateAndLevel thar (StateAndLevel) o;return state!null?state.toString().equals(thar.state.toString()):thar.statenull;}}public static void main(String[] args) {Scanner scanner new Scanner(System.in);start new StringBuilder(scanner.nextLine());target new StringBuilder(scanner.nextLine());bfs();}private static void bfs() {/*初始状态加入队列*/QueueStateAndLevel qnew LinkedList();q.add(new StateAndLevel(start, 0, start.indexOf(*)));allState.add(start.toString());/*不定的弹出对手一步烟花成相邻状态加入队列(判重)*/while (!q.isEmpty()){StateAndLevel front q.poll();StringBuilder state front.state;int level front.level;//和 目标值作比较if (state.toString().equals(target.toString())){System.out.println(level);break;}int pos front.pos;//可以演化出若干种相邻的状态for (int i -3; i 3; i) {if(i0) continue;if(posi0posistate.length()){StringBuilder new_state new StringBuilder(state);swap(new_state,pos,posi);//交换达到新状态if (!allState.contains(new_state)){q.add(new StateAndLevel(new_state, level 1, pos i));allState.add(new_state.toString());//放入set}}}}}public static void swap(StringBuilder a,int i,int j){char ta.charAt(i);a.setCharAt(i,a.charAt(j));a.setCharAt(j,t);}}
