2022-10-25：在一个 2 * 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次 移动 定义为选择 0 与一个相邻的数字（上下左右）进行交换.

2022-10-25：在一个 2 * 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示,
以及一块空缺用 0 来表示。一次 移动 定义为选择 0 与一个相邻的数字（上下左右）进行交换.
最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
给出一个谜板的初始状态 board ，
返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
输入：board = [[1,2,3],[4,0,5]]。
输出：1。

答案2022-10-25：

力扣773。A*算法，曼哈顿距离。
经过测试，rust的运行速度和内存占用都是最优的，go次之，java再次之。c++运行速度比java还慢了。
这道题可以用穷举打表法。

代码用rust编写。代码如下：

use std::collections::HashSet;

impl Solution {

    pub fn sliding_puzzle(m: Vec<Vec<i32>>) -> i32 {

        unsafe {

            nexts = vec![0, 0, 0];

            let mut set: HashSet<i32> = HashSet::new();

            let from =

                m[0][0] * b6 + m[0][1] * b5 + m[0][2] * b4 + m[1][0] * b3 + m[1][1] * b2 + m[1][2];

            let mut heap = Vec::new();

            // [

            // 从from出发到达当前状态，已经走了几步，

            // 从当前状态到最终状态的估计距离

            // 当前状态是什么，用数字代表

            // ]

            heap.push(vec![0, Solution::distance(from), from]);

            let mut ans = -1;

            while heap.len() > 0 {

                heap.sort_by(|a, b| (b[0] + b[1]).cmp(&(a[0] + a[1])));

                let arr = heap.pop().unwrap();

                let distance = arr[0];

                let cur = arr[2];

                if set.contains(&cur) {

                    continue;

                }

                if cur == 123450 {

                    ans = distance;

                    break;

                }

                set.insert(cur);

                let next_size = Solution::nexts(cur);

                for i in 0..next_size {

                    let next = nexts[i as usize];

                    if !set.contains(&next) {

                        heap.push(vec![distance + 1, Solution::distance(next), next]);

                    }

                }

            }

            return ans;

        }

    }

    unsafe fn nexts(from: i32) -> i32 {

        // 301245

        //  10000

        // a = 3

        let a = from / b6;

        // b = 0

        let b = (from / b5) % 10;

        // c = 1

        let c = (from / b4) % 10;

        // d = 2

        let d = (from / b3) % 10;

        // e = 4

        let e = (from / b2) % 10;

        // f = 5

        let f = from % 10;

        if a == 0 {

            nexts[0] = from + (b - a) * b6 + (a - b) * b5;

            nexts[1] = from + (d - a) * b6 + (a - d) * b3;

            return 2;

        } else if b == 0 {

            nexts[0] = from + (a - b) * b5 + (b - a) * b6;

            nexts[1] = from + (c - b) * b5 + (b - c) * b4;

            nexts[2] = from + (e - b) * b5 + (b - e) * b2;

            return 3;

        } else if c == 0 {

            nexts[0] = from + (b - c) * b4 + (c - b) * b5;

            nexts[1] = from + (f - c) * b4 + (c - f);

            return 2;

        } else if d == 0 {

            nexts[0] = from + (a - d) * b3 + (d - a) * b6;

            nexts[1] = from + (e - d) * b3 + (d - e) * b2;

            return 2;

        } else if e == 0 {

            nexts[0] = from + (b - e) * b2 + (e - b) * b5;

            nexts[1] = from + (d - e) * b2 + (e - d) * b3;

            nexts[2] = from + (f - e) * b2 + (e - f);

            return 3;

        } else {

            nexts[0] = from + (e - f) + (f - e) * b2;

            nexts[1] = from + (c - f) + (f - c) * b4;

            return 2;

        }

    }

    // 当前的数，num

    // 最终要去的数，123450

    // 返回num -> 123450 曼哈顿距离！

    fn distance(num: i32) -> i32 {

        let a = -1;

        let b = i32::abs(a);

        let mut ans = end[(num / b6) as usize][0] + end[(num / b6) as usize][1];

        ans +=

            end[((num / b5) % 10) as usize][0] + i32::abs(end[((num / b5) % 10) as usize][1] - 1);

        ans +=

            end[((num / b4) % 10) as usize][0] + i32::abs(end[((num / b4) % 10) as usize][1] - 2);

        ans +=

            i32::abs(end[((num / b3) % 10) as usize][0] - 1) + end[((num / b3) % 10) as usize][1];

        ans += i32::abs(end[((num / b2) % 10) as usize][0] - 1)

            + i32::abs(end[((num / b2) % 10) as usize][1] - 1);

        ans +=

            i32::abs(end[(num % 10) as usize][0] - 1) + i32::abs(end[(num % 10) as usize][1] - 2);

        return ans;

    }

}

const b6: i32 = 100000;

const b5: i32 = 10000;

const b4: i32 = 1000;

const b3: i32 = 100;

const b2: i32 = 10;

static mut nexts: Vec<i32> = vec![];

const end: [[i32; 2]; 6] = [[1, 2], [0, 0], [0, 1], [0, 2], [1, 0], [1, 1]];

fn main() {

    let nums = vec![vec![1, 2, 3], vec![4, 0, 5]];

    let ans = Solution::sliding_puzzle(nums);

    println!("ans = {:?}", ans);

}

struct Solution {}

执行结果如下：

左神java代码

2022-10-25：在一个 2 * 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次 移动 定义为选择 0 与一个相邻的数字（上下左右）进行交换.的相关教程结束。