在九宫格里放在1到8共8个数字还有一个是空格，与空格相邻的数字可以移动到空格的位置，问给定的状态最少需要几步能到达目标状态（用0表示格）：
120345678
输入一个给定的状态。
输出输出到达目标状态的最小步数。不能到达时输出-1。
输入样例012345678
输出样例2
public class Node {
private int state;
private Node parent;
private int value;
private int depth;
public int getState() {
return state;
}
public void setState(int state) {
this.state = state;
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public int getDepth() {
return depth;
}
public void setDepth(int depth) {
this.depth = depth;
}
public class astarEight {
static Comparator cmp = new Comparator() {
//按照value值和Depth值最小的方式构造优先队列
@Override
public int compare(Node n1, Node n2) {
// TODO Auto-generated method stub
return (n1.getDepth() + n1.getValue()) - (n2.getDepth() + n2.getValue());
}
};
static Queue openTable = new PriorityQueue<>(cmp); //用优先队列存储open表
static Deque closeTable = new linkedList<>(); //close表
static Stack path = new Stack(); //用栈来存储路径
static Map vis = new HashMap<>(); //用来存储遍历过的状态
static int r; // 行
static int c; // 列
static int[][] mat = new int[3][3]; // 将一个九位整数转化为一个3X3的矩阵
static int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }; // 上、下、左、右
public static void main(String[] args) {
// TODO Auto-generated method stub
int start, goal;
Scanner input = new Scanner(System.in);
start = input.nextInt(); //初始状态
goal = input.nextInt(); //目标状态
Node Nstart = new Node();
Node Ngoal = new Node();
//对初始状态和目标状态进行初始化
init(Nstart, Ngoal, start, goal);
//将初始状态入队列
openTable.add(Nstart);
while (true) {
closeTable.add(openTable.peek()); //将open表中优先级最高的放入close表中
vis.put(start, 1); //保存出现过的状态
openTable.poll();//将open表中优先级最高的元素删除
if (closeTable.peekLast().getState() == goal) { //如果当前状态与目标状态相同，退出循环
break;
} else {
//扩展子节点
extendNode(closeTable.peekLast(), Ngoal);
}
}
Node tmpNode = new Node();
tmpNode = closeTable.peekLast(); //返回close表中最后一个元素
while (tmpNode.getParent() != null) {
path.add(tmpNode);
tmpNode = tmpNode.getParent(); //找父节点
}
path.add(tmpNode);
System.out.println(path.size()-1);
while (path.size() > 0) {
Node t = (Node) path.peek();
System.out.println(t.getState());
path.pop();
}
}
//计算估计函数值，函数值由曼哈顿距离与深度之和确定
public static int value(Node s, Node g) {
int count = 0;
int start = s.getState();
int goal = g.getState();
int[][] begin = new int[3][3];
int[][] end = new int[3][3];
for (int i = 2; i >= 0; i--) {
for (int j = 2; j >= 0; j--) {
begin[i][j] = start % 10;
start = start / 10;
end[i][j] = goal % 10;
goal = goal / 10;
}
}
for (int i = 0; i < 3; i++) // 检查当前图形的正确度
for (int j = 0; j < 3; j++) {
if (begin[i][j] != end[i][j]) {
for (int k = 0; k < 3; k++)
for (int w = 0; w < 3; w++)
if (begin[i][j] == end[k][w])
//计算曼哈顿距离
count = (int) (count + Math.abs(i - k * 1.0) + Math.abs(j - w * 1.0)); // 累加计算每个数字当前状态与最终状态的曼哈顿距离
} else {
continue;
}
}
return count + s.getDepth();
}
//扩展子节点
public static void extendNode(Node S, Node G) {
for (int i = 0; i < 4; i++) {
if (judge(S, i)) {
int t = 0;
Node tmp = new Node();
int ur = r + dir[i][0];
int uc = c + dir[i][1];
mat[r][c] = mat[ur][uc];
mat[ur][uc] = 0;
for (int j = 0; j < 3; j++) {
for (int z = 0; z < 3; z++) {
t = t * 10 + mat[j][z];
}
}
if (vis.get(t) == null) {
tmp.setState(t);
tmp.setDepth(S.getDepth() + 1);
tmp.setValue(value(tmp, G));
tmp.setParent(S);
// System.out.println(tmp.getState());
openTable.add(tmp);
} else {
continue;
}
}
}
}
// 判断该状态是都可行
public static boolean judge(Node u, int d) {
int t = u.getState();
for (int i = 2; i >= 0; i--) {
for (int j = 2; j >= 0; j--) {
mat[i][j] = t % 10;
t = t / 10;
if (mat[i][j] == 0) {
r = i;
c = j;
}
}
}
// 判断四个方向
if ((d == 0 && r == 0) || (d == 1 && r == 2) || (d == 2 && c == 0) || (d == 3 && c == 2))
return false;
return true;
}
//对初始状态和目标状态进行初始化
public static void init(Node S, Node G, int start, int goal) {
S.setParent(null);
S.setDepth(0);
S.setValue(0);
S.setState(start);
G.setParent(null);
G.setDepth(0);
G.setValue(0);
G.setState(goal);
}
