标题：九宫重排
如图1的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成图2所示的局面。
我们把图1的局面记为：12345678.
把图2的局面记为：123.46758
显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。
例如：
输入数据为：
12345678.
123.46758
则,程序应该输出：
3
再如：
输入：
13524678.
46758123.
则，程序输出：
22
资源约定：
峰值内存消耗（含虚拟机） < 64M
CPU消耗 < 2000ms
bfs搜索的一道非常典型题目,写得有点啰嗦!!
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
| /**
*
*/
package D1;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Set;
/**
* @作者： gx_143
* @创建时间： 2017-5-19上午11:31:28
*/
public class T8 {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
String str=sc.nextLine();
String stop=sc.nextLine();
stop=stop.substring(0,3)+"@"+stop.substring(3,6)+"@"+stop.substring(6,9);
//System.out.println(stop);
char[] begin=new char[11];
int index=0,X=0;
for (int i = 0; i < begin.length; i++) {
if(i==3||i==7){
begin[i]='@';
}else{
begin[i]=str.charAt(index);
index++;
if(begin[i]=='.'){
X=i;
}
}
}
f(begin,stop,X);
}
/**
* @param begin
* @param stop
* @param x
*/
static int[] fx=new int[]{1,-1,4,-4};
private static void f(char[] begin, String stop, int x) {
Queue<Node> queue=new LinkedList<Node>();
Node node=new Node(begin,x,0);
Set testSet = new HashSet();
String start1=new String(begin);
queue.add(node);
testSet.add(start1);
while(!queue.isEmpty()){
Node notNode=queue.poll();
char[] ch=notNode.ch;
int xnext=notNode.x;
int sum=notNode.sum;
for (int i = 0; i < fx.length; i++) {
int next=xnext+fx[i];
if(next>=0&&next<11&&next!=3&&next!=7){
char[] cc=new char[11];
for (int j = 0; j < cc.length; j++) {
cc[j]=ch[j];
}
char t=cc[xnext];
cc[xnext]=cc[next];
cc[next]=t;
String sta=new String(cc);
int size1=testSet.size();
testSet.add(sta);
int size2=testSet.size();
if(size1!=size2){
Node newNode=new Node(cc,next,sum+1);
queue.add(newNode);
}
}
}
String start=new String(ch);
//System.out.println(start);
if(start.equals(stop)){
System.out.println(sum);
return;
}
}
}
public static class Node{
public char[] ch;
public int x;
public int sum;
public Node(char[] ch,int x,int sum){
this.ch=ch;
this.x=x;
this.sum=sum;
}
}
}
|