Problem Description
这个15难题已经存在了100多年了，即使你不知道它的名字，你也看到了。它由15个滑动瓦片构成，每个滑动瓦片的数量从1到15，并且全部装入4乘4帧，缺少一个瓦片。我们称之为缺失的瓦片’x’;难题的目的是安排瓷砖，以便它们按以下顺序排列：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 x
其中唯一合法的操作是与其共享边缘的一个瓷砖交换’x’。作为一个例子，下面的一系列动作解决了一个稍微混乱的难题：
1 2 3 4 -> 1 2 3 4 -> 1 2 3 4 -> 1 2 3 4
5 6 7 8 -> 5 6 7 8 -> 5 6 7 8 -> 5 6 7 8
9 x 10 12 -> 9 10 x 12 -> 9 10 11 12 -> 9 10 11 12
13 14 11 15 -> 13 14 11 15 -> 13 14 x 15 -> 13 14 15 x
r-> d-> r->
上一行中的字母表示每个步骤中’x’瓦片的哪个邻居与’x’瓦片交换;法律价值分别为’r’，‘l’，‘u’和’d’，分别为正，左，上和下。
并非所有的谜题都可以解决;在1870年，一个名叫萨姆·洛伊德的人因发布了一个难以解决的难题而闻名
挫败了很多人。事实上，只需要交换两块拼块（当然，不包括缺失的“x”拼块），您所需要做的就是拼成一个难以解决的难题。
在这个问题中，你将编写一个程序来解决不太知名的8拼图，它是由3×3的拼图组成的安排。
输入
您将收到有关8拼图配置的几个说明。一个描述只是一个在其初始位置的图块列表，其中行从上到下列出，并且在一行内从左到右列出图块，其中图块由数字1到8表示，再加上’x’ 。例如，这个难题
1 2 3
x 4 6
7 5 8
is described by this list:
1 2 3 x 4 6 7 5 8
Output
如果拼图没有解决方案，或者将完全由字母’r’，‘l’，'u’和’d’组成的字符串描述为一系列移动产生一个解决方案。该字符串不应包含空格，并从行首开始。不要在案件之间打印空行。
Sample Input
2 3 4 1 5 x 7 6 8
Sample Output
ullddrurdllurdruldr
问题分析：
因为有多组测试数据，我使用的是bfs 康托，bfs跑一遍，遍历所有情况，然后输出输入的值，我把初始数组变为123456789，因为输入的x和9在字符串大小是等效的。值得注意的是路径要倒着写，因为我们走的过程是取反过程。还有注意的是一维二维数组的转换，计算康托值用一维数组，但是移动要变成二维注意Java的对象克隆，不然你的数组会被更改。
还有大佬用A*和双向bfs的可以了解下。方法也很巧妙。
贴上代码
import java.util.ArrayDeque; import java.util.Queue; import java.util.Scanner; public class 杭电1043 { static int jiecheng[]= {1,1,2,6,24,120,720,5040,40320}; public static void main(String[] args) { Scanner sc=new Scanner(System.in); char start[][]= {{'1','2','3'},{'4','5','6'},{'7','8','9'}}; //初始状态 int judgel[]=new int[362880];//标记 String path []=new String [362880];//记录路径 Queue q1=new ArrayDeque(); judgel[0]=1;path[0]="";//初始化（0到0要特殊处理） q1.add(start);//入队 while(!q1.isEmpty()) { char[][]exa=q1.poll(); int kang=kangtuo(exa);//对应的位置; int x1=0,y1=0; for(int i=0;i<3;i )//找打'x'（9）的位置 { for(int j=0;j<3;j ) { if(exa[i][j]=='9') {x1=i;y1=j;} } } int k2=0; //执行bfs {char[][]t2=r(exa,x1,y1); k2=kangtuo(t2);if(judgel[k2]==0) {q1.add(t2);path[k2]='l' path[kang];judgel[k2]=1;}} {char[][]t1=l(exa,x1,y1); k2=kangtuo(t1);if(judgel[k2]==0) {q1.add(t1);path[k2]='r' path[kang];judgel[k2]=1;}} {char[][]t4=down(exa,x1,y1); k2=kangtuo(t4);if(judgel[k2]==0) {q1.add(t4);path[k2]='u' path[kang];judgel[k2]=1;}} {char[][]t3=up(exa,x1,y1); k2=kangtuo(t3);if(judgel[k2]==0) {q1.add(t3);path[k2]='d' path[kang];judgel[k2]=1;}} } while(sc.hasNextLine()) { String a=sc.nextLine(); String a2[]=a.split(" "); char c[][]=new char[3][3]; for(int i=0;i<9;i ) { c[i/3][i%3]=a2[i].charAt(0); } String value=path[kangtuo(c)];//直接输出保存过的值 if(value==null) {System.out.println("unsolvable"); } else if(value=="") {System.out.println("lr");} else System.out.println(value); } } static int kangtuo(char[][] start) { int m=0;int n=0; char b[]=new char[9]; for(int i=0;i<3;i ) { for(int j=0;j<3;j ) b[i*3 j]=start[i][j]; } for(int i=0;i<9;i ) { m=0; for(int j=i 1;j<9;j ) { if(b[i]>b[j])m ; } n =m*jiecheng[8-i]; } return n; } static char[][] l (char a[][],int x1,int y1) { char b[][]=new char[3][3]; b[0]=a[0].clone(); b[1]=a[1].clone(); b[2]=a[2].clone(); if(y1>0) { char team=b[x1][y1]; b[x1][y1]=b[x1][y1-1]; b[x1][y1-1]=team;} return b; } static char[][] r (char a[][],int x1,int y1) { char b[][]=new char[3][3]; b[0]=a[0].clone(); b[1]=a[1].clone(); b[2]=a[2].clone(); if(y1<2) { char team=b[x1][y1]; b[x1][y1]=b[x1][y1 1]; b[x1][y1 1]=team;} return b; } static char[][] up (char a[][],int x1,int y1) { char b[][]=new char[3][3]; b[0]=a[0].clone(); b[1]=a[1].clone(); b[2]=a[2].clone(); if(x1==1||x1==2) { char team=b[x1][y1]; b[x1][y1]=b[x1-1][y1]; b[x1-1][y1]=team;} return b; } static char[][] down (char a[][],int x1,int y1) { char b[][]=new char[3][3]; b[0]=a[0].clone(); b[1]=a[1].clone(); b[2]=a[2].clone(); if(x1==0||x1==1) { char team=b[x1][y1]; b[x1][y1]=b[x1 1][y1]; b[x1 1][y1]=team;} return b; } }
