魔板:
Problem Description
在魔方风靡全球之后不久，Rubik先生发明了它的简化版——魔板。魔板由8个同样大小的方块组成，每个方块颜色均不相同，可用数字1-8分别表示。任一时刻魔板的状态可用方块的颜色序列表示：从魔板的左上角开始，按顺时针方向依次写下各方块的颜色代号，所得到的数字序列即可表示此时魔板的状态。例如，序列(1,2,3,4,5,6,7,8)表示魔板状态为：
1 2 3 4
8 7 6 5
对于魔板，可施加三种不同的操作，具体操作方法如下：
A: 上下两行互换,如上图可变换为状态87654321
B: 每行同时循环右移一格,如上图可变换为41236785
C: 中间4个方块顺时针旋转一格,如上图可变换为17245368
给你魔板的初始状态与目标状态，请给出由初态到目态变换数最少的变换步骤，若有多种变换方案则取字典序最小的那种。
Input
每组测试数据包括两行，分别代表魔板的初态与目态。
Output
对每组测试数据输出满足题意的变换步骤。
Sample Input
12345678
17245368
12345678
82754631
Sample Output
C
AC
分析核心：映射，bfs，康托（康托只是一个工具）
1：刚开始的做法：把没输入的两行当作字符串，写出函数ABC的操作过程，然后每输入一个数就把他当作初态然后运行bfs。输出结果。当然，肯定是要标记进行bfs的。我就建立了boolean【88888888】数组对其标记，结果：wa
2：后来参考了别人的做法：首先把字符串的处理变成char【】数组的处理。我发现别人都用康托展开。后来想了一下，这八个数的排列是有顺序并且没有重复的，总共就8！种情况，我用了88888888数组明显造成资源浪费。然后就学习了下康托展开。对于康托，只是一种表示的工具，可以看作是一种巧妙的数据结构，但是不是算法。
附上康托展开实现
static int kangtuo(char a[])//转化为康托展开的值 { int jiecheng[]= {1,1,2,6,24,120,720,5040}; int m=0,n=0; for(int i=0;i<8;i ) { m=0; for(int j=i 1;j<8;j ) { if(a[i]>a[j])m ; } n =m*jiecheng[7-i]; } return n; }
这样就可以用40321个数表示所有能出现的情况，而不需要88888888个。但是结果还是wa
3：请教学长之后，想到了用映射。就是跑一遍bfs，而不是跑多遍bfs，一遍bfs记录所有的结果，你或许会问初态不一样，终态不一样怎么办，你要转化，把所有的初态转化成12245678，所有终态转化为对应数字，直接输入对应的记录过的结果，简而言之就是我后面输入输出，我只在意他位置的变化，而不是数字的变化，举个简单例子，如果输入的是321，213，你可以看到第一个数3跑到第三位上，2跑到第一位上，1跑到第二位上，（这里就是把三看成1，把2看成2，把1看成3）他的执行步骤其实和123跑到231，看看两组数组的位置是否对应一样。理解这个就可以了。
附上代码如下：
import java.util.ArrayDeque; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class 杭电1430 { static int jiecheng[]= {1,1,2,6,24,120,720,5040}; public static void main(String[] args) { Scanner sc=new Scanner(System.in); int jud[]=new int[40321]; String path[]=new String[40321]; char start[]= {'1','2','3','4','5','6','7','8'}; path[kangtuo(start)]="";//初始第一个数组元素是""而不是null Queueq1=new ArrayDeque(); q1.add(start); while(!q1.isEmpty()) { char t2[]=q1.poll(); //去头并返回 int exam=kangtuo(t2);//当前的康托展开值 jud[exam]=1; { char p1[]=a(t2);int kang=kangtuo(p1);//分别走三部并且判断是否可走 if(jud[kang]==0) {q1.add(p1);path[kang]=path[exam] 'A';jud[kang]=1; } char p2[]=b(t2); kang=kangtuo(p2); if(jud[kang]==0) {q1.add(p2);path[kang]=path[exam] 'B'; jud[kang]=1;} char p3[]=c(t2); kang=kangtuo(p3); if(jud[kang]==0) {q1.add(p3);path[kang]=path[exam] 'C';jud[kang]=1; } } } while(sc.hasNextLine()) { String c=sc.nextLine();//初始状态 String d=sc.nextLine();//结束状态 char c1[]=c.toCharArray(); char d1[]=d.toCharArray();//转化为字符数组 d1= zhuanhua(c1,d1); System.out.println(path[kangtuo(d1)]); } } private static char[] zhuanhua(char[] c1, char[] d1) { for(int i=0;i<8;i ) { for(int j=0;j<8;j ) {if(d1[i]==c1[j]) {d1[i]=(char) (j 1 '0');break;}} } return d1; } static int kangtuo(char a[])//转化为康托展开的值 { int m=0,n=0; for(int i=0;i<8;i ) { m=0; for(int j=i 1;j<8;j ) { if(a[i]>a[j])m ; } n =m*jiecheng[7-i]; } return n; } static void swap(char a[],int b,int c) { char tem=a[b]; a[b]=a[c]; a[c]=tem; } private static char[] a(char b[])//a的实现方法 { char a[]=b.clone();//赋值b数组不改变b数组 swap(a,0,7); swap(a,1,6); swap(a,2,5); swap(a,3,4); return a; } static char[] b(char b[]) { char a[]=b.clone(); swap(a,3,2); swap(a,2,1); swap(a,1,0); swap(a,4,5); swap(a,5,6); swap(a,6,7); return a; } static char[] c(char b[]) { char a[]=b.clone(); swap(a,1,6); swap(a,2,6); swap(a,5,6); return a; } }
康托只是一种工具，其中映射的道理，减少bfs的次数。才是最重要的。
