第三届蓝桥杯预赛真题-C++高职组-10题（Java实现）
??? 2x3=6个方格中放入ABCDE五个字母，右下角的那个格空着。如图【1.jpg】所示。
?
??? 和空格子相邻的格子中的字母可以移动到空格中，比如，图中的C和E就可以移动，移动后的局面分别是：
A B
D E C
A B C
D?? E
??? 为了表示方便，我们把6个格子中字母配置用一个串表示出来，比如上边的两种局面分别表示为：
AB*DEC
ABCD*E
??? 题目的要求是：请编写程序，由用户输入若干表示局面的串，程序通过计算，输出是否能通过对初始状态经过若干次移动到达该状态。可以实现输出1,否则输出0。初始状态为：ABCDE*
??
??? 用户输入的格式是：先是一个整数n，表示接下来有n行状态。程序输出也应该是n行1或0
??? 例如，用户输入：
3
ABCDE*
AB*DEC
CAED*B
??? 则程序应该输出：
1
1
0
??? 注意：
??? 请仔细调试！您的程序只有能运行出正确结果的时候才有机会得分！
???
??? 在评卷时使用的输入数据与试卷中给出的实例数据可能是不同的。
??? 请把所有函数写在同一个文件中，调试好后，存入与【考生文件夹】下对应题号的“解答.txt”中即可。
???
??? 相关的工程文件不要拷入。
???
??? 源代码中不能能使用诸如绘图、Win32API、中断调用、硬件操作或与操作系统相关的API。
???
??? 允许使用STL类库，但不能使用MFC或ATL等非ANSI c++标准的类库。例如，不能使用CString类型（属于MFC类库）。
------------------------------
我利用广度优先算法。并且连移动的步骤都打印出来了。
?
import java.util.ArrayList;import java.util.Scanner;public class Move {private static String destStr="ABCDE*";//目标字符串ArrayList<String>remove=new ArrayList<String>();private static boolean result=false;public static void main(String[] args) {Scanner scan=new Scanner(System.in);System.out.print("请输入目标状态字符串：");String user=scan.nextLine();new Move().find(user, user);if(!result) System.out.println("无解");}//寻找解public void find(String str,String bz){ArrayList<moveStr>list=new ArrayList<moveStr>();moveStr ms=new moveStr(str,bz);list.add(ms);//入队remove.add(str);while(list.size()>0){String temp="";moveStr tempMs=list.get(0);//出队if(tempMs.str.equals("str")&&list.size()!=1) return;if(tempMs.str.equals(destStr)){result=true;System.out.println(str+": 有解 "+tempMs.bz);return ;}list.remove(0);int k=tempMs.str.indexOf("*");//找到*号出现的位置if(k!=2){temp=sawp(tempMs.str,k+1);//向右移动if(!temp.equals("")&&!remove.contains(temp)) {String tempBz=tempMs.bz+"->"+temp;moveStr ms1=new moveStr(temp,tempBz);list.add(ms1);remove.add(temp);}temp=sawp(tempMs.str,k-3);//向上移动if(!temp.equals("")&&!remove.contains(temp)) {String tempBz=tempMs.bz+"->"+temp;moveStr ms1=new moveStr(temp,tempBz);list.add(ms1);remove.add(temp);}}if(k!=3){temp=sawp(tempMs.str,k-1);//向左移动if(!temp.equals("")&&!remove.contains(temp)) {String tempBz=tempMs.bz+"->"+temp;moveStr ms1=new moveStr(temp,tempBz);list.add(ms1);remove.add(temp);}temp=sawp(tempMs.str,k+3);//向下移动if(!temp.equals("")&&!remove.contains(temp)) {String tempBz=tempMs.bz+"->"+temp;moveStr ms1=new moveStr(temp,tempBz);list.add(ms1);remove.add(temp);}}}}//移动字母public static String sawp(String str,int j){if(j<0||j>=str.length()) return "";int i=str.indexOf("*");String old=str.charAt(j)+""; str=str.replace(old, "*");if(i<j) str=str.replaceFirst("\\*", old);else {String start=str.substring(0,str.indexOf("*")+1);String end=str.substring(str.indexOf("*")+1);end=end.replace("*", old);str=start+end;}return str;}class moveStr{String str;String bz;moveStr(String str,String bz){this.str=str;this.bz=bz;}public String getStr() {return str;}public void setStr(String str) {this.str = str;}public String getBz() {return bz;}public void setBz(String bz) {this.bz = bz;}}}?