java中没有swap函数，也不能对字符串进行直接操作，所以改变x的位置的操作需要先转化为char数组，然后再手写swap函数，再用String的valueOf()方法将char数组转化为字符串保存

import java.util.*;
import java.io.*;

public class Main{
    //本题难点需要进行状态更新，每次变换x的位置时，需要把当前状态记录下来，防止下次再次遍历出现死循环
    //如果使用二维数组来保存数据，很难实现状态更新
    static int[][] dir = {{-1,0},{0,1},{1,0},{0,-1}};
    static Queue<String> qu = new LinkedList<String>();
    static Map<String, Integer> map = new HashMap<String, Integer>();
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String st = br.readLine().replace(" ", "");
        int stx=0,sty=0;
        System.out.print(bfs(st));
    }
    public static int bfs(String st){
        map.put(st, 0);
        qu.add(st);
        while(!qu.isEmpty()){
            st = qu.poll();
            if(st.equals("12345678x")) return map.get(st);
            int dis = map.get(st);
            int x = st.indexOf('x')/3;//将字符串转化为想象中的一个二维数组，记录x的横坐标
            int y = st.indexOf('x')%3;//将字符串转化为想象中的一个二维数组，记录x的纵坐标
            int xdis = st.indexOf('x');
            char[] sc = st.toCharArray();
            for(int i=0;i<4;i++){
                int newx = x+dir[i][0],newy = y+dir[i][1];
                if(newy<3&&newx>=0&&newx<3&&newy>=0){
                    char temp = sc[xdis];
                    sc[xdis]= sc[newx*3+newy];
                    sc[newx*3+newy] = temp;
                    if(!map.containsKey(String.valueOf(sc))) {//如果当前搜索的状态已经出现过那么久直接跳过，否则加入队列
                        map.put(String.valueOf(sc), dis+1);
                        qu.add(String.valueOf(sc));
                    }
                    temp = sc[xdis];
                    sc[xdis]= sc[newx*3+newy];
                    sc[newx*3+newy] = temp;
                }
            }
        }
        return -1;
    }
}