思路

1. bfs基本操作 将初始字符串start入队；并加入到map中；
2. bfs固定操作 从队首取元素str 进行操作；求出‘x’的索引index1
3. 根据x的索引k 求出 x在矩阵中的坐标 x，y
4. 四个方向延伸 得到新的坐标 newX newY；并你转化为 index2索引；
5. 交换index1与index2处的字符 得到新的字符串
   6.检查新的newStr 以及更新 map 以及 入队操作

import java.util.*;
public class Main{
    static Queue<String>q=new LinkedList();
    static Map<String,Integer>map=new HashMap();
    static String end="12345678x";
    static int []dx={-1,0,1,0};
    static  int []dy={0,-1,0,1};

    //字符串交换两个位置并得到新的字符串 使用char[]中间转换
    static String getNewStr(String str,int k,int t){
        char []cs=str.toCharArray();
        char c=cs[t];
        cs[k]=c;
        cs[t]='x';
        return new String(cs);
    }

    static int bfs(String start){
        //初始化 队列和map
        q.add(start);
        map.put(start,0);

        //bfs 步骤  非空 进行操作
        while(!q.isEmpty()){
            String t=q.poll();
            //找到直接返回
            if(t.equals(end))return map.get(t);
            //1、找出x的索引
            int k=t.indexOf('x');
            //2、根据索引求出 x在矩阵中的下标
            int x=k/3;int y=k%3;
            //3、四个方向延伸；
            for(int i=0;i<4;i++){
                int a=x+dx[i];
                int b=y+dy[i];
                //越界之后直接退出
                if(a<0||a>2||b<0||b>2)continue;
                //4、延伸之后 交换字符 构成新的字符串；
                String newStr=getNewStr(t,k,3*a+b);
                //如果map中不含有 该字符串 就加到map  并入队
                if(!map.containsKey(newStr)){
                    map.put(newStr,map.get(t)+1);
                    q.add(newStr);
                }
            }

        }
        return -1;
    }

    public static void main(String[]args){
        Scanner sc=new Scanner (System.in);
        String str=sc.nextLine().replaceAll(" ","");
        System.out.println(bfs(str));
    }
}