题目描述

样例

import java.util.*;

class Main{
    //private static char[][] g = new char[3][3];
    private static int[] dirx = {-1, 1, 0, 0}, diry = {0, 0, -1, 1};
    private static Queue<String> q = new LinkedList<>();
    private static Map<String, Integer> map = new HashMap<>();
    public static String swap(String str, int posn, int posx){
       StringBuilder sbstr = new StringBuilder(str);
       String tt = String.valueOf(sbstr.charAt(posn));
       sbstr.replace(posx, posx + 1, tt);
       sbstr.replace(posn, posn + 1, "x");
       return sbstr.toString();
    }
    public static int bfs(String start){
        String end = "12345678x";
        q.offer(start);
        map.put(start, 0);
        while(q.size() > 0){
            String str = q.poll();
            int dist = map.get(str);
            if(str.equals(end)){
                return dist;
            }
            int t = str.indexOf('x');
            int x = t / 3;
            int y = t % 3;
            for(int i = 0; i < 4; i ++){
                int x0 = x + dirx[i];
                int y0 = y + diry[i];
                if(x0 >= 0 && x0 < 3 && y0 >= 0 && y0 < 3){
                    String ss = swap(str, x0 * 3 + y0, t);
                    if(!map.containsKey(ss)){
                        map.put(ss, dist + 1);
                        q.offer(ss);
                    }
                }
            }
        }
        return -1;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String start = sc.nextLine();
        start = start.replaceAll("\\s+", "");
        System.out.println(bfs(start));
    }
}