AC代码

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

class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String st = in.readLine().replace(" ", "");
        System.out.println(bfs(st));
    }

    static int bfs(String st){
        LinkedList<String> list = new LinkedList<>();
        list.add(st);
        HashMap<String, Integer> hmp = new HashMap<>();
        hmp.put(st, 0);

        int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};

        while(!list.isEmpty()){
            String t = list.poll();//poll()方法,返回链表第一个元素并删除
            int dist = hmp.get(t);
            if(t.equals("12345678x")) return dist;

            int k = t.indexOf("x");
            int x = k / 3, y = k % 3;

            for(int i = 0;i < 4;i ++){
                int a = x + dx[i],y = y + dy[i];
                if(a<0 || a>2 || b<0 || b>=3) continue;
                String newstr = swap(t, k, a*3+b);
                if(hmp.containsKey(newstr))  continue;
                hmp.put(newstr, dist + 1);
                list.add(newstr);
            }
        }

        return -1;
    }

    static String swap(String t, int a, int b){
        StringBuffer sb = new StringBuffer(t);
        char ch = sb.charAt(a);
        char ch2 = sb.charAt(b);
        sb.setCharAt(b, ch);
        sb.setCharAt(a, ch2);
        return sb.toString();
    }
}