最近刷到一套新卷的 100 分题题名叫“绘图机器”要求用 Java、JS、Python、C 四门语言分别实现。这题我在本地从建模到测试完整过了一遍踩了不少坑尤其是用不同语言重写同一套逻辑时细节差异比想象中大得多。写这篇算是把整个过程做个复盘给后面遇到类似题的人一条捷径。先说结论这道题本质是一个坐标模拟 路径去重的问题不涉及复杂算法但非常考验基础功底。你只要能把“方向步数”正确转成坐标位移再用合适的数据结构记录线段基本就能拿满分。难的不是思路而是四种语言各自的数据结构表达方式以及边界情况处理。1. 题目定位与核心考点拆解1.1 题面还原绘图机器到底在考什么虽然不同题库里的措辞略有差异但这道题的核心题面可以还原成这样有一个绘图机器初始位置在坐标原点朝向默认方向固定。机器会收到若干条指令每条指令包含方向和步数例如R 3表示向右移动 3 格U 2表示向上移动 2 格。机器每移动一格就会在网格上画出一条长度为 1 的线段。要求输出两样东西第一所有被绘制过的互不重叠的线段总长度第二整个绘图区域的最小包围矩形宽高。注意这里的第一个输出点题目强调的是“互不重叠”。也就是说如果机器走了一段路之后又折返回来重复经过的线段只能算一次。这个条件和普通的路径长度计算完全不同稍不注意就会掉进“按步数累加”的陷阱里。我见过一些同学拿到题就直接totalLength step这样样例可能能过但遇到回环路径就会挂掉。题目之所以给 100 分说明它不是单纯考察循环累加而是在考察你能不能找到一种方式把走过的“几何线段”存下来并去重。第二个输出点最小包围矩形宽高其实是为了逼你去维护坐标的最小值和最大值。有些变体题目只让你输出路径长度不让你输出包围盒但核心逻辑是一样的。1.2 从考点反推解法模拟、建模与去重把考点拆开看其实就三个第一是模拟。机器按照指令顺序移动这个没什么好说的一个 for 循环遍历指令根据方向修改当前坐标就行。关键是要把“方向”翻译成坐标增量的映射关系。我习惯用一个二维方向数组来表达dx和dy分别表示水平、垂直方向的偏移这样代码不会散落一堆 if 分支。第二是建模。走过的路径怎么表示你可以把连续移动拆成“一条一条长度为 1 的小线段”然后考虑每个小线段的存储方式。最简单的做法是针对每一次“从点 A 移动到点 B”把它转成一条有向线段但存储的时候统一成无向的、有序的标准形式。第三是去重。用什么数据结构维护已经走过的线段Java 用HashSetStringPython 用set存元组JS 用SetStringC 语言就看你有没有实现哈希表的经验或者直接用打表标记。这四种方案在工程效率上有差别但对这道题而言都能在限定数据规模内跑完。这么一拆你就明白了解题的核心根本不是“机器人怎么走”而是“怎么把走过的路记录下来保证不重不漏”。这个思维转换就是及格到满分的分水岭。2. 解题思路与建模方法2.1 坐标系统从“方向步数”到向量拆分拿到题目先别急着写代码先在纸上定义清楚坐标系统。我假设网格的 x 轴向右为正y 轴向上为正原点在(0, 0)。虽然网格坐标看起来可以取负数但这不影响计算只要你在记录边界时用变量动态维护即可。方向映射表是固定的这里我给出自己常用的定义Rx 增加 1y 不变即dx1, dy0Lx 减少 1y 不变即dx-1, dy0Uy 增加 1x 不变即dx0, dy1Dy 减少 1x 不变即dx0, dy-1不管哪种语言我都建议用一个二维数组或者两个独立数组来存这四个方向的增量比如写成这样的索引映射int[][] dirs {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};配合一个指令字符到索引的映射函数就能避免写四个几乎一模一样的 if 分支。这样做的好处是后续如果题目改成E、W、N、S这种英文方向词你只需要改映射函数不用动主逻辑。我实测下来这种写法在代码审查时也更容易解释。处理步数的时候一定要“一格一格走”而不是“一次跳三格”。举个例子R 3不是从(0,0)一步跳到(3,0)而是依次经过(1,0)、(2,0)、(3,0)。这是因为你需要把每一条长度为 1 的线段都单独统计和去重如果跳着走中间线段就丢了。虽然一步跳这种写法可以用线段覆盖的方式处理但要额外写区间合并逻辑对这道题来说属于过度设计老老实实单步模拟最容易对。2.2 路径去重线段集合而不是点集合这里有个新手最容易犯的错误用“点”去重而不是用“线段”去重。比如路径R 2再从D 2回来走的是一个 2 乘 2 的方形轮廓如果你只存点相邻的点之间是哪条线段根本没法确定两个点之间甚至可能隔了好几个格子。所以正确做法是把每一次移动产生的线段作为最小单元。我定义一条线段的方式是这样的水平移动当前点(x1, y)移动后到达(x2, y)记录时把两个端点排个序保证左小右大即H:min(x1,x2) - max(x1,x2) y。垂直移动当前点(x, y1)移动后到达(x, y2)同样排序保证下小上大即V:min(y1,y2) - max(y1,y2) x。为什么要排序因为机器从(0,0)向右走到(3,0)和从(3,0)向左走到(0,0)在几何上是同一条线段。如果你不把端点统一排序去重就会失效左走和右走会被当成两条不同的路径。这个细节特别容易踩坑我身边已经不止一个人在这里翻车。每次走完一步就把这条线段的标准形式放进集合里。集合天然去重所以重复走的线段不会增加计数。最终统计时集合的大小就是唯一线段总长度。如果你还要输出包围盒宽高那就顺手在每一步更新minX、maxX、minY、maxY最后输出maxX - minX和maxY - minY即可。2.3 复杂度与数据规模预判这道题的数据规模通常是令人放心的比如指令条数在 1000 条以内单条步长在 1000 以内总步数不超过 100 万。这意味着你用单步模拟时间复杂度是 O(总步数)空间复杂度是 O(唯一线段数)在大多数语言里都能轻松跑进 1 秒。但如果你用打表法就要注意坐标范围。假设单条指令步长最大 1000最坏情况一直在同一个方向走那么坐标跨度就是 100000二维数组是不现实的。不过 C 语言的哈希表实现难度略高这里先卖个关子后面在 C 语言章节我会讲一个既简单又不会爆内存的处理方式。我的建议是不要为了优化而优化直接在 O(总步数) 的模拟逻辑上把去重做好稳健性远比炫技重要。除非题目明确给了超大范围否则单步模拟 集合去重就是最合适的解法。3. 四种语言落地实现3.1 Java 版用 HashSet 存线段注意整型比较Java 版本是我最推荐先写的因为它的语法中规中矩不容易出现隐式类型转换的坑。我在实现时直接用了HashSetStringkey 的生成方式是把线段标准化成字符串。核心逻辑写出来大概是这样import java.util.*; public class Plotter { static String key(int x1, int y1, int x2, int y2) { if (x1 x2) { // 垂直线段 int minY Math.min(y1, y2); int maxY Math.max(y1, y2); return V: x1 : minY - maxY; } else { // 水平线段 int minX Math.min(x1, x2); int maxX Math.max(x1, x2); return H: y1 : minX - maxX; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); SetString lines new HashSet(); int x 0, y 0; int minX 0, maxX 0, minY 0, maxY 0; for (int i 0; i n; i) { String dir sc.next(); int step sc.nextInt(); int dx 0, dy 0; if (dir.equals(R)) { dx 1; } else if (dir.equals(L)) { dx -1; } else if (dir.equals(U)) { dy 1; } else if (dir.equals(D)) { dy -1; } for (int j 0; j step; j) { int nx x dx; int ny y dy; lines.add(key(x, y, nx, ny)); x nx; y ny; minX Math.min(minX, x); maxX Math.max(maxX, x); minY Math.min(minY, y); maxY Math.max(maxY, y); } } System.out.println(lines.size()); System.out.println((maxX - minX) (maxY - minY)); } }这里有几个点想提醒一下。第一key函数里垂直和水平的区分必须依赖 x 或 y 是否相等。如果你只是简单判断x1 x2是垂直反过来就是水平那么注意在水平移动时 y 始终不变所以字符串里直接用y1就行不需要再排序 y垂直移动同理x 始终不变排序 y 即可。这样生成的 key 是唯一的不会把两条不同线段混淆。第二Java 里很多初学者在dir.equals(R)这里会出错如果dir是 Scanner 读进来的字符串一般不会为 null但严谨起见建议用常量放在前面比如R.equals(dir)防止空指针。虽然本题不会碰到但好习惯要养成。第三输出时注意题目要求的是“宽 高”还是先宽后高的具体顺序别搞反了。我自己在调的时候因为样例看起来像是普通矩形一时分不清谁先谁后最后是重新读了一遍题才确定的。写题之前花十秒确认输出格式能省后面十分钟的调试。3.2 Python 版元组字典一把梭Python 是我个人觉得写这题最舒服的语言因为它的set天然支持元组而元组正好是我在 2.2 节定义的标准化线段。代码量可以压缩得非常短而且可读性不降反升。核心实现如下我保留了完整的注释方便你看懂每一步def line_key(x1, y1, x2, y2): if x1 x2: return (V, x1, min(y1, y2), max(y1, y2)) else: return (H, y1, min(x1, x2), max(x1, x2)) def solve(): n int(input()) x, y 0, 0 min_x, max_x, min_y, max_y 0, 0, 0, 0 lines set() dir_map { R: (1, 0), L: (-1, 0), U: (0, 1), D: (0, -1), } for _ in range(n): d, step input().split() dx, dy dir_map[d] step int(step) for _ in range(step): nx, ny x dx, y dy lines.add(line_key(x, y, nx, ny)) x, y nx, ny min_x min(min_x, x) max_x max(max_x, x) min_y min(min_y, y) max_y max(max_y, y) print(len(lines)) print(f{max_x - min_x} {max_y - min_y}) solve()Python 版本的优点在于不用费心设计字符串 key直接用元组就行。注意元组的元素顺序必须和我的标准定义一致先标识横竖方向再写不变的坐标最后写排序后的两个端点。比如水平线段(H, y, smallX, bigX)垂直线段(V, x, smallY, bigY)。这里的坑在于如果你用(H, y, x1, x2)但不排序 x1 和 x2那么在反向行走时就会出现两条不同 key 的线段去重失效。我见过有人用 tuple 就以为自动去重了结果忽略了内部顺序问题最后答案比预期大一倍。排序这个动作一定要显式写出来。另外Python 的input()读取速度在数据量大时会慢但此题总步数不超过几十万完全够用。如果你实在担心可以用sys.stdin.buffer.read().split()一次性读入实测性能差别不大但写起来优雅很多。3.3 JavaScript 版字符串拼接做 key性能别担心Node.js 环境下写这道题最大的问题是Set的语义。JS 的Set虽然能存对象但对象的比较是基于引用而不是结构所以不能直接存数组或对象。最稳妥的方式就是像 Java 一样用字符串做 key然后存进SetString。我之前也试过用二维数组模拟坐标但是发现坐标可能为负后就打消了这个念头。字符串做了一个干净利落的替代方案虽然拼接和比较可能比哈希稍慢一点但对这道题的数据量来说可以忽略不计。实现如下重点是key函数的生成function lineKey(x1, y1, x2, y2) { if (x1 x2) { const low Math.min(y1, y2); const high Math.max(y1, y2); return V:${x1}:${low}-${high}; } const low Math.min(x1, x2); const high Math.max(x1, x2); return H:${y1}:${low}-${high}; } function solve(input) { const data input.trim().split(/\s/); let pos 0; const n parseInt(data[pos]); const lines new Set(); let x 0, y 0; let minX 0, maxX 0, minY 0, maxY 0; const dirMap { R: [1, 0], L: [-1, 0], U: [0, 1], D: [0, -1], }; for (let i 0; i n; i) { const d data[pos]; const step parseInt(data[pos]); const [dx, dy] dirMap[d]; for (let j 0; j step; j) { const nx x dx; const ny y dy; lines.add(lineKey(x, y, nx, ny)); x nx; y ny; minX Math.min(minX, x); maxX Math.max(maxX, x); minY Math.min(minY, y); maxY Math.max(maxY, y); } } console.log(lines.size); console.log(${maxX - minX} ${maxY - minY}); }JS 里有一个隐藏陷阱Set的大小取的是size属性不是length方法。我平时写习惯了数组一不留神就想用lines.length结果输出undefined。这个错其实很容易规避只要你意识到 JS 的集合对象和数组是两码事。还有一点如果你是在浏览器环境练习注意input需要自己定义好读取方式。如果是 Node.js 环境我推荐用fs.readFileSync(/dev/stdin, utf8)读入全部内容。网上很多平台的 JS 示例写得比较简陋你要学会自己封装输入解析函数这样换平台也能直接用。3.4 C 版哈希表别硬写打表标记才稳C 语言版本是这个题最容易让不少人卡住的地方因为 C 标准库里没有现成的哈希表。我在第一次动手时还想着手写一个链表哈希表存线段写着写着发现代码量翻了一倍调试成本也高。后来转念一想这题的坐标范围是有上限的可以直接采用“坐标偏置 三维标记数组”的方案。思路是这样的先把所有坐标整体平移到非负区域。比如我统计到最小 x 值和最小 y 值然后把每个点都加上偏移量让 minX 对应到 0minY 对应到 0。这样在数组里就不会出现负数下标。接下来开一个三维数组第一维标记水平方向第二维标记垂直方向。具体做法是#define MAXN 2005 int h[MAXN][MAXN]; // h[x][y] 表示以 (x, y) 为左端点的水平线段是否走过 int v[MAXN][MAXN]; // v[x][y] 表示以 (x, y) 为下端点的垂直线段是否走过这里2005是根据步长上限保守估计的如果你不确定可以预先把可能出现的最远坐标算出来最大步长乘以指令数量再留出偏移余量。当然如果题目数据范围比较小例如单条步长不超过 100指令不超过 10那么 2005 的空间绰绰有余。在单步移动时判断当前产生的线段是否被访问过若没有则计数加一。注意保持“小坐标作为记录基准点”的习惯#include stdio.h #include string.h #define MAXN 2005 int h[MAXN][MAXN]; int v[MAXN][MAXN]; int main() { memset(h, 0, sizeof(h)); memset(v, 0, sizeof(v)); int n; scanf(%d, n); int x 1000, y 1000; // 给初始坐标一个安全偏移 int minX x, maxX x, minY y, maxY y; int total 0; for (int i 0; i n; i) { char d[4]; int step; scanf(%s %d, d, step); int dx 0, dy 0; if (d[0] R) dx 1; else if (d[0] L) dx -1; else if (d[0] U) dy 1; else if (d[0] D) dy -1; for (int j 0; j step; j) { int nx x dx; int ny y dy; if (x nx) { // 垂直线段用较低的点作为标记基准 int lowY y ny ? y : ny; int highY y ny ? y : ny; int px x; if (!v[px][lowY]) { v[px][lowY] 1; total; } } else { // 水平线段用较左的点作为标记基准 int lowX x nx ? x : nx; int highX x nx ? x : nx; int py y; if (!h[lowX][py]) { h[lowX][py] 1; total; } } x nx; y ny; if (x minX) minX x; if (x maxX) maxX x; if (y minY) minY y; if (y maxY) maxY y; } } printf(%d\n, total); printf(%d %d\n, maxX - minX, maxY - minY); return 0; }这里我把初始坐标设成(1000, 1000)而不是(0, 0)就是为了给负数方向留出偏移空间。你如果愿意也可以先读一遍指令求出理论上的 minX 和 minY再加偏移但那样会多写一遍循环。对大多数数据规模来说固定偏移1000已经足够安全。只要你保证1000 最小可能坐标 0即可而最小可能坐标大约是- 单条步长上限 / 2 * 指令条数这个值在常规题里远大于负 1000。如果你不确定宁可在建表前先动态算偏移也不要把数组开小了。C 版本的哈希数组虽然简单但有一个代价二维数组占用的空间固定即使实际走过的线段很少空间也照样分配。以2005 * 2005为例两个 int 数组大约是 800 万字节也就是接近 32MB在一般内存限制下完全可以接受。如果内存限制很严格那就需要把数组类型改成char或bool进一步压缩到 8MB。回过头来再说一句C 语言不是不能手写哈希只是在这个题上打表法更直观、更不容易出 bug。工程上永远是“够用就好”这个思路放到其它坐标类题目里一样适用。4. 实测中的常见问题与排查技巧4.1 坐标负数与数组越界做 C 语言版本的初期我遇到的第一个问题就是负数坐标。如果直接用mark[x][y]当作数组下标只要坐标出现负数数组就访问越界程序直接崩溃。这个问题在 Java、Python、JS 里不突出因为它们可以用哈希表但 C 语言必须正视。我给出的解决方案就是前面说的坐标偏置。不管实际坐标是多少都先加上一个足够大的偏移量让所有坐标变成非负整数。偏移量的选择原则是大于等于所有可能出现的最小坐标的绝对值。稳妥起见我建议在写代码前先读一遍全部指令计算一下理论上的 minX 和 minY然后取绝对值向上取整再加一个余量。不过有些平台的输入是需要边读边处理的不能预先读第二遍那就在初始坐标上给足偏移例如 2000只要题目不出现极端大的负方向移动就不会撞边界。如果你发现h[lowX][py]或v[px][lowY]报数组越界多半就是偏移量给少了。这时不要急着改数组大小先把坐标打印出来看看最极端的位置到底是多少再反推需要的偏移。4.2 重复线段到底算几次这是最容易让答案出错的地方而且平台给出的样例经常比较刁钻专门设计成让重复路径出现。我印象最深的一个测试用例是先R 3再L 3在正确逻辑下唯一线段长度是 3但如果直接按步数累加会得到 6。我最初在 Java 版本里把 key 写成了“当前点 - 移动后点”的有序字符串结果R 3和L 3生成的 key 不一样去重完全失效答案直接翻倍。后来我把 key 设计成“排序后的端点 方向标志”问题立刻解决。这里我再强调一遍存储线段时一定要先把端点排序确保同一条几何线段的表示形式唯一。同理在 Python 版本中(H, y, minX, maxX)和(H, y, maxX, minX)是两条不同的元组你必须在放入集合前手动排序。还有一种情况是“跨步重合”比如R 2之后再R 2但实际只覆盖了新的 2 格其中前 2 格与前半段重合。我的单步模拟方式天然解决了这个问题因为每格线段都会单独和已有集合做比对重复的会被自动忽略。你要是用“跳跃式”模拟就得额外处理区间合并那才是真的自找麻烦。4.3 把调试输出玩明白不管哪种语言我调试时都习惯在每一步打印当前坐标、生成的 key 以及当前集合大小。Java 里我会临时在循环体里加一句System.err.println(...)Python 里用print(..., filesys.stderr)JS 里用console.errorC 语言直接fprintf(stderr, ...)。这样不会干扰正常的标准输出提交前删掉即可。一个实用的技巧是先构造一个非常小的用例比如只有两三条指令手动在纸上画出路径数出期望的线段数然后跑代码看输出是否一致。我一般用“回字形”路径来测去重逻辑因为它包含了顺走、逆走、上下交叉能一次性暴露 key 设计的问题。比如这样的测试4 R 2 U 2 L 2 D 2在纸上画出来是一个 2x2 的方块重复线段没有唯一线段应该是 8 条包围盒是 2 2。如果输出不是 8说明 key 生成有问题。再比如2 R 3 L 3期望是 3 和 3 0如果输出 6说明去重没生效。4.4 测试用例设计与压力测试提交之前我习惯至少准备四类测试用例。第一类是最简单的单方向直线比如R 5期望输出 5 和 5 0。第二类是回环路径用来测去重。第三类是负坐标路径比如先L 2再D 2确认初始坐标偏移是否足够。第四类是交叉路径目的是让水平和垂直线段交错验证 key 不会把“水平”和“垂直”搞混。压力测试我可以直接生成大量随机指令步长也在合理范围随机取值然后让 Java 版和 Python 版互相对拍输出。如果两个版本结果一致那么正确性基本就有保证了。互相对拍是我写了几年算法题之后养成的习惯比单纯看自己的逻辑强很多因为两个独立实现的代码同时出同样 bug 的概率极低。对 C 语言版额外还要检查内存如果开了两个大数组注意栈空间是否够用。我的经验是把大数组定义成全局变量而不是放在main函数内部否则某些环境默认栈空间只有几 MB运行时会直接爆栈。4.5 不同变体的应对思路“绘图机器”在不少题库里会有变体。有些只要求输出路径总长度有些要求输出覆盖的格子数而不是线段数还有些会把方向改成英文单词East、West等。面对变体我的建议是回到定义上想清楚题目要的到底是“线”还是“面”还是“长度”。如果是覆盖格子数那就要换个建模方式把走过的格子坐标直接存进集合因为格子覆盖的语义和线段不同。如果只要路径总长度那你可以直接把所有步数加起来因为路径总长度本质就是总步数但要注意题目是否要求去重后的长度这个描述一定要看清。应对变体的核心能力就是把题干描述精准翻译成数据模型而不是死记某种题型的模板。5. 经验总结与最后的建议这道题做完之后我最大的感受是算法题的差距往往不在“会不会思路”而在“能不能用目标语言把思路表达得干净利落”。Java 和 Python 的集合类型非常好用但 C 语言里必须靠打表或手写哈希来替代这本身就是一道很好的语言特性对比题。你把这题的四种写法都过一遍基本上就能摸清这些语言在“存储不重复元素”这件事上的各自套路。实操上还有一个建议别在一开始就追求四种语言全部优化到最短。先选你最熟悉的语言把逻辑跑通再照着同样思路翻译到其它语言。翻译的时候只改数据结构表达方式不改算法骨架这样定位 bug 会容易得多。我一开始就同时开四个文件写结果一个语言报错我要在其他三个里同时核对效率大打折扣。最后再分享一个调试时的小技巧如果你发现输出结果比预期大一倍基本可以断定是去重失效重点检查 key 的生成和端点排序如果你发现输出结果比预期小很多那很可能是某些线段被错误地合并了检查是不是在水平判断和垂直判断里写错了条件。这两类错误占了这题调试问题的九成以上方向对了排查就快了。 
长河君 · 2026/10/10 2:36:03 · 阅读 1.2k 绘图机器题解：四语言实现坐标模拟与线段去重
最近刷到一套新卷的 100 分题题名叫“绘图机器”要求用 Java、JS、Python、C 四门语言分别实现。这题我在本地从建模到测试完整过了一遍踩了不少坑尤其是用不同语言重写同一套逻辑时细节差异比想象中大得多。写这篇算是把整个过程做个复盘给后面遇到类似题的人一条捷径。先说结论这道题本质是一个坐标模拟 路径去重的问题不涉及复杂算法但非常考验基础功底。你只要能把“方向步数”正确转成坐标位移再用合适的数据结构记录线段基本就能拿满分。难的不是思路而是四种语言各自的数据结构表达方式以及边界情况处理。1. 题目定位与核心考点拆解1.1 题面还原绘图机器到底在考什么虽然不同题库里的措辞略有差异但这道题的核心题面可以还原成这样有一个绘图机器初始位置在坐标原点朝向默认方向固定。机器会收到若干条指令每条指令包含方向和步数例如R 3表示向右移动 3 格U 2表示向上移动 2 格。机器每移动一格就会在网格上画出一条长度为 1 的线段。要求输出两样东西第一所有被绘制过的互不重叠的线段总长度第二整个绘图区域的最小包围矩形宽高。注意这里的第一个输出点题目强调的是“互不重叠”。也就是说如果机器走了一段路之后又折返回来重复经过的线段只能算一次。这个条件和普通的路径长度计算完全不同稍不注意就会掉进“按步数累加”的陷阱里。我见过一些同学拿到题就直接totalLength step这样样例可能能过但遇到回环路径就会挂掉。题目之所以给 100 分说明它不是单纯考察循环累加而是在考察你能不能找到一种方式把走过的“几何线段”存下来并去重。第二个输出点最小包围矩形宽高其实是为了逼你去维护坐标的最小值和最大值。有些变体题目只让你输出路径长度不让你输出包围盒但核心逻辑是一样的。1.2 从考点反推解法模拟、建模与去重把考点拆开看其实就三个第一是模拟。机器按照指令顺序移动这个没什么好说的一个 for 循环遍历指令根据方向修改当前坐标就行。关键是要把“方向”翻译成坐标增量的映射关系。我习惯用一个二维方向数组来表达dx和dy分别表示水平、垂直方向的偏移这样代码不会散落一堆 if 分支。第二是建模。走过的路径怎么表示你可以把连续移动拆成“一条一条长度为 1 的小线段”然后考虑每个小线段的存储方式。最简单的做法是针对每一次“从点 A 移动到点 B”把它转成一条有向线段但存储的时候统一成无向的、有序的标准形式。第三是去重。用什么数据结构维护已经走过的线段Java 用HashSetStringPython 用set存元组JS 用SetStringC 语言就看你有没有实现哈希表的经验或者直接用打表标记。这四种方案在工程效率上有差别但对这道题而言都能在限定数据规模内跑完。这么一拆你就明白了解题的核心根本不是“机器人怎么走”而是“怎么把走过的路记录下来保证不重不漏”。这个思维转换就是及格到满分的分水岭。2. 解题思路与建模方法2.1 坐标系统从“方向步数”到向量拆分拿到题目先别急着写代码先在纸上定义清楚坐标系统。我假设网格的 x 轴向右为正y 轴向上为正原点在(0, 0)。虽然网格坐标看起来可以取负数但这不影响计算只要你在记录边界时用变量动态维护即可。方向映射表是固定的这里我给出自己常用的定义Rx 增加 1y 不变即dx1, dy0Lx 减少 1y 不变即dx-1, dy0Uy 增加 1x 不变即dx0, dy1Dy 减少 1x 不变即dx0, dy-1不管哪种语言我都建议用一个二维数组或者两个独立数组来存这四个方向的增量比如写成这样的索引映射int[][] dirs {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};配合一个指令字符到索引的映射函数就能避免写四个几乎一模一样的 if 分支。这样做的好处是后续如果题目改成E、W、N、S这种英文方向词你只需要改映射函数不用动主逻辑。我实测下来这种写法在代码审查时也更容易解释。处理步数的时候一定要“一格一格走”而不是“一次跳三格”。举个例子R 3不是从(0,0)一步跳到(3,0)而是依次经过(1,0)、(2,0)、(3,0)。这是因为你需要把每一条长度为 1 的线段都单独统计和去重如果跳着走中间线段就丢了。虽然一步跳这种写法可以用线段覆盖的方式处理但要额外写区间合并逻辑对这道题来说属于过度设计老老实实单步模拟最容易对。2.2 路径去重线段集合而不是点集合这里有个新手最容易犯的错误用“点”去重而不是用“线段”去重。比如路径R 2再从D 2回来走的是一个 2 乘 2 的方形轮廓如果你只存点相邻的点之间是哪条线段根本没法确定两个点之间甚至可能隔了好几个格子。所以正确做法是把每一次移动产生的线段作为最小单元。我定义一条线段的方式是这样的水平移动当前点(x1, y)移动后到达(x2, y)记录时把两个端点排个序保证左小右大即H:min(x1,x2) - max(x1,x2) y。垂直移动当前点(x, y1)移动后到达(x, y2)同样排序保证下小上大即V:min(y1,y2) - max(y1,y2) x。为什么要排序因为机器从(0,0)向右走到(3,0)和从(3,0)向左走到(0,0)在几何上是同一条线段。如果你不把端点统一排序去重就会失效左走和右走会被当成两条不同的路径。这个细节特别容易踩坑我身边已经不止一个人在这里翻车。每次走完一步就把这条线段的标准形式放进集合里。集合天然去重所以重复走的线段不会增加计数。最终统计时集合的大小就是唯一线段总长度。如果你还要输出包围盒宽高那就顺手在每一步更新minX、maxX、minY、maxY最后输出maxX - minX和maxY - minY即可。2.3 复杂度与数据规模预判这道题的数据规模通常是令人放心的比如指令条数在 1000 条以内单条步长在 1000 以内总步数不超过 100 万。这意味着你用单步模拟时间复杂度是 O(总步数)空间复杂度是 O(唯一线段数)在大多数语言里都能轻松跑进 1 秒。但如果你用打表法就要注意坐标范围。假设单条指令步长最大 1000最坏情况一直在同一个方向走那么坐标跨度就是 100000二维数组是不现实的。不过 C 语言的哈希表实现难度略高这里先卖个关子后面在 C 语言章节我会讲一个既简单又不会爆内存的处理方式。我的建议是不要为了优化而优化直接在 O(总步数) 的模拟逻辑上把去重做好稳健性远比炫技重要。除非题目明确给了超大范围否则单步模拟 集合去重就是最合适的解法。3. 四种语言落地实现3.1 Java 版用 HashSet 存线段注意整型比较Java 版本是我最推荐先写的因为它的语法中规中矩不容易出现隐式类型转换的坑。我在实现时直接用了HashSetStringkey 的生成方式是把线段标准化成字符串。核心逻辑写出来大概是这样import java.util.*; public class Plotter { static String key(int x1, int y1, int x2, int y2) { if (x1 x2) { // 垂直线段 int minY Math.min(y1, y2); int maxY Math.max(y1, y2); return V: x1 : minY - maxY; } else { // 水平线段 int minX Math.min(x1, x2); int maxX Math.max(x1, x2); return H: y1 : minX - maxX; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); SetString lines new HashSet(); int x 0, y 0; int minX 0, maxX 0, minY 0, maxY 0; for (int i 0; i n; i) { String dir sc.next(); int step sc.nextInt(); int dx 0, dy 0; if (dir.equals(R)) { dx 1; } else if (dir.equals(L)) { dx -1; } else if (dir.equals(U)) { dy 1; } else if (dir.equals(D)) { dy -1; } for (int j 0; j step; j) { int nx x dx; int ny y dy; lines.add(key(x, y, nx, ny)); x nx; y ny; minX Math.min(minX, x); maxX Math.max(maxX, x); minY Math.min(minY, y); maxY Math.max(maxY, y); } } System.out.println(lines.size()); System.out.println((maxX - minX) (maxY - minY)); } }这里有几个点想提醒一下。第一key函数里垂直和水平的区分必须依赖 x 或 y 是否相等。如果你只是简单判断x1 x2是垂直反过来就是水平那么注意在水平移动时 y 始终不变所以字符串里直接用y1就行不需要再排序 y垂直移动同理x 始终不变排序 y 即可。这样生成的 key 是唯一的不会把两条不同线段混淆。第二Java 里很多初学者在dir.equals(R)这里会出错如果dir是 Scanner 读进来的字符串一般不会为 null但严谨起见建议用常量放在前面比如R.equals(dir)防止空指针。虽然本题不会碰到但好习惯要养成。第三输出时注意题目要求的是“宽 高”还是先宽后高的具体顺序别搞反了。我自己在调的时候因为样例看起来像是普通矩形一时分不清谁先谁后最后是重新读了一遍题才确定的。写题之前花十秒确认输出格式能省后面十分钟的调试。3.2 Python 版元组字典一把梭Python 是我个人觉得写这题最舒服的语言因为它的set天然支持元组而元组正好是我在 2.2 节定义的标准化线段。代码量可以压缩得非常短而且可读性不降反升。核心实现如下我保留了完整的注释方便你看懂每一步def line_key(x1, y1, x2, y2): if x1 x2: return (V, x1, min(y1, y2), max(y1, y2)) else: return (H, y1, min(x1, x2), max(x1, x2)) def solve(): n int(input()) x, y 0, 0 min_x, max_x, min_y, max_y 0, 0, 0, 0 lines set() dir_map { R: (1, 0), L: (-1, 0), U: (0, 1), D: (0, -1), } for _ in range(n): d, step input().split() dx, dy dir_map[d] step int(step) for _ in range(step): nx, ny x dx, y dy lines.add(line_key(x, y, nx, ny)) x, y nx, ny min_x min(min_x, x) max_x max(max_x, x) min_y min(min_y, y) max_y max(max_y, y) print(len(lines)) print(f{max_x - min_x} {max_y - min_y}) solve()Python 版本的优点在于不用费心设计字符串 key直接用元组就行。注意元组的元素顺序必须和我的标准定义一致先标识横竖方向再写不变的坐标最后写排序后的两个端点。比如水平线段(H, y, smallX, bigX)垂直线段(V, x, smallY, bigY)。这里的坑在于如果你用(H, y, x1, x2)但不排序 x1 和 x2那么在反向行走时就会出现两条不同 key 的线段去重失效。我见过有人用 tuple 就以为自动去重了结果忽略了内部顺序问题最后答案比预期大一倍。排序这个动作一定要显式写出来。另外Python 的input()读取速度在数据量大时会慢但此题总步数不超过几十万完全够用。如果你实在担心可以用sys.stdin.buffer.read().split()一次性读入实测性能差别不大但写起来优雅很多。3.3 JavaScript 版字符串拼接做 key性能别担心Node.js 环境下写这道题最大的问题是Set的语义。JS 的Set虽然能存对象但对象的比较是基于引用而不是结构所以不能直接存数组或对象。最稳妥的方式就是像 Java 一样用字符串做 key然后存进SetString。我之前也试过用二维数组模拟坐标但是发现坐标可能为负后就打消了这个念头。字符串做了一个干净利落的替代方案虽然拼接和比较可能比哈希稍慢一点但对这道题的数据量来说可以忽略不计。实现如下重点是key函数的生成function lineKey(x1, y1, x2, y2) { if (x1 x2) { const low Math.min(y1, y2); const high Math.max(y1, y2); return V:${x1}:${low}-${high}; } const low Math.min(x1, x2); const high Math.max(x1, x2); return H:${y1}:${low}-${high}; } function solve(input) { const data input.trim().split(/\s/); let pos 0; const n parseInt(data[pos]); const lines new Set(); let x 0, y 0; let minX 0, maxX 0, minY 0, maxY 0; const dirMap { R: [1, 0], L: [-1, 0], U: [0, 1], D: [0, -1], }; for (let i 0; i n; i) { const d data[pos]; const step parseInt(data[pos]); const [dx, dy] dirMap[d]; for (let j 0; j step; j) { const nx x dx; const ny y dy; lines.add(lineKey(x, y, nx, ny)); x nx; y ny; minX Math.min(minX, x); maxX Math.max(maxX, x); minY Math.min(minY, y); maxY Math.max(maxY, y); } } console.log(lines.size); console.log(${maxX - minX} ${maxY - minY}); }JS 里有一个隐藏陷阱Set的大小取的是size属性不是length方法。我平时写习惯了数组一不留神就想用lines.length结果输出undefined。这个错其实很容易规避只要你意识到 JS 的集合对象和数组是两码事。还有一点如果你是在浏览器环境练习注意input需要自己定义好读取方式。如果是 Node.js 环境我推荐用fs.readFileSync(/dev/stdin, utf8)读入全部内容。网上很多平台的 JS 示例写得比较简陋你要学会自己封装输入解析函数这样换平台也能直接用。3.4 C 版哈希表别硬写打表标记才稳C 语言版本是这个题最容易让不少人卡住的地方因为 C 标准库里没有现成的哈希表。我在第一次动手时还想着手写一个链表哈希表存线段写着写着发现代码量翻了一倍调试成本也高。后来转念一想这题的坐标范围是有上限的可以直接采用“坐标偏置 三维标记数组”的方案。思路是这样的先把所有坐标整体平移到非负区域。比如我统计到最小 x 值和最小 y 值然后把每个点都加上偏移量让 minX 对应到 0minY 对应到 0。这样在数组里就不会出现负数下标。接下来开一个三维数组第一维标记水平方向第二维标记垂直方向。具体做法是#define MAXN 2005 int h[MAXN][MAXN]; // h[x][y] 表示以 (x, y) 为左端点的水平线段是否走过 int v[MAXN][MAXN]; // v[x][y] 表示以 (x, y) 为下端点的垂直线段是否走过这里2005是根据步长上限保守估计的如果你不确定可以预先把可能出现的最远坐标算出来最大步长乘以指令数量再留出偏移余量。当然如果题目数据范围比较小例如单条步长不超过 100指令不超过 10那么 2005 的空间绰绰有余。在单步移动时判断当前产生的线段是否被访问过若没有则计数加一。注意保持“小坐标作为记录基准点”的习惯#include stdio.h #include string.h #define MAXN 2005 int h[MAXN][MAXN]; int v[MAXN][MAXN]; int main() { memset(h, 0, sizeof(h)); memset(v, 0, sizeof(v)); int n; scanf(%d, n); int x 1000, y 1000; // 给初始坐标一个安全偏移 int minX x, maxX x, minY y, maxY y; int total 0; for (int i 0; i n; i) { char d[4]; int step; scanf(%s %d, d, step); int dx 0, dy 0; if (d[0] R) dx 1; else if (d[0] L) dx -1; else if (d[0] U) dy 1; else if (d[0] D) dy -1; for (int j 0; j step; j) { int nx x dx; int ny y dy; if (x nx) { // 垂直线段用较低的点作为标记基准 int lowY y ny ? y : ny; int highY y ny ? y : ny; int px x; if (!v[px][lowY]) { v[px][lowY] 1; total; } } else { // 水平线段用较左的点作为标记基准 int lowX x nx ? x : nx; int highX x nx ? x : nx; int py y; if (!h[lowX][py]) { h[lowX][py] 1; total; } } x nx; y ny; if (x minX) minX x; if (x maxX) maxX x; if (y minY) minY y; if (y maxY) maxY y; } } printf(%d\n, total); printf(%d %d\n, maxX - minX, maxY - minY); return 0; }这里我把初始坐标设成(1000, 1000)而不是(0, 0)就是为了给负数方向留出偏移空间。你如果愿意也可以先读一遍指令求出理论上的 minX 和 minY再加偏移但那样会多写一遍循环。对大多数数据规模来说固定偏移1000已经足够安全。只要你保证1000 最小可能坐标 0即可而最小可能坐标大约是- 单条步长上限 / 2 * 指令条数这个值在常规题里远大于负 1000。如果你不确定宁可在建表前先动态算偏移也不要把数组开小了。C 版本的哈希数组虽然简单但有一个代价二维数组占用的空间固定即使实际走过的线段很少空间也照样分配。以2005 * 2005为例两个 int 数组大约是 800 万字节也就是接近 32MB在一般内存限制下完全可以接受。如果内存限制很严格那就需要把数组类型改成char或bool进一步压缩到 8MB。回过头来再说一句C 语言不是不能手写哈希只是在这个题上打表法更直观、更不容易出 bug。工程上永远是“够用就好”这个思路放到其它坐标类题目里一样适用。4. 实测中的常见问题与排查技巧4.1 坐标负数与数组越界做 C 语言版本的初期我遇到的第一个问题就是负数坐标。如果直接用mark[x][y]当作数组下标只要坐标出现负数数组就访问越界程序直接崩溃。这个问题在 Java、Python、JS 里不突出因为它们可以用哈希表但 C 语言必须正视。我给出的解决方案就是前面说的坐标偏置。不管实际坐标是多少都先加上一个足够大的偏移量让所有坐标变成非负整数。偏移量的选择原则是大于等于所有可能出现的最小坐标的绝对值。稳妥起见我建议在写代码前先读一遍全部指令计算一下理论上的 minX 和 minY然后取绝对值向上取整再加一个余量。不过有些平台的输入是需要边读边处理的不能预先读第二遍那就在初始坐标上给足偏移例如 2000只要题目不出现极端大的负方向移动就不会撞边界。如果你发现h[lowX][py]或v[px][lowY]报数组越界多半就是偏移量给少了。这时不要急着改数组大小先把坐标打印出来看看最极端的位置到底是多少再反推需要的偏移。4.2 重复线段到底算几次这是最容易让答案出错的地方而且平台给出的样例经常比较刁钻专门设计成让重复路径出现。我印象最深的一个测试用例是先R 3再L 3在正确逻辑下唯一线段长度是 3但如果直接按步数累加会得到 6。我最初在 Java 版本里把 key 写成了“当前点 - 移动后点”的有序字符串结果R 3和L 3生成的 key 不一样去重完全失效答案直接翻倍。后来我把 key 设计成“排序后的端点 方向标志”问题立刻解决。这里我再强调一遍存储线段时一定要先把端点排序确保同一条几何线段的表示形式唯一。同理在 Python 版本中(H, y, minX, maxX)和(H, y, maxX, minX)是两条不同的元组你必须在放入集合前手动排序。还有一种情况是“跨步重合”比如R 2之后再R 2但实际只覆盖了新的 2 格其中前 2 格与前半段重合。我的单步模拟方式天然解决了这个问题因为每格线段都会单独和已有集合做比对重复的会被自动忽略。你要是用“跳跃式”模拟就得额外处理区间合并那才是真的自找麻烦。4.3 把调试输出玩明白不管哪种语言我调试时都习惯在每一步打印当前坐标、生成的 key 以及当前集合大小。Java 里我会临时在循环体里加一句System.err.println(...)Python 里用print(..., filesys.stderr)JS 里用console.errorC 语言直接fprintf(stderr, ...)。这样不会干扰正常的标准输出提交前删掉即可。一个实用的技巧是先构造一个非常小的用例比如只有两三条指令手动在纸上画出路径数出期望的线段数然后跑代码看输出是否一致。我一般用“回字形”路径来测去重逻辑因为它包含了顺走、逆走、上下交叉能一次性暴露 key 设计的问题。比如这样的测试4 R 2 U 2 L 2 D 2在纸上画出来是一个 2x2 的方块重复线段没有唯一线段应该是 8 条包围盒是 2 2。如果输出不是 8说明 key 生成有问题。再比如2 R 3 L 3期望是 3 和 3 0如果输出 6说明去重没生效。4.4 测试用例设计与压力测试提交之前我习惯至少准备四类测试用例。第一类是最简单的单方向直线比如R 5期望输出 5 和 5 0。第二类是回环路径用来测去重。第三类是负坐标路径比如先L 2再D 2确认初始坐标偏移是否足够。第四类是交叉路径目的是让水平和垂直线段交错验证 key 不会把“水平”和“垂直”搞混。压力测试我可以直接生成大量随机指令步长也在合理范围随机取值然后让 Java 版和 Python 版互相对拍输出。如果两个版本结果一致那么正确性基本就有保证了。互相对拍是我写了几年算法题之后养成的习惯比单纯看自己的逻辑强很多因为两个独立实现的代码同时出同样 bug 的概率极低。对 C 语言版额外还要检查内存如果开了两个大数组注意栈空间是否够用。我的经验是把大数组定义成全局变量而不是放在main函数内部否则某些环境默认栈空间只有几 MB运行时会直接爆栈。4.5 不同变体的应对思路“绘图机器”在不少题库里会有变体。有些只要求输出路径总长度有些要求输出覆盖的格子数而不是线段数还有些会把方向改成英文单词East、West等。面对变体我的建议是回到定义上想清楚题目要的到底是“线”还是“面”还是“长度”。如果是覆盖格子数那就要换个建模方式把走过的格子坐标直接存进集合因为格子覆盖的语义和线段不同。如果只要路径总长度那你可以直接把所有步数加起来因为路径总长度本质就是总步数但要注意题目是否要求去重后的长度这个描述一定要看清。应对变体的核心能力就是把题干描述精准翻译成数据模型而不是死记某种题型的模板。5. 经验总结与最后的建议这道题做完之后我最大的感受是算法题的差距往往不在“会不会思路”而在“能不能用目标语言把思路表达得干净利落”。Java 和 Python 的集合类型非常好用但 C 语言里必须靠打表或手写哈希来替代这本身就是一道很好的语言特性对比题。你把这题的四种写法都过一遍基本上就能摸清这些语言在“存储不重复元素”这件事上的各自套路。实操上还有一个建议别在一开始就追求四种语言全部优化到最短。先选你最熟悉的语言把逻辑跑通再照着同样思路翻译到其它语言。翻译的时候只改数据结构表达方式不改算法骨架这样定位 bug 会容易得多。我一开始就同时开四个文件写结果一个语言报错我要在其他三个里同时核对效率大打折扣。最后再分享一个调试时的小技巧如果你发现输出结果比预期大一倍基本可以断定是去重失效重点检查 key 的生成和端点排序如果你发现输出结果比预期小很多那很可能是某些线段被错误地合并了检查是不是在水平判断和垂直判断里写错了条件。这两类错误占了这题调试问题的九成以上方向对了排查就快了。