介绍
为 C++ 推箱子游戏加入完整值快照和安全的多步撤销。
你将制作一个固定地形与移动对象分离的小型终端游戏。你会实现核心 C++ 函数，然后实际游玩并检查行为。
在合法移动前保存状态
本步骤记录完整的先前状态，使稍后的撤销能够同时逆转行走与推箱。本实验独立初始化文件，不需要前一个实验的文件。从 Terminal 标签页开始，或使用 WebIDE 中的 Terminal > New Terminal。
cd /home/labex/project/sokoban
完整的 sample 与学员引擎分开。运行它，依次输入 d、d、u，每次按 Enter，观察完成状态、玩家和箱子恢复到获胜推动之前的值。输入 q 退出。
./sample
你自己的 engine.cpp 已有正确的移动和完成判断，但不会记录历史，其 undo() 总是拒绝。查看它：
cat engine.cpp
准备好的 Game 类在 engine.hpp 中声明。Point 保存整数坐标 x 和 y：x 向右增大，y 向下增大。State 保存玩家和一个包含所有箱子的 std::vector<Point>。terrain[y][x] 只包含 # 墙壁、空格和 . 目标。const 使地形在构造后只读，因此移动的箱子不会抹掉目标。渲染时合并这两层：* 表示目标上的箱子，+ 表示目标上的玩家。
floor(point) 判断坐标是否位于棋盘内且不是墙壁。boxAt(point) 返回该处箱子的 vector 索引；没有箱子时返回 -1。这些辅助函数、加载、渲染和命令读取均已准备好。你在 engine.cpp 中实现 move、won，稍后再实现 undo；保留 engine.hpp、support.cpp、main.cpp、levels/ 和 sample。你可以添加辅助函数并使用等价算法。检查关注实际行为，不要求特定写法或路线。
支持的地图是由墙封闭的矩形 ASCII 网格，至少三行、三列。地图恰有一个玩家、至少一个箱子，目标数量与箱子数量相同，且对象不重叠。符号为：# 墙壁、空格地面、. 目标、@ 玩家、$ 箱子、+ 目标上的玩家，以及 * 目标上的箱子。地图可以无解，也可以初始时已经完成。准备好的加载器会拒绝其他输入；你不需要编写解析器。
move(dx, dy) 只接受 (1,0)、(-1,0)、(0,1) 或 (0,-1)。其他任何整数对都必须返回 false，且不改变状态或历史。合法动作返回 true；非法动作返回 false，不改变任何内容。箱子 vector 中的顺序不影响占位含义。稍后的撤销会恢复该动作之前实际保存的完整状态，包括当时的箱子顺序。
std::vector<State> history 是完整状态的有序集合。history.push_back(state) 保存一份值拷贝：之后修改 state.player 或 state.boxes 的任一元素，都不会改变先前的副本。只保存玩家会丢失被推动箱子的位置。固定地形不需要复制，因为合法游戏不会改变它；完成状态根据地形和箱子推导，不单独保存为一个标志。
被拒绝的动作不能占用撤销位置。将快照操作放在所有拒绝分支之后、第一次修改之前。方向、墙壁、第二个箱子或阻塞的目的格拒绝移动时，都不需要快照。初始历史为空。
下面的检查在初始代码上会有意失败，提示 walk records its entire before state：
bash /opt/labex-sokoban/check.sh history
下面的完整文件为每个合法动作添加一份快照；撤销仍未完成。cat > 替换文件；带引号的 here-document 按原样写入 C++，直到结尾的 CPP 行。
cat > engine.cpp <<'CPP'
#include "engine.hpp"
bool Game::move(int dx, int dy) {
if (!((dx == -1 && dy == 0) || (dx == 1 && dy == 0) ||
(dx == 0 && dy == -1) || (dx == 0 && dy == 1))) return false;
Point next{state.player.x + dx, state.player.y + dy};
if (!floor(next)) return false;
int box = boxAt(next);
Point beyond{next.x + dx, next.y + dy};
if (box >= 0 && (!floor(beyond) || boxAt(beyond) >= 0)) return false;
history.push_back(state);
if (box >= 0) state.boxes[box] = beyond;
state.player = next;
return true;
}
bool Game::undo() {
return false;
}
bool Game::won() const {
if (state.boxes.empty()) return false;
for (Point box : state.boxes) {
if (terrain[box.y][box.x] != '.') return false;
}
return true;
}
CPP
使用 C++17 和编译器警告进行构建。若有某行输入错误，请修正该行或重新完整替换文件，然后重新构建。
g++ -std=c++17 -Wall -Wextra engine.cpp support.cpp main.cpp -o sokoban
./sokoban
依次输入 d、d、d，每次按 Enter。历史依次变为 1、2、3：行走、推上目标、推离目标。再输入一个 d 会显示 Blocked，并保持 History: 3。输入 u：下一步实现撤销之前，预期仍显示 No earlier move，棋盘不变。输入 q。
bash /opt/labex-sokoban/check.sh history
All history checks passed 表示合法动作保存了真实、完整的先前值，而拒绝动作没有新增记录。这还不代表撤销已经可用。
恢复并移除最新快照
本步骤实现撤销，并实际游玩多次回退。继续使用 Terminal，工作目录为 /home/labex/project/sokoban。
history.empty() 判断是否没有更早的合法动作。若为空，返回 false，不作任何修改。否则，history.back() 引用最新快照。将它赋给 state，会通过值拷贝恢复玩家和所有箱子。复制完成后，pop_back() 才移除已经使用的快照。在空 vector 上访问 back() 是无效的，因此必须先检查。撤销不会再添加一条历史记录。
其余移动逻辑保持不变。替换完整文件：
cat > engine.cpp <<'CPP'
#include "engine.hpp"
bool Game::move(int dx, int dy) {
if (!((dx == -1 && dy == 0) || (dx == 1 && dy == 0) ||
(dx == 0 && dy == -1) || (dx == 0 && dy == 1))) return false;
Point next{state.player.x + dx, state.player.y + dy};
if (!floor(next)) return false;
int box = boxAt(next);
Point beyond{next.x + dx, next.y + dy};
if (box >= 0 && (!floor(beyond) || boxAt(beyond) >= 0)) return false;
history.push_back(state);
if (box >= 0) state.boxes[box] = beyond;
state.player = next;
return true;
}
bool Game::undo() {
if (history.empty()) return false;
state = history.back();
history.pop_back();
return true;
}
bool Game::won() const {
if (state.boxes.empty()) return false;
for (Point box : state.boxes) {
if (terrain[box.y][box.x] != '.') return false;
}
return true;
}
CPP
g++ -std=c++17 -Wall -Wextra engine.cpp support.cpp main.cpp -o sokoban
./sokoban
输入 u：No earlier move 表示初始棋盘未改变。输入 d、d：游戏完成。再输入 d：箱子离开目标，玩家脚下的目标显示为 +，胜利状态消失。再试一个 d：它会被拒绝，历史保持为 3。
现在输入 u：游戏恢复到获胜棋盘，包括箱子的位置。第二个 u 恢复到获胜推箱之前的位置，显示 Not solved。第三个 u 恢复玩家的初始位置，显示 History: 0；再输入一个 u 会安全显示 No earlier move。输入 q。
./sokoban levels/warehouse.txt
依次尝试 w、s、d、d、w，每次按 Enter。两个箱子都到达目标。输入五次 u：每一步都恢复先前的完整状态，最终将两个箱子和玩家都恢复到初始位置。额外撤销会安全拒绝。另一条合法路线是 d、d、w、s、a、a、w；引擎必须支持两条路线，而不是只支持固定序列。输入 q。
bash /opt/labex-sokoban/check.sh undo
All undo checks passed 包括不同路线后的真实先前状态恢复、空历史、非法动作不污染历史、离开目标，以及逆转胜利状态。检查器在隔离游戏实例中测试原样函数和已经构建的 sokoban 可执行文件；编辑后请重新构建，让可玩程序与源码一致。它不会向正在游玩的会话发送动作，也不会改写进度。
遇到普通错误时，例如 ./sokoban levels/missing.txt 这样的拼写错误，会打印 Cannot open level: ... 并退出。改用 levels/warehouse.txt 重复命令即可。在运行中的游戏内部输入错误命令，会打印 Use one command per line...，而不改变状态；改输合法的单字母命令即可。你始终可以输入 q，必要时修正源码并重新构建，再开始新的内存游戏，不会改变原始关卡文件。
总结
你在合法修改前保存值快照，恢复了每个移动对象，并在撤销后重新判断胜利。非法动作不会改变游戏状态或历史。
