八数码

算法思想

算法模板

import java.util .*;

public class Main {
    static int N = 10;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String start = "";
        for (int i = 0; i < 9; i++) start += sc.next();
        System.out.println(bfs(start));
    }

    // state 代表迷宫的状态
    public static int bfs(String state) {
        // q[]存储迷宫的每个状态
        Queue<String> q = new LinkedList<>();
        // d[]存储每个状态距离开始状态的距离（移动次数）
        Map<String, Integer> d = new HashMap<>();
        String end = "12345678x";

        d.put(state, 0);

        q.offer(state);

        while (!q.isEmpty())
        {
            String t = q.poll();
            if (t.equals(end)) return d.get(t);
            
            int distance = d.get(t);
            // 一维索引转化为二维索引
            int index = t.indexOf('x');
            int x = index / 3, y = index % 3;
            // 上下左右四个方向
            int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};

            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)
                {
                    // 移动 x 得到一个新的状态
                    String nState = swapChars(index, a * 3 + b, t);
                    // 若状态已经出现过，则过滤掉
                    if(!d.containsKey(nState))
                    {
                        d.put(nState, distance + 1);
                        q.offer(nState);
                    }
                }
            }
        }

        return -1;
    }

    public static String swapChars(int i, int j, String str) {
        if (i == j) return str;

        char[] cs = str.toCharArray();
        char tmp = cs[i];
        cs[i] = cs[j];
        cs[j] = tmp;

        return new String(cs);
    }
}