拼图（偷的大神的代码

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;
import java.util.ArrayList;
import java.lang.StringBuilder;

//广度优先
public class Main{

     //目标序列
    public static String destNumbers = "123456780";
    //已计算Set，用来判断哪些位置已经移动到过
    public static Set<Integer> set = new HashSet<Integer>();
     
    //0在每一位置的可移动(交换)规则[上(1) 左(2) 右(4) 下(8),位或关系]
    public static int[]moveTable = new int[]{12,14,10,13,15,11,5,7,3};

    
    /*
    上(1) 左(2) 右(4) 下(8)
    0 -> 右 下(12)
    1 -> 左 右 下(14)
    2 -> 左 下(10)
    3 -> 上 右 下(13)
    4 -> 上 左 下 右(15)
    5 -> 上 左 下(11)
    6 -> 上 右(5)
    7 -> 左 上 右(7)
    8 -> 上 左(3)
    */
    //moveStatus 上(1) 左(2) 右(4) 下(8)
    public static ArrayList<Node> getNextMoveList(Node pNode){
 
        int position = pNode.numbers.indexOf("0");
        int moveStatus = moveTable[position];
        ArrayList<Node> cNodes = new ArrayList<Node>();
 
 
        for(int status=1; status <=8; status=status<<1){
            if((moveStatus & status) > 0){
                char[] charNumbers = pNode.numbers.toCharArray();
                int switchPosition = 0;
                if(status == 1){//上
                   switchPosition = position - 3;
                } else if(status == 2){//左
                   switchPosition = position - 1;
                } else if(status == 4){//右
                   switchPosition = position + 1;
                } else if(status == 8){//下
                   switchPosition = position + 3;
                }
                charNumbers[position] = charNumbers[switchPosition];
                charNumbers[switchPosition] = '0';
                String s = String.valueOf(charNumbers);
                //判断此序列未出现过
                if(!set.contains(Integer.valueOf(s))){
                    set.add(Integer.valueOf(s));
                    Node n = new Node(pNode, s, charNumbers[position]);
                    cNodes.add(n);
                }
            }
        }
        return cNodes;
    }

    /*请完成下面这个函数，实现题目要求的功能*/
    /*当然，你也可以不按照下面这个模板来作答，完全按照自己的想法来 ^-^ */
    /******************************开始写代码******************************/

    //输出结果
    static int getResult(Node node){
        String result = "";
        while(node.parentNode != null){
            result += node.currentNum;
            node = node.parentNode;
        }
        return new StringBuffer(result).reverse().toString().length();
    }

    static int run(String numbers){
		if(numbers.equals(destNumbers)){
            //无需移动
            return 0;
        }
        ArrayList<Node> numsList = new ArrayList<Node>();
        //初始化根节点
        numsList.add(new Node(null, numbers, ' '));
        while(numsList.size() > 0){
            //广度优先每层的tmpList
            ArrayList<Node> tmpList = new ArrayList<Node>();
 
            for(Node pNode : numsList){
                ArrayList<Node> cNodes = getNextMoveList(pNode);
 
                for(Node cNode : cNodes){
                    if(cNode.numbers.equals(destNumbers)){
                        //返回步数
                        return getResult(cNode);
                     }
                    tmpList.add(cNode);
                }
            }
 
            numsList = tmpList;
        }
        //无解
        return -1;
    }
   /******************************结束写代码******************************/

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
      
        String numbers = new String();
        for(int rows=3; rows>0; rows--){
            for(String n: scan.nextLine().split(" ")){
                numbers += n;
            }
        }
 
        int res = run(numbers);
      
        System.out.println(String.valueOf(res));
    }
}


//节点类
class Node {
    public Node(Node parentNode, String numbers, char currentNum){
        this.numbers = numbers;
        this.currentNum = currentNum;
        this.parentNode = parentNode;
    }
    public char currentNum;            //节点当前移动的数字
    public String numbers;    //当前数字序列字符
    public Node parentNode;           //父节点
}