信息学奥赛一本通T1449-魔板-题解（Java代码）

主要思路：

魔板的初始状态为，key="12348765"；

对魔板的操作有 A、B、C，对魔板遍历所有的操作,并且把每一个操作和对应的结果存储起来，如果某个结果和输入的结果相等，那么这个操作就是答案。

对魔板的操作过程为 A,B,C    AA,AB,AC    BA,BB,BC......

这与广度搜索的思想完全相同。

提交过程：

第一次提交，结果：超时

原因：因为在执行ABC操作时，会有许多的操作得到同样的结果，例如AA，得到的就是与原数据相同的值，这时如果继续加入队列，会增加许多不必要且重复的判断。

修改：增加一个判断，判断是否已经存在这个结果。

if (queValue.contains(newValue)) {
	System.out.println("已经存在："+Arrays.toString(newValue));
	continue;
}

第二次提交，结果：超时

原因：两个int类型数组使用 o.equals(e) 方法，得到的永远是false。

修改：将int类型数组改为String字符串，就可以得到比较的结果。

使用两个linkedList，分别存储key和value。

LinkedListqueValue=new LinkedList();
LinkedListqueKey=new LinkedList();

第三次提交，结果：超时

依然超时，相较前一次，有提升。

原因：判断是否重复不够快。（可能吧）

修改：使用LinkedHashMap存储操作和操作的结果，Link的HashMap的containsKey()判断是否存在某个结果的的时间应该是比较快的。

并且，使用一个LinkedList存储 queKey照常使用，用于获取map队列的首个键值对，来达到队列的效果。

LinkedList<String> queKey=new LinkedList<String>();
HashMap<String, String> que=new LinkedHashMap<String, String>();

第四次提交，结果：通过

代码：

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {

	/**
	 * @param args
	 */

	public static String Answer="";
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		//输入
		for (int i = 0; i <4; i++) {
			Answer+=sc.next();
		}
		StringBuffer st=new StringBuffer();
		for (int i = 0; i < 4; i++) {
			st.insert(0, sc.next());
		}
		Answer+=st;
		
		//BFS
		LinkedListqueKey=new LinkedList();
		HashMapque=new LinkedHashMap();//map存储的内容为 结果 ，操作
		
		
		//添加一个起点
		queKey.add("12348765");
		que.put("12348765", "");
		
		while (true) {
			String key=queKey.poll();//结果
			String value=que.get(key);//操作
			
			if (key.equals(Answer)) {
				System.out.println(value.length());
				System.out.println(value);
				//System.out.println("key:"+key);//测试
				break;
			}
			for (int i = 0; i < 3; i++) {
				String newValue=value+(char)(i+65)+"";
				String newKey=change(i,key);//通过i的值，与原来的数组，得到新的数组。
				
				//如果在之前的基本操作中，已经到达了这个步骤，那么就不执行入队
				if (que.containsKey(newKey)) {
					//System.out.println("已经存在："+newKey);//测试
					continue;
				}
				
				//入队
				queKey.add(newKey);
				que.put(newKey, newValue);
			}
			
		}
		
		
}

	
//	“A”：交换上下两行；0
//	“B”：将最右边的一行插入最左边；1
//	“C”：魔板中央作顺时针旋转。2
	//根据指令，进行数组的改变
	public static String change(int opt,String str) {
		char []arr=str.toCharArray();
		char t='0';
		switch (opt) {
		case 0:
			t=arr[0];arr[0]=arr[4];arr[4]=t;
			t=arr[1];arr[1]=arr[5];arr[5]=t;
			t=arr[2];arr[2]=arr[6];arr[6]=t;
			t=arr[3];arr[3]=arr[7];arr[7]=t;
			break;
		case 1:
			t=arr[3];
			arr[3]=arr[2];
			arr[2]=arr[1];
			arr[1]=arr[0];
			arr[0]=t;
			
			t=arr[7];
			arr[7]=arr[6];
			arr[6]=arr[5];
			arr[5]=arr[4];
			arr[4]=t;
			break;
		case 2:
			t=arr[1];
			arr[1]=arr[5];
			arr[5]=arr[6];
			arr[6]=arr[2];
			arr[2]=t;
	break;
		default:
			break;
		}
		return String.valueOf(arr);
	}
	
}