杭电1430康托 bfs（java）

魔板:
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; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
 

这样就可以用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;
	}		
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
 

康托只是一种工具，其中映射的道理，减少bfs的次数。才是最重要的。

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/79914365