java 代码

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

class Main{
    static ArrayDeque<String> q = new ArrayDeque<String>();
    static HashMap<String, Integer> d = new HashMap<>();
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
    static int bfs(String start){
        q.offer(start);
        d.put(start, 0);
        String end = "12345678x";
        while(q.size() != 0){
            String str = q.poll();
            int dist = d.get(str);
            if(str.equals(end)){
                return dist;
            }
            int k = str.indexOf("x");
            int x = k / 3, y = k % 3;
            //状态转移
            for(int i = 0; i < 4; ++i){
                int a = x + dx[i], b = y + dy[i];
                if(a >= 0 && a < 3 && b >= 0 && b < 3){
                    char[] chs = str.toCharArray();
                    char ch = chs[k];
                    chs[k] = chs[a * 3 + b];
                    chs[a * 3 + b] = ch;
                    String str_new = String.valueOf(chs);
                    if(!d.containsKey(str_new)){
                        d.put(str_new, dist + 1);
                        q.offer(str_new);
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args)throws Exception{
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        String str = buf.readLine().replace(" ","");
        System.out.print(bfs(str));
    }
}