Acwing 845

这道题实际上最主要是要理解如何把整个3x3的矩阵转化为一个最小路径的图。然后用bfs来解决。
其实核心关键就在于每次尝试换x和它周围的一个数字的时候，你要记录这次是否之前换过，并且距离是多少（距离就是bfs第一次换到的地方，因为bfs本身就带有最短路径的属性）
想到这点就能够通过map来记录每次交换的距离并且之前是否交换过了。然后如果交换到了“12345678x”这个最终节点，那就输出答案，否则遍历所有节点后还没到最终节点就表示换不到，输出-1
下面是代码：

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

public class Main {
    public static void main(String[] arg) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] in = br.readLine().split(" ");
        String start = "";
        for (String s : in) start += s;
        System.out.print(bfs(start));
    }
    static int bfs(String s) {
        int[][] dirs = new int[][] {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
        String end = "12345678x";
        Queue<String> q = new LinkedList<>();
        Map<String, Integer> map = new HashMap<>();
        map.put(s,0);
        q.add(s);
        while (!q.isEmpty()) {
            String cur = q.poll();
            int distance = map.get(cur);
            if (cur.equals(end)) return distance;
            char[] cArr = cur.toCharArray();
            int num = cur.indexOf('x');
            int i = num / 3, j = num % 3;
            for (int[] dir : dirs) {
                int x = i + dir[0], y = j + dir[1];
                if (x >= 0 && x < 3 && y >= 0 && y < 3) {
                    char temp = cArr[num];
                    cArr[num] = cArr[x * 3 + y];
                    cArr[x * 3 + y] = temp;
                    String nString = new String(cArr);
                    if (!map.containsKey(nString)) {
                        map.put(nString, distance + 1);
                        q.add(nString);
                    }
                    temp = cArr[num];
                    cArr[num] = cArr[x * 3 + y];
                    cArr[x * 3 + y] = temp;
                }
            }
        }
        return -1;
    }
}