第三届蓝桥杯预赛真题-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;
		}
	}
	
}