以下是 LCP 31. 变换的迷宫 的 C 实现基于 BFS 状态压缩参考了 glucoco.com 的题解思路。---解题思路状态设计f[time][x][y][scroll_state] 表示在时刻 time 位于 (x, y)、卷轴使用状态为 scroll_state 时的最短步数。状态值 含义0 未使用任何卷轴1 只使用了临时消除术2 只使用了永久消除术3 两个卷轴都使用了关键细节- 每时刻可以上下左右移动一步或停留原地共 5 种选择- 临时消除术仅让下一时刻的指定位置变为空地用一次后消失- 永久消除术将指定位置永久变为空地需要记录该位置坐标 (px, py)后续所有时刻经过该位置都视为空地- 只要在迷宫变化结束前含最后时刻到达终点 (n-1, m-1) 即算成功---C 代码cpp#include bits/stdc.husing namespace std;class Solution {public:// 五个方向右、左、下、上、停留const int dx[5] {0, 0, 1, -1, 0};const int dy[5] {1, -1, 0, 0, 0};// 卷轴使用状态const int NONE_USED 0; // 未使用任何卷轴const int ONLY_TEMP 1; // 只使用了临时消除术const int ONLY_PERM 2; // 只使用了永久消除术const int TEMP_PERM 3; // 两个卷轴都使用了// 状态值结构记录到达该状态的步数和永久消除的位置struct StatusValue {int d; // 到达该状态的步数int px; // 永久消除位置的x坐标-1表示没有int py; // 永久消除位置的y坐标-1表示没有StatusValue(int d_, int px_, int py_) : d(d_), px(px_), py(py_) {}StatusValue() : d(INT_MAX), px(-1), py(-1) {}};// BFS状态struct Status {int i, x, y, sc; // 时刻、行、列、卷轴状态StatusValue v; // 状态值Status(int i_, int x_, int y_, int sc_, StatusValue v_): i(i_), x(x_), y(y_), sc(sc_), v(v_) {}};bool escapeMaze(vectorvectorstring mazes) {int layers mazes.size();if (layers 0) return false;int rows mazes[0].size();if (rows 0) return false;int cols mazes[0][0].size();// f[time][x][y][scroll_state]// 使用vector动态分配避免栈溢出vectorvectorvectorvectorStatusValue f(layers,vectorvectorvectorStatusValue(rows,vectorvectorStatusValue(cols,vectorStatusValue(4, StatusValue()))));queueStatus q;// 初始状态时刻0在(0,0)未使用卷轴f[0][0][0][NONE_USED] StatusValue(0, -1, -1);q.push(Status(0, 0, 0, NONE_USED, f[0][0][0][NONE_USED]));while (!q.empty()) {auto frt q.front();q.pop();int c_layer frt.i;int c_x frt.x;int c_y frt.y;int c_sc frt.sc;auto c_opt frt.v;int next_layer c_layer 1;// 下一时刻超出范围if (next_layer layers) {continue;}for (int dir 0; dir 5; dir) {int nx c_x dx[dir];int ny c_y dy[dir];// 边界检查if (!(nx 0 nx rows ny 0 ny cols)) {continue;}// 检查下一时刻该位置是否是空地if (mazes[next_layer][nx][ny] .) {if (c_opt.d 1 f[next_layer][nx][ny][c_sc].d) {f[next_layer][nx][ny][c_sc] c_opt;f[next_layer][nx][ny][c_sc].d c_opt.d 1;q.push(Status(next_layer, nx, ny, c_sc, f[next_layer][nx][ny][c_sc]));}continue;}// 检查是否是永久消除的位置bool is_perm_pos (c_sc ONLY_PERM || c_sc TEMP_PERM) c_opt.px nx c_opt.py ny;if (is_perm_pos) {if (c_opt.d 1 f[next_layer][nx][ny][c_sc].d) {f[next_layer][nx][ny][c_sc] c_opt;f[next_layer][nx][ny][c_sc].d c_opt.d 1;q.push(Status(next_layer, nx, ny, c_sc, f[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].d c_opt.d 1;f[next_layer][nx][ny][TEMP_PERM].px nx;f[next_layer][nx][ny][TEMP_PERM].py ny;q.push(Status(next_layer, nx, ny, TEMP_PERM, f[next_layer][nx][ny][TEMP_PERM]));}}// 状态2只用永久可以再用临时消除术 - 状态3if (c_sc ONLY_PERM) {if (c_opt.px nx c_opt.py ny) {// 永久消除的位置直接通行前面已处理此处为保险if (c_opt.d 1 f[next_layer][nx][ny][c_sc].d) {f[next_layer][nx][ny][c_sc] c_opt;f[next_layer][nx][ny][c_sc].d c_opt.d 1;q.push(Status(next_layer, nx, ny, c_sc, f[next_layer][nx][ny][c_sc]));}} else {// 使用临时消除术if (c_opt.d 1 f[next_layer][nx][ny][TEMP_PERM].d) {f[next_layer][nx][ny][TEMP_PERM] c_opt;f[next_layer][nx][ny][TEMP_PERM].d c_opt.d 1;q.push(Status(next_layer, nx, ny, TEMP_PERM, f[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].d c_opt.d 1;f[next_layer][nx][ny][ONLY_PERM].px nx;f[next_layer][nx][ny][ONLY_PERM].py ny;q.push(Status(next_layer, nx, ny, ONLY_PERM, f[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] c_opt;f[next_layer][nx][ny][ONLY_TEMP].d c_opt.d 1;q.push(Status(next_layer, nx, ny, ONLY_TEMP, f[next_layer][nx][ny][ONLY_TEMP]));}}}}// 检查在任意时刻、任意卷轴状态下是否到达终点for (int i 0; i layers; i) {for (int sc 0; sc 4; sc) {if (f[i][rows - 1][cols - 1][sc].d ! INT_MAX) {return true;}}}return 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.cpp](sandbox:///mnt/agents/output/lcp31_escape_maze.cpp)