如果刷 UVa 的入门题118 这道题几乎绕不开。它看起来不过是一道“照着指令走路”的模拟题地图最大才 50×50指令也只有 L、R、F 三种读题五分钟就能开写但真正提交的时候很多人反而会在一个非常隐蔽的规则上翻车某个位置一旦有机器人掉出去后续机器人再走到这个位置就不会掉第二次那条试图走出去的指令会被直接忽略。我第一次写这道题就吃了一个 WA问题正出在这里。这次就把 UVa 118 从读题、建模、编码到调试的完整过程拆开讲透适合刚开始练模拟题、或者经常在边界状态处理上栽跟头的同学参考。1. 题目到底在说什么三条规则与一个隐藏机制1.1 先看清楚输入输出长什么样题目背景翻译过来大概是Flatworld 是一张二维平面世界左下角是(0, 0)右上角坐标由输入第一行给出比如5 3那这个世界的 x 范围就是0..5y 范围就是0..3。一批机器人依次被投放到这个世界的某个坐标点上每个机器人会收到一串由L、R、F组成的指令你要模拟它执行完所有指令后的最终位置和朝向。输入格式很容易被一眼带过我一开始也差点看漏第一行只有两个整数也就是地图右上角的坐标接下来是若干组机器人数据每组数据占两行第一行是机器人的初始x y坐标和朝向字符N/E/S/W第二行是一串指令。机器人有多少个题目没给输入会一直持续到文件结束也就是要用while (cin ...)这种“读到 EOF”的方式处理。很多人在输入上踩的第一个坑就是以为机器人数量是固定给出的于是写了for (int i 0; i n; i)结果运行起来读入奇奇怪怪或者只处理了第一组数据。UVa 老题的输入往往不给你数量文件结束就是结束这是做这类模拟题的基本素养。1.2 三条规则转向、前进、掉出机器人的行为规则其实只有三条L原地左转 90 度坐标不变。R原地右转 90 度坐标不变。F沿着当前朝向走一格坐标发生变化。只要移动后的新坐标仍然满足0 x maxX并且0 y maxY机器人就正常走过去。如果移动后的坐标超出地图边界机器人就从世界边缘掉下去了输出时要在朝向后面加上LOST。这个规则本身不复杂但它有一个非常容易忽略的附加条件如果机器人当前所在的位置之前已经有别的机器人从这里掉出去过那么这次“掉出去”不会发生这条F指令被直接忽略机器人留在原地朝向也不变继续执行后面的指令。换句话说世界有一个“记忆”某个边缘格子一旦掉过机器人就相当于被打了一个标记之后再来的机器人站到这个格子上想往外走会被一种神秘力量拦住。这个设定我第一遍读题时根本没当回事写代码时完全没处理结果样例只能过一半第二个样例输出跟答案对不上。1.3 被一句话带过的“掉出记忆”为什么是关键这个“掉出记忆”机制本质上把题目从“单机器人模拟”升级成了“带全局状态的模拟”。每个掉出去的机器人都会在世界地图上留下一个永久标记这个标记会影响后面所有机器人的行为。如果不理解这一点很容易写出下面这种逻辑机器人走到边界下一步F会越界直接判掉出输出LOST结束。但正确逻辑是当机器人站在一个“已经掉出过的位置”时它想往外走是走不出去的这条F会被跳过接下来它可能转向、可能沿着边界走别的方向最终甚至可能活得好好的。官方样例里的第三个机器人就是这种情况它站在(3, 3)想往北走但第二个机器人恰恰是从(3, 3)这个位置掉出去的所以它的北移指令被忽略之后它左转、前进最后活着停在(2, 3)输出里没有LOST。这个“掉出点标记表”必须全程保留不能每个机器人开始时清空。我第一次就是在一组机器人处理完后把标记数组重置了导致第三个机器人也掉出去样例输出直接错掉。2. 方向环与状态机动手前先把模型定下来2.1 用数字表示方向N/E/S/W 的索引化模拟题最忌讳的就是在代码里到处写if (dir N) ... else if (dir E) ...不仅代码冗长还特别容易在转向时漏掉某一种情况。正确做法是先把方向抽象成数字。我的习惯是把N、E、S、W分别映射成0、1、2、3。为什么用这个顺序因为从北到东、从南到西正好是顺时针方向。这样设计后向右转就是数字加一向左转就是数字减一整条方向链可以用一个很小很规整的循环来表达。用一个表来看更直观朝向索引 dir左转 L 后右转 R 后N0W(3)E(1)E1N(0)S(2)S2E(1)W(3)W3S(2)N(0)观察这张表可以发现方向索引是“顺时针”排列的所以右转Rdir (dir 1) % 4左转Ldir (dir 3) % 4等价于(dir - 1 4) % 4模运算处理方向环是这个题目最经典的建模技巧。后面做 BFS、DFS 里的方向遍历时这种写法也一脉相承。2.2 移动向量与越界判断怎么约定方向和坐标轴的对应关系也要提前定好。既然N是 y 轴正方向E是 x 轴正方向那么可以定义两组常量数组dir朝向dxdy0N011E102S0-13W-10执行F时先算nx x dx[dir]、ny y dy[dir]然后判断nx、ny是否越界。如果没越界就更新坐标如果越界就要根据当前位置是否已经标记为“禁区”来决定到底是掉出去还是忽略指令。这里有个细节值得提前说明越界前的那个位置一定在地图内也就是x、y本身一定是合法的所以我们完全可以用lost[x][y]这个二维标记来表示“从这个位置往外走会掉出去”。很多新手试图用lost[nx][ny]来标记掉出点但nx、ny可能已经是-1或51这种非法下标直接越界而且语义上也说不通——因为后来者能站到的位置是(x, y)不是地图外的(nx, ny)。2.3 全局状态一个二维布尔数组如何承担“世界记忆”“掉出记忆”用bool lost[55][55]这样一个二维布尔数组实现就足够了。坐标范围最大是 50所以开到 55 完全够用。这个数组的语义是lost[a][b] true表示“曾经有机器人在(a, b)这个位置执行F时掉出了世界”。后续机器人来到(a, b)如果再想往外走就不会再掉出去了。实现时要注意掉出时标记的是掉出前的位置(x, y)不是越界后的位置。一个位置只要掉出过一次标记就永久为true不需要也不可能被重置。lost数组要在所有机器人之间共享也就是放在读入机器人数据之前初始化全程保留。用一个二维数组记录全局状态是这道题的核心。想清楚“记录是谁、在哪里、作用于谁”这三点后代码写起来其实非常快。3. 完整 C 实现从读入到输出的逐段拆解3.1 处理输入while(cin ...) 读完整组机器人UVa 老题最稳妥的输入处理方式就是利用cin 会自动跳过空白字符包括换行的特性直接连读int maxX, maxY; cin maxX maxY; int x, y; char heading; string inst; while (cin x y heading) { cin inst; // 处理一个机器人的逻辑 }第一行读完地图边界后循环里每次先读三个值横坐标、纵坐标、朝向字符。虽然输入里每个机器人分两行但cin 不关心换行它只按空格或换行分隔所以cin x y heading能干净地跨行读取。inst是第二行整串指令用string存最方便。这里不建议用scanf 手动处理残留换行容易踩到缓冲区问题也不建议用getline因为要额外处理换行符麻烦还容易出错。while (cin x y heading)是最省心的方案。3.2 主循环指令执行、越界判断、掉出中断处理单个机器人时先把朝向字符转成方向索引然后遍历指令串中的每一个字符。核心逻辑分三层L/R只修改方向索引不修改坐标。F计算目标位置(nx, ny)。判断目标位置是否越界没越界更新坐标到(nx, ny)。越界检查lost[x][y]为false标记lost[x][y] true机器人掉出isLost true立即跳出指令循环。为true说明这个位置已经掉出过机器人忽略这条F不更新坐标不改变方向继续处理下一条指令。这里最容易搞错的是“掉出后要 break”和“忽略 F 时不能 break”的区别。掉出后机器人已经不在世界上了后面指令没有意义必须 break而因为记忆标记被忽略的F机器人还好端端站在当前位置只是这一步没走出去后续指令还要继续执行。3.3 可 AC 的完整代码下面这份代码是我整理后可以稳定通过 UVa 118 的版本关键位置都加了注释#include iostream #include string using namespace std; int main() { int maxX, maxY; cin maxX maxY; // lost[a][b] 表示曾经有机器人在 (a, b) 位置掉出过世界 bool lost[55][55] {false}; // 方向索引0N, 1E, 2S, 3W顺时针 int dx[4] {0, 1, 0, -1}; int dy[4] {1, 0, -1, 0}; char dirChar[4] {N, E, S, W}; int x, y; char heading; string inst; while (cin x y heading) { cin inst; int dir; switch (heading) { case N: dir 0; break; case E: dir 1; break; case S: dir 2; break; default: dir 3; break; // W } bool isLost false; for (char c : inst) { if (c L) { dir (dir 3) % 4; // 左转逆时针 } else if (c R) { dir (dir 1) % 4; // 右转顺时针 } else { // c F int nx x dx[dir]; int ny y dy[dir]; // 越界判断 if (nx 0 || nx maxX || ny 0 || ny maxY) { if (!lost[x][y]) { lost[x][y] true; // 记录掉出位置 isLost true; break; // 机器人已经不在了 } // 该位置已经掉出过机器人忽略这条 F继续执行后续指令 } else { x nx; y ny; } } } cout x y dirChar[dir]; if (isLost) cout LOST; cout \n; } return 0; }这段代码的骨架非常简单但它把方向环、越界判断、全局记忆三个核心点都覆盖到了。记住lost数组只负责记录掉出位置它不负责拦截“机器人站上去”这个行为只负责拦截从该位置“再往外走”的动作。4. 样例推演与三个高频踩坑点4.1 手动过一遍官方样例官方样例输入是5 3 1 1 E RFRFRFRF 3 2 N FRRFLLFFRRFLL 0 3 W LLFFFLFLFL第一个机器人从(1, 1)出发朝向E指令是RFRFRFRF。一步一步拆R方向从 E 变 SF从(1,1)走到(1,0)R方向从 S 变 WF从(1,0)走到(0,0)R方向从 W 变 NF从(0,0)走到(0,1)R方向从 N 变 EF从(0,1)走回(1,1)它走了一个边长 1 的矩形最后回到原地朝向也是原来的E输出1 1 E。第二个机器人从(3, 2)出发朝向N指令是FRRFLLFFRRFLL。关键在最后几步F从(3,2)到(3,3)R、R方向从 N 变 E 再变 SF从(3,3)回到(3,2)L、L方向从 S 变 E 再变 NF从(3,2)到(3,3)F再往北就会到(3,4)越界且lost[3][3]为false所以标记lost[3][3] true掉出。输出是3 3 N LOST注意位置是掉出前的(3, 3)不是越界后的(3, 4)。第三个机器人从(0, 3)出发朝向W指令是LLFFFLFLFL。走到后面它会到达(3, 3)并尝试往北走此时lost[3][3]已经是true所以这条F被忽略机器人没有掉出去。随后它左转、前进、再左转最后停在(2, 3)朝向S输出2 3 S。把这个样例完整推一遍比看十遍题面都有用。第三个机器人就是专门用来验证“掉出记忆”是否实现的能推对基本就成功了一大半。4.2 坑一掉出后没有 break或者用越界后的位置做标记一个非常经典的错误代码片段if (nx 0 || nx maxX || ny 0 || ny maxY) { lost[nx][ny] true; // 错误nx, ny 可能越界 isLost true; // 忘记 break继续跑后面的指令 }这样做有两个问题一是nx、ny可能变成-1或51这种非法下标导致数组越界访问轻则逻辑错误重则 RE二是掉出后不 break机器人会继续执行后面指令坐标被改到奇怪的地方最终输出完全错误。正确的做法之前已经说过标记lost[x][y]也就是掉出前的位置一旦isLost true立刻break掉 for 循环。4.3 坑二把“忽略单条 F”写成“忽略整条指令串”这个坑特别隐蔽。很多人知道lost[x][y] true时机器人不会掉于是直接在代码里写成if (lost[x][y]) { // 当作无事发生直接跳过当前指令 continue; }这个写法单独看不算错能继续处理下一条指令。但如果你在实现时图省事把if (lost[x][y])放在了整个指令串的循环条件里比如只要预判后面某个位置会掉就把整条指令串都扔掉那就会出错。记住被忽略的只有“当前这条试图越界的F”。机器人后续的L、R、F指令都要照常执行。官方样例第三个机器人就是活生生的例子它先前在北移时被拦下后面又左转前进最终走到了别的位置。4.4 坑三L 和 R 的转向方向搞反方向环建模里L是逆时针R是顺时针这是常识但代码里很容易在dir (dir 3) % 4和dir (dir 1) % 4之间搞混。如果你用的是0N, 1E, 2S, 3W这个顺时针索引那么R是(dir 1) % 4L是(dir 3) % 4。反过来如果你把方向定义成逆时针排列那L和R的加减关系也要跟着反过来。一个验证方法是拿样例第一个机器人手推(1,1) E执行R后应该朝向S。如果E的索引是1(11)%42正好是S说明你的顺序对。要是推出来朝向朝北说明方向环排反了。5. 模拟题的进阶心法状态记忆与边界测试5.1 从“无状态模拟”到“带全局状态的模拟”UVa 118 表面上是一个入门模拟题但它其实暗含了一个非常重要的思维跃迁模拟过程可以修改环境环境反过来会影响后续的模拟步骤。lost数组就是“环境状态”。第一台机器人掉出后环境发生了变化这种变化被记录下来并作用于第二台、第三台机器人。这种“实体行动影响环境环境影响后续实体”的模式在后面的算法题里非常常见。比如迷宫寻路里的“走过的格子不能再走”本质上也是一种环境状态的积累。所以不要把这道题当成简单的“照着走”它值得你多花十分钟想一想lost数组为什么这样设计、为什么必须设成全局的、为什么掉出和忽略会产生完全不同的行为分支。想通这些你的模拟思维会上一个台阶。5.2 构造边界测试的几种实用方法UVa 提交是一次性的没有在线调试所以提交前自己构造边界测试非常关键。我推荐这几个测试思路角落测试把一个机器人放在(0, 0)或(maxX, maxY)朝向朝外让它执行一次F它必须立刻掉出并输出LOST。记忆测试两个机器人走完全相同的路径第一个掉出后第二个在同一个位置再次执行越界指令时必须被拦下最终不出LOST。沿边行走机器人站在边界上但方向与边界平行比如在(0, y)朝N走这一步不应被判定为越界。转向不影响坐标一个机器人连续执行很多次L或R坐标绝对不能变最后的朝向才改变。这些小测试自己跑一遍基本能把所有分支逻辑覆盖住。5.3 这类模拟题给后续算法打下的基础很多人觉得 UVa 118 太简单AC 完就丢掉了。但我想说模拟题是所有算法题的底座。UVa 118 教会你的“先建模、再编码、最后用样例推演验证”的流程做任何题目都用得上。尤其是状态表示这一块坐标用什么变量、方向用什么编码、全局状态用什么结构、指令循环里什么时候 break、什么时候 continue这些判断直接决定代码是简洁清晰还是一团乱麻。把这些基本功练扎实了后面遇到 BFS、DFS、状态压缩 DP 这类更复杂的题才能保证自己在状态转移和边界条件上不犯低级错误。说实话我后来回头看自己 UVa 118 的提交记录最感慨的不是 AC 本身而是第一次 WA 时那种“明明很简单却不明白哪里错”的挫败感。这道题的坑点其实很值得反复品味把它彻底吃透边界处理那一关就算过了大半。