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编写。代码如下：
代码语言：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代码
