$$\color{Red}{魔板—最小步数模型}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

思路

我的八数码三种语言的题解

这道题可以说是八数码的强化升级版，难度在于首先转化的时候，第二行是倒序，这是关键，需要读清楚题目，所以字符串转化为二维的字符数组，需要进行第二行倒序。

而进行变化的三种情况，都不需要倒序考虑，直接进行转化，而转化回字符串，需要按之前的顺序恢复。

其次我们为了记录方案，还需要设置一个内部类，去定义每部操作下的上一步的字符串状态。

这道题的字典序顺序，从数学归纳法的角度，只需要每次搜答案都按字典序，并没有特殊需要判断的情况。

最终，为了记录字符操作的符号，需要进行字符转化，利用字符的ASCII码加减法即可。

JAVA

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

public class Main {
    static HashMap<String, Integer> dist = new HashMap<>();
    static HashMap<String, Node> pre = new HashMap<>();
    static LinkedList<String> q = new LinkedList<>();
    static char[][] g = new char[2][4];
    private static String start;
    private static String end;

    static class Node {
        char operate;
        String str;

        public Node(char operate, String str) {
            this.operate = operate;
            this.str = str;
        }
    }

    //将当前字符串转化到字符数组中
    public static void set(String str) {
        for (int i = 0; i < 4; i++) g[0][i] = str.charAt(i);
        for (int i = 0; i < 4; i++) g[1][i] = str.charAt(7 - i);
    }

    // 获取当前字符数组转化成的字符串
    public static String get() {
        String str = "";
        for (int i = 0; i < 4; i++) str += g[0][i];
        for (int i = 3; i >= 0; i--) str += g[1][i];
        return str;
    }

    // 操作A：上下两行交换
    public static String moveA(String str) {
        set(str);
        char[] temp = new char[4];
        for (int i = 0; i < 4; i++) {
            temp[i] = g[0][i];
            g[0][i] = g[1][i];
            g[1][i] = temp[i];
        }
        return get();
    }

    // 操作B：最右边一列插到左边
    public static String moveB(String str) {
        set(str);
        char a = g[0][3];
        char b = g[1][3];
        for (int i = 3; i > 0; i--) {
            g[0][i] = g[0][i - 1];
            g[1][i] = g[1][i - 1];
        }
        g[0][0] = a;
        g[1][0] = b;
        return get();
    }

    // 操作C：中间顺时针旋转
    public static String moveC(String str) {
        set(str);
        char temp = g[0][1];
        g[0][1] = g[1][1];
        g[1][1] = g[1][2];
        g[1][2] = g[0][2];
        g[0][2] = temp;
        return get();
    }

    public static int bfs(String start, String end) {
        if (start.equals(end)) return 0;
        dist.put(start, 0);
        q.add(start);
        while (!q.isEmpty()) {
            String t = q.pop();
            if (t.equals(end)) return dist.get(end);
            String[] str = new String[3];
            str[0] = moveA(t);
            str[1] = moveB(t);
            str[2] = moveC(t);
            for (int i = 0; i < 3; i++) {
                if (dist.containsKey(str[i])) continue;
                dist.put(str[i], dist.get(t) + 1);
                pre.put(str[i], new Node((char) (i + 'A'), t));
                q.add(str[i]);
            }
        }
        return -1;
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] s = br.readLine().split(" ");
        String end = "";
        for (int i = 0; i < s.length; i++) end += s[i];
        String start = "12345678";

        System.out.println(bfs(start, end));
        String res = "";
        String ans = end;
        while (!ans.equals(start)) {
            res += pre.get(ans).operate;
            ans = pre.get(ans).str;
        }
        for (int i = res.length() - 1; i >= 0; i--) {
            System.out.print(res.charAt(i));
        }
    }
}