以下是 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 代码
```rust
use std::collections::VecDeque;
struct Solution;
impl Solution {
pub fn escape_maze(maze: Vec<Vec<String>>) -> 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: Vec<Vec<Vec<Vec<StateVal>>>> = 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（只用临时）：可以再用永久消除术 -> 状态 3
if 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（只用永久）：可以再用临时消除术 -> 状态 3
if 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 {
// 使用临时消除术消除当前陷阱，进入状态 3
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: c_opt.px,
py: c_opt.py,
};
q.push_back((next_layer, nx, ny, TEMP_PERM));
}
}
}
// 状态 0（都没用）：可以使用临时或永久消除术
if c_sc == NONE_USED {
// 使用永久消除术 -> 状态 2
if 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));
}
// 使用临时消除术 -> 状态 1
if 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)
