以下是 LCP 31. 变换的迷宫 的 Rust 实现采用 BFS 状态压缩 的思路参考了 C 题解的状态设计 。---解题思路状态设计f[time][x][y][scroll_state] 表示在时刻 time 位于 (x, y)、卷轴使用状态为 scroll_state 时的最短步数。状态值 含义0 未使用任何卷轴1 只使用了临时消除术2 只使用了永久消除术3 两个卷轴都使用了关键细节- 每时刻可以上下左右移动一步或停留原地共 5 种选择- 临时消除术仅让下一时刻的指定位置变为空地用一次后消失- 永久消除术将指定位置永久变为空地需要记录该位置坐标 (px, py)后续所有时刻经过该位置都视为空地- 只要在迷宫变化结束前含最后时刻到达终点 (n-1, m-1) 即算成功---Rust 代码rustuse std::collections::VecDeque;struct Solution;impl Solution {pub fn escape_maze(maze: VecVecString) - bool {let layers maze.len();if layers 0 {return false;}let rows maze[0].len();if rows 0 {return false;}let cols maze[0][0].len();// 五个移动方向右、左、下、上、停留const DX: [i32; 5] [0, 0, 1, -1, 0];const DY: [i32; 5] [1, -1, 0, 0, 0];// 卷轴使用状态const NONE_USED: usize 0; // 未使用任何卷轴const ONLY_TEMP: usize 1; // 只使用了临时消除术const ONLY_PERM: usize 2; // 只使用了永久消除术const TEMP_PERM: usize 3; // 两个卷轴都使用了const INF: i32 i32::MAX / 2;/// 状态值记录到达该状态的步数和永久消除的位置#[derive(Clone, Copy)]struct StateVal {d: i32, // 到达该状态的步数px: i32, // 永久消除位置的 x 坐标-1 表示没有使用永久消除术py: i32, // 永久消除位置的 y 坐标-1 表示没有使用永久消除术}// DP 数组f[layer][row][col][scroll_state]let mut f: VecVecVecVecStateVal vec![vec![vec![vec![StateVal { d: INF, px: -1, py: -1 }; 4];cols];rows];layers];// BFS 队列存储 (时刻, 行, 列, 卷轴状态)let mut q: VecDeque(usize, usize, usize, usize) VecDeque::new();// 初始状态时刻 0 在起点 (0, 0)未使用任何卷轴f[0][0][0][NONE_USED] StateVal { d: 0, px: -1, py: -1 };q.push_back((0, 0, 0, NONE_USED));while let Some((c_layer, c_x, c_y, c_sc)) q.pop_front() {let c_opt f[c_layer][c_x][c_y][c_sc];let next_layer c_layer 1;// 下一时刻超出迷宫变化范围无法继续移动if next_layer layers {continue;}for dir in 0..5 {let nx c_x as i32 DX[dir];let ny c_y as i32 DY[dir];// 边界检查if nx 0 || nx rows as i32 || ny 0 || ny cols as i32 {continue;}let nx nx as usize;let ny ny as usize;// 检查下一时刻该位置是否是空地let next_is_empty maze[next_layer][nx].as_bytes()[ny] b.;// 检查是否是永久消除的位置永久消除后该位置始终可通行let is_perm_pos (c_sc ONLY_PERM || c_sc TEMP_PERM) c_opt.px nx as i32 c_opt.py ny as i32;if next_is_empty || is_perm_pos {// 该位置可通行卷轴状态保持不变if c_opt.d 1 f[next_layer][nx][ny][c_sc].d {f[next_layer][nx][ny][c_sc] StateVal {d: c_opt.d 1,px: c_opt.px,py: c_opt.py,};q.push_back((next_layer, nx, ny, c_sc));}continue;}// 下一时刻该位置是陷阱考虑使用卷轴// 状态 1只用临时可以再用永久消除术 - 状态 3if c_sc ONLY_TEMP {if c_opt.d 1 f[next_layer][nx][ny][TEMP_PERM].d {f[next_layer][nx][ny][TEMP_PERM] StateVal {d: c_opt.d 1,px: nx as i32, // 永久消除当前陷阱位置py: ny as i32,};q.push_back((next_layer, nx, ny, TEMP_PERM));}}// 状态 2只用永久可以再用临时消除术 - 状态 3if c_sc ONLY_PERM {if c_opt.px nx as i32 c_opt.py ny as i32 {// 当前位置已被永久消除直接通行前面已处理此处为保险if c_opt.d 1 f[next_layer][nx][ny][c_sc].d {f[next_layer][nx][ny][c_sc] StateVal {d: c_opt.d 1,px: c_opt.px,py: c_opt.py,};q.push_back((next_layer, nx, ny, c_sc));}} else {// 使用临时消除术消除当前陷阱进入状态 3if c_opt.d 1 f[next_layer][nx][ny][TEMP_PERM].d {f[next_layer][nx][ny][TEMP_PERM] StateVal {d: c_opt.d 1,px: c_opt.px,py: c_opt.py,};q.push_back((next_layer, nx, ny, TEMP_PERM));}}}// 状态 0都没用可以使用临时或永久消除术if c_sc NONE_USED {// 使用永久消除术 - 状态 2if c_opt.d 1 f[next_layer][nx][ny][ONLY_PERM].d {f[next_layer][nx][ny][ONLY_PERM] StateVal {d: c_opt.d 1,px: nx as i32,py: ny as i32,};q.push_back((next_layer, nx, ny, ONLY_PERM));}// 使用临时消除术 - 状态 1if c_opt.d 1 f[next_layer][nx][ny][ONLY_TEMP].d {f[next_layer][nx][ny][ONLY_TEMP] StateVal {d: c_opt.d 1,px: c_opt.px,py: c_opt.py,};q.push_back((next_layer, nx, ny, ONLY_TEMP));}}}}// 检查在任意时刻、任意卷轴状态下是否到达终点for layer in 0..layers {for sc in 0..4 {if f[layer][rows - 1][cols - 1][sc].d ! INF {return true;}}}false}}---复杂度分析- 时间复杂度O(T \times N \times M \times 4 \times 5)其中 T 为时刻数N \times M 为迷宫大小4 为卷轴状态数5 为移动方向数- 空间复杂度O(T \times N \times M \times 4)用于存储 DP 状态数组和 BFS 队列---下载文件[lcp31_escape_maze.rs](sandbox:///mnt/agents/output/lcp31_escape_maze.rs)
以下是 LCP 31. 变换的迷宫 的 Rust 实现采用 BFS 状态压缩 的思路参考了 C 题解的状态设计 。---解题思路状态设计f[time][x][y][scroll_state] 表示在时刻 time 位于 (x, y)、卷轴使用状态为 scroll_state 时的最短步数。状态值 含义0 未使用任何卷轴1 只使用了临时消除术2 只使用了永久消除术3 两个卷轴都使用了关键细节- 每时刻可以上下左右移动一步或停留原地共 5 种选择- 临时消除术仅让下一时刻的指定位置变为空地用一次后消失- 永久消除术将指定位置永久变为空地需要记录该位置坐标 (px, py)后续所有时刻经过该位置都视为空地- 只要在迷宫变化结束前含最后时刻到达终点 (n-1, m-1) 即算成功---Rust 代码rustuse std::collections::VecDeque;struct Solution;impl Solution {pub fn escape_maze(maze: VecVecString) - bool {let layers maze.len();if layers 0 {return false;}let rows maze[0].len();if rows 0 {return false;}let cols maze[0][0].len();// 五个移动方向右、左、下、上、停留const DX: [i32; 5] [0, 0, 1, -1, 0];const DY: [i32; 5] [1, -1, 0, 0, 0];// 卷轴使用状态const NONE_USED: usize 0; // 未使用任何卷轴const ONLY_TEMP: usize 1; // 只使用了临时消除术const ONLY_PERM: usize 2; // 只使用了永久消除术const TEMP_PERM: usize 3; // 两个卷轴都使用了const INF: i32 i32::MAX / 2;/// 状态值记录到达该状态的步数和永久消除的位置#[derive(Clone, Copy)]struct StateVal {d: i32, // 到达该状态的步数px: i32, // 永久消除位置的 x 坐标-1 表示没有使用永久消除术py: i32, // 永久消除位置的 y 坐标-1 表示没有使用永久消除术}// DP 数组f[layer][row][col][scroll_state]let mut f: VecVecVecVecStateVal vec![vec![vec![vec![StateVal { d: INF, px: -1, py: -1 }; 4];cols];rows];layers];// BFS 队列存储 (时刻, 行, 列, 卷轴状态)let mut q: VecDeque(usize, usize, usize, usize) VecDeque::new();// 初始状态时刻 0 在起点 (0, 0)未使用任何卷轴f[0][0][0][NONE_USED] StateVal { d: 0, px: -1, py: -1 };q.push_back((0, 0, 0, NONE_USED));while let Some((c_layer, c_x, c_y, c_sc)) q.pop_front() {let c_opt f[c_layer][c_x][c_y][c_sc];let next_layer c_layer 1;// 下一时刻超出迷宫变化范围无法继续移动if next_layer layers {continue;}for dir in 0..5 {let nx c_x as i32 DX[dir];let ny c_y as i32 DY[dir];// 边界检查if nx 0 || nx rows as i32 || ny 0 || ny cols as i32 {continue;}let nx nx as usize;let ny ny as usize;// 检查下一时刻该位置是否是空地let next_is_empty maze[next_layer][nx].as_bytes()[ny] b.;// 检查是否是永久消除的位置永久消除后该位置始终可通行let is_perm_pos (c_sc ONLY_PERM || c_sc TEMP_PERM) c_opt.px nx as i32 c_opt.py ny as i32;if next_is_empty || is_perm_pos {// 该位置可通行卷轴状态保持不变if c_opt.d 1 f[next_layer][nx][ny][c_sc].d {f[next_layer][nx][ny][c_sc] StateVal {d: c_opt.d 1,px: c_opt.px,py: c_opt.py,};q.push_back((next_layer, nx, ny, c_sc));}continue;}// 下一时刻该位置是陷阱考虑使用卷轴// 状态 1只用临时可以再用永久消除术 - 状态 3if c_sc ONLY_TEMP {if c_opt.d 1 f[next_layer][nx][ny][TEMP_PERM].d {f[next_layer][nx][ny][TEMP_PERM] StateVal {d: c_opt.d 1,px: nx as i32, // 永久消除当前陷阱位置py: ny as i32,};q.push_back((next_layer, nx, ny, TEMP_PERM));}}// 状态 2只用永久可以再用临时消除术 - 状态 3if c_sc ONLY_PERM {if c_opt.px nx as i32 c_opt.py ny as i32 {// 当前位置已被永久消除直接通行前面已处理此处为保险if c_opt.d 1 f[next_layer][nx][ny][c_sc].d {f[next_layer][nx][ny][c_sc] StateVal {d: c_opt.d 1,px: c_opt.px,py: c_opt.py,};q.push_back((next_layer, nx, ny, c_sc));}} else {// 使用临时消除术消除当前陷阱进入状态 3if c_opt.d 1 f[next_layer][nx][ny][TEMP_PERM].d {f[next_layer][nx][ny][TEMP_PERM] StateVal {d: c_opt.d 1,px: c_opt.px,py: c_opt.py,};q.push_back((next_layer, nx, ny, TEMP_PERM));}}}// 状态 0都没用可以使用临时或永久消除术if c_sc NONE_USED {// 使用永久消除术 - 状态 2if c_opt.d 1 f[next_layer][nx][ny][ONLY_PERM].d {f[next_layer][nx][ny][ONLY_PERM] StateVal {d: c_opt.d 1,px: nx as i32,py: ny as i32,};q.push_back((next_layer, nx, ny, ONLY_PERM));}// 使用临时消除术 - 状态 1if c_opt.d 1 f[next_layer][nx][ny][ONLY_TEMP].d {f[next_layer][nx][ny][ONLY_TEMP] StateVal {d: c_opt.d 1,px: c_opt.px,py: c_opt.py,};q.push_back((next_layer, nx, ny, ONLY_TEMP));}}}}// 检查在任意时刻、任意卷轴状态下是否到达终点for layer in 0..layers {for sc in 0..4 {if f[layer][rows - 1][cols - 1][sc].d ! INF {return true;}}}false}}---复杂度分析- 时间复杂度O(T \times N \times M \times 4 \times 5)其中 T 为时刻数N \times M 为迷宫大小4 为卷轴状态数5 为移动方向数- 空间复杂度O(T \times N \times M \times 4)用于存储 DP 状态数组和 BFS 队列---下载文件[lcp31_escape_maze.rs](sandbox:///mnt/agents/output/lcp31_escape_maze.rs)
