杭电1043java实现bfs一遍

题目Eight
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; }
	
}


  

 

  
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
  
96
  
97
  
98
  
99
  
100
  
101
  
102
  
103
  
104
  
105
  
106
  
107
  
108
  
109
  
110
  
111
  
112
  
113
  
114
  
115
  
116
  
117
  
118
 

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

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