这是 LeetCode LCP 13. 寻宝的 Rust 实现。解题思路这道题是BFS 状态压缩动态规划的经典组合题核心思路如下1. 问题分析- 迷宫中有 S起点、T终点、M机关最多16个、O石堆最多40个、#墙壁- 触发机关需要石头必须从 O 搬石头到 M- 一次只能搬一块石头搬石头和放下石头不算步数- 求从 S 出发触发所有 M 后到达 T 的最少步数2. 关键观察- S → M必须经过某个 O取石头即 S → O → M- M → M必须经过某个 O取石头即 Mi → O → Mj- M → T直接走即可不需要石头3. 算法步骤步骤 操作 复杂度① 从 S 和每个 M 分别做 BFS求到全图的最短距离 O((1num_M) × n × m)② 枚举石堆 O计算 S→O→M、Mi→O→Mj、M→T 的最短距离 O(num_M² × num_O)③ 状态压缩 DPdp[mask][i] 表示已触发 mask 状态的机关当前在机关 i 的最小步数 O(2^num_M × num_M²)4. 状态压缩 DP- mask 是一个二进制数第 j 位为 1 表示第 j 个机关已触发- 初始化dp[1i][i] S→Mi 的距离- 转移dp[mask\|(1j)][j] min(dp[mask][i] Mi→Mj)- 答案min(dp[full_mask][i] Mi→T)---Rust 代码rustuse std::collections::VecDeque;impl Solution {pub fn minimal_steps(maze: VecString) - i32 {let n maze.len();let m maze[0].len();let maze: VecVecchar maze.iter().map(|s| s.chars().collect()).collect();// 收集特殊点let mut buttons: Vec(usize, usize) Vec::new(); // 机关点 Mlet mut stones: Vec(usize, usize) Vec::new(); // 石堆点 Olet mut start (0usize, 0usize);let mut end (0usize, 0usize);for i in 0..n {for j in 0..m {match maze[i][j] {M buttons.push((i, j)),O stones.push((i, j)),S start (i, j),T end (i, j),_ {}}}}let num_b buttons.len();let num_s stones.len();// BFS 计算从 (x, y) 到迷宫中所有其他点的最短距离let bfs |x: usize, y: usize| - VecVeci32 {let mut dist vec![vec![-1; m]; n];let mut q VecDeque::new();dist[x][y] 0;q.push_back((x, y));let dirs [(0, 1), (0, -1), (1, 0), (-1, 0)];while let Some((cx, cy)) q.pop_front() {for (dx, dy) in dirs {let nx cx as i32 dx;let ny cy as i32 dy;if nx 0 nx n as i32 ny 0 ny m as i32 {let nx nx as usize;let ny ny as usize;if maze[nx][ny] ! # dist[nx][ny] -1 {dist[nx][ny] dist[cx][cy] 1;q.push_back((nx, ny));}}}}dist};// 计算起点到所有点的距离let start_dist bfs(start.0, start.1);// 如果没有机关直接从 S 走到 Tif num_b 0 {return start_dist[end.0][end.1];}// 计算每个机关到所有点的距离let mut button_dists: VecVecVeci32 Vec::new();for i in 0..num_b {button_dists.push(bfs(buttons[i].0, buttons[i].1));}// dist[i][num_b] S - O - Mi 的最短距离起点到机关i必须经过石堆// dist[i][num_b1] Mi - T 的最短距离机关i到终点// dist[i][j] Mi - O - Mj 的最短距离机关i到机关j必须经过石堆let mut dist vec![vec![-1; num_b 2]; num_b];for i in 0..num_b {// 机关 i 到终点 Tdist[i][num_b 1] button_dists[i][end.0][end.1];// 起点 S 到机关 i必须经过某个石堆let mut min_dist -1;for j in 0..num_s {let (sx, sy) stones[j];if button_dists[i][sx][sy] ! -1 start_dist[sx][sy] ! -1 {let d button_dists[i][sx][sy] start_dist[sx][sy];if min_dist -1 || d min_dist {min_dist d;}}}dist[i][num_b] min_dist;// 机关 i 到机关 j必须经过某个石堆for j in (i 1)..num_b {let mut min_dist -1;for k in 0..num_s {let (sx, sy) stones[k];if button_dists[i][sx][sy] ! -1 button_dists[j][sx][sy] ! -1 {let d button_dists[i][sx][sy] button_dists[j][sx][sy];if min_dist -1 || d min_dist {min_dist d;}}}dist[i][j] min_dist;dist[j][i] min_dist;}}// 如果有机关无法从起点到达或无法到达终点返回 -1for i in 0..num_b {if dist[i][num_b] -1 || dist[i][num_b 1] -1 {return -1;}}// 状态压缩 DP// dp[mask][i] 当前处于第 i 个机关已触发机关状态为 mask 的最短步数// mask 的第 j 位为 1 表示第 j 个机关已触发let mut dp vec![vec![-1; num_b]; 1 num_b];// 初始化从起点 S 到每个机关for i in 0..num_b {dp[1 i][i] dist[i][num_b];}// DP 转移for mask in 1..(1 num_b) {for i in 0..num_b {if mask (1 i) 0 { continue; }if dp[mask][i] -1 { continue; }for j in 0..num_b {if mask (1 j) ! 0 { continue; }if dist[i][j] -1 { continue; }let next_mask mask | (1 j);let new_dist dp[mask][i] dist[i][j];if dp[next_mask][j] -1 || new_dist dp[next_mask][j] {dp[next_mask][j] new_dist;}}}}// 所有机关触发后从最后一个机关走到终点 Tlet final_mask (1 num_b) - 1;let mut ans -1;for i in 0..num_b {if dp[final_mask][i] -1 || dist[i][num_b 1] -1 { continue; }let total dp[final_mask][i] dist[i][num_b 1];if ans -1 || total ans {ans total;}}ans}}下载文件: [LCP 13 寻宝 Rust 实现](sandbox:///mnt/agents/output/lcp13_xun_bao.rs)
