八数码

845. 八数码

在一个 3×3的网格中，1∼8 这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。
例如：

1 2 3
x 4 6
7 5 8

在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。
我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
4 5 6
7 8 x

例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下：

1 2 3   1 2 3   1 2 3   1 2 3
x 4 6   4 x 6   4 5 6   4 5 6
7 5 8   7 5 8   7 x 8   7 8 x

现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。
输入格式
输入占一行，将 3×3 的初始网格描绘出来。
例如，如果初始网格如下所示：

1 2 3 
x 4 6 
7 5 8

则输入为：1 2 3 x 4 6 7 5 8
输出格式
输出占一行，包含一个整数，表示最少交换次数。
如果不存在解决方案，则输出 −1。
输入样例：

2  3  4  1  5  x  7  6  8

输出样例

19

思路：

类型：最短路径问题
重点：将其看作一个整体，从初始状态经过变换到最终状态的过程。

import java.util.*;
public class Main {
    static final String end = "12345678x";
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < 9; i++) {
            str.append(sc.next());
        }
        System.out.println(bfs(str.toString(), end));
    }
    static int bfs(String start, String end) {
        Map<String, Integer> map = new HashMap<>();
        map.put(start, 0);
        Queue<String> q = new LinkedList<>();
        q.offer(start);
        int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
        while (!q.isEmpty()) {
            String cur = q.poll();
            if (cur.equals(end)) break;
            char[] chars = cur.toCharArray();
            int index = cur.indexOf('x');
            int a = index / 3, b = index % 3;
            for (int i = 0; i < dx.length; i++) {
                int x = a + dx[i], y = b + dy[i];
                if (x >= 0 && x < 3 && y >= 0 && y < 3) {
                    swap(chars, index, x * 3 + y);
                    String tmp = new String(chars);
                    if (map.get(tmp) == null) {
                        int count = map.get(cur);
                        map.put(tmp, count + 1);
                        q.offer(tmp);
                    }
                    swap(chars, index, x * 3 + y);
                }
            }
        }
        if (map.get(end) == null) return -1;
        else return map.get(end);
    }
    static void swap(char[] ch, int i, int j) {
        char tmp = ch[i];
        ch[i] = ch[j];
        ch[j] = tmp;
    }
}