$$\color{Red}{八数码——三种语言——最小步数模型}$$

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

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

一维数组和二维数组的坐标相互转换

这里以3 * 3的数组举例
 int x = k / 3, y = k % 3;//一维数组转换二维数组坐标
 int z = x * 3 + y;       //二维数组转换一维数组坐标

java bfs优先队列优化

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

public class Main {

    static String start = "";
    static String end = "12345678x";
    static HashMap<String, Integer> d = new HashMap<>();

    static void swap(char[] a, int x, int y) {
        char temp = a[x];
        a[x] = a[y];
        a[y] = temp;
    }

    static class Node {
        String str;
        Integer cnt;

        public Node(String str, Integer cnt) {
            this.str = str;
            this.cnt = cnt;
        }
    }

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

    static int bfs() {
        PriorityQueue<Node> heap = new PriorityQueue<>((o1, o2) -> o1.cnt - o2.cnt);
        heap.add(new Node(start, 0));
        d.put(start, 0);
        int[] dx = new int[]{-1, 0, 1, 0}, dy = new int[]{0, 1, 0, -1};

        while (!heap.isEmpty()) {
            Node peek = heap.poll();
            if (peek.str.equals(end)) return d.get(end);
            int index = peek.str.indexOf("x");
            int x = index / 3, y = index % 3;
            for (int i = 0; i < 4; i++) {
                char[] c = peek.str.toCharArray();
                int a = x + dx[i], b = y + dy[i];
                if (a < 0 || a >= 3 || b < 0 || b >= 3) continue;
                swap(c, index, a * 3 + b);
                String str = new String(c);
                if(!d.containsKey(str)){
                    heap.add(new Node(str, peek.cnt + 1));
                    d.put(str, peek.cnt + 1);
                }
            }
        }
        return -1;
    }


    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        String seq = "";
        for (int i = 0; i < s1.length; i++) {
            start += s1[i];
            if (!s1[i].equals("x")) seq += s1[i];
        }
        int cnt = 0;
        for (int i = 0; i < seq.length(); i++)
            for (int j = i + 1; j < seq.length(); j++)
                if ((int) seq.charAt(i) > (int) seq.charAt(j)) cnt++;
        if (cnt % 2 !=0) System.out.println(-1);
        else System.out.println(bfs());
    }
}

java bfs深搜

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> map = new HashMap<>();
    static LinkedList<String> q = new LinkedList<>();
    static String end = "12345678x";

    static void swap(char[] a, int i, int j) {
        char temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    static void bfs(String start, String end) {
        int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
        map.put(start, 0);
        q.add(start);
        while (!q.isEmpty()) {
            String t = q.pop();
            if (t.equals(end)) {
                System.out.println(map.get(end));
                return;
            }
            int index = t.indexOf('x');
            int x = index / 3, y = index % 3;
            for (int i = 0; i < 4; i++) {
                char[] chars = t.toCharArray();
                int a = x + dx[i], b = y + dy[i];
                if (a < 0 || a >= 3 || b < 0 || b >= 3) continue;
                swap(chars, index, a * 3 + b);
                String str = new String(chars);
                if (map.get(str) == null){
                    map.put(str, map.get(t) + 1);
                    q.add(str);
                }
            }
        }
        System.out.println(-1);
    }

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

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

        bfs(start, end);
    }
}

python3 代码

from collections import deque
dist = {}
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def bfs(st):
    dist[st] = 0
    q = deque([st])
    ed = '12345678x'

    while q:
        h = q.popleft()
        distance = dist[h]  #预保存当前步数
        if h == ed:
            return distance #找寻到答案则返回

        idx = h.find('x')    #预报存x的索引位置
        a = idx // 3
        b = idx % 3    #转化为二维位置
        for i in range(4):
            x = dx[i] + a
            y = dy[i] + b
            if 0 <= x < 3 and 0 <= y < 3:
                #字符串不能通过索引交换字符，应该转化为列表
                h = list(h)
                h[idx], h[x * 3 + y] = h[x * 3 + y], h[idx]
                #列表转化为字符串的join函数
                h = ''.join(h)
                if h not in dist: #若从未入队才入队
                    dist[h] = distance + 1
                    q.append(h)
                h = list(h)
                h[idx], h[x * 3 + y] = h[x * 3 + y], h[idx]
                h = ''.join(h)
    #若无法走到则说明路径不存在
    return -1

if __name__ == '__main__':
    st = input().replace(' ', '')
    print(bfs(st))

C++ 代码

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <queue>

using namespace std;

int bfs(string start)
{
    queue<string> q;
    unordered_map<string, int> d;

    q.push(start);
    d[start] = 0;

    int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
    string end = "12345678x";

    while(q.size())
    {
        auto t = q.front();
        q.pop();
        //当第一次队头出现end的字符串
        //此时必为最近的解，返回他在哈希表对应的距离
        if(t == end) return d[t];

        //暂存t的距离，此题由于涉及到字符串的变形
        //t的值在中途会发生变化，虽然每次距离赋值后会变回
        //但赋值时，没法表达原串的距离，所以这里暂存一下
        int distance = d[t];
        int k = t.find('x');

        //一维数组转换二维数组下标的方法
        int x = k / 3, y = k % 3;

        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)
            {
                swap(t[k], t[a * 3 + b]);
                if(!d.count(t))
                {
                    d[t] = distance + 1;
                    q.push(t);
                }
                //为了防止进入下一层for循环出现错误
                //还应将t变回最初取出的样子
                swap(t[k], t[a * 3 + b]);
            }
        }
    }
    //此时走出while说明此前并没有可以变为
    //end的子树，返回-1
    return -1;
}

int main()
{
    string start;
    for(int i=0; i<9; i++)
    {
        char s;
        cin >> s;
        start += s;
    }
    cout << bfs(start) << endl;
    return 0;
}