变进制数散列
java实现，要比Map的String键快很多

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;


/**
 * @author Ryan
 * @data 2020/05/20 - 周三
 */
public class Main {
    private static int[] fact = new int[10];
    private static boolean[] visited;
    // fact[i] -> i!
    static {
        fact[0] = 1;
        for (int i = 1; i < fact.length; i++) {
            fact[i] = fact[i-1] * i;
        }
    }

    private static int bfs(String start, String end) {
        Queue<String> q = new LinkedList<>();
        q.add(start);
        int idx = permutation_hash(start.toCharArray(),9);
        visited[idx] = true;
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};
        int step = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int j = 0; j < size; j++) {
                String s = q.poll();
                if (s.equals(end)) {
                    return step;
                }
                int k = s.indexOf('x');
                int x = k / 3, y = k % 3;
                for (int i = 0; i < dx.length; i++) {
                    int x1 = x + dx[i], y1 = y + dy[i];
                    if (x1 >= 0 && x1 < 3 && y1 >= 0 && y1 < 3) {
                        char[] ch = s.toCharArray();
                        swap(ch, x1 * 3 + y1, k);
                        idx = permutation_hash(ch,9);
                        String newS = String.valueOf(ch);
                        if (!visited[idx]) {
                            q.offer(newS);
                            visited[idx] = true;
                        }
                    }
                }
            }
            step++;
        }
        return -1;
    }
    //求长度为n的字符串某种排列的哈希值
    private static int permutation_hash(char s[], int n) {
       int idx = 0;
        for (int i = 0; i < 9; i++) {
            int d = 0;
            for (int j = 0; j < i; j++) {
                if (s[j] > s[i]) {
                    d++;
                }
            }
            idx += fact[i] * d;
        }
        return idx;
    }

    private static void swap(char[] ch, int i, int j) {
        char c = ch[i];
        ch[i] = ch[j];
        ch[j] = c;
    }


    public static void main(String[] args) throws IOException {
        visited = new boolean[fact[9]];
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String start = s.replaceAll(" ", "");
        String end = "12345678x";
        System.out.println(bfs(start, end));
    }
}