华为OD机考的C卷里贪吃蛇这道题几乎是常驻题目。我第一次在双机位环境下看到它时还以为是道休闲题结果写着写着发现不对劲蛇身怎么存、撞到自己怎么判断、指令G到底往哪走……这些细节全挤在一起稍不留神就漏掉一个分支。网上能搜到的题解大多只给一种语言这次我按平时刷题和实战的习惯把Java、Python、JS、C/C、Go五种写法全部过了一遍顺便把每一步为什么这么设计讲清楚。无论你是准备OD机考还是在刷算法面试里的模拟题这篇都能直接用上。1. C卷贪吃蛇的考点拆解模拟流程、队列与边界判定1.1 这类题目的常见输入形式与考点这道题本质上是一个网格模拟题。常见的输入结构是先给一个 n 行 m 列的二维地图地图上有两种格子0 表示空地1 表示食物初始时蛇头在 (0,0)蛇身长度是 1。接下来给一串移动指令每个指令是一个字符可能是 U、D、L、R、G最后要求输出游戏结束时蛇的长度。考点其实很明确就三个二维网格上的坐标移动需要会写方向数组比如dx {-1,1,0,0}、dy {0,0,-1,1}。蛇身是动态变长的序列需要支持“头插入、尾删除”这是双端队列的经典场景。碰撞检测要快每次移动都要判断蛇头是不是撞到了自己的身体哈希集合是首选。题目本身不难难的是把规则完完整整地模拟出来尤其是吃食物和没吃食物这两种情况下蛇身的变化完全不一样。1.2 为什么看着简单考场上却写不对我在双机位答题的时候最大的感受就是这道题太容易“看着会、写完错”了。主要原因有三个。第一蛇的移动不是单纯换一个坐标。蛇头往前走一步之后如果没吃到食物蛇尾就要往前缩一节如果吃到食物蛇尾不能缩。很多人第一版代码只处理了蛇头位置的更新忘了动蛇尾结果跑出来蛇身越来越长。第二撞自己的判断时机很微妙。蛇头撞到蛇身中间某个格子那肯定死但如果蛇头刚好走到蛇尾巴所在的那一格呢这个格子很快会被释放按真实贪吃蛇的规则是不算死的。这个细节如果题目描述不说清楚实现起来非常容易踩坑。第三G指令的语义。G不是独立方向它表示“沿着当前方向继续前进”。也就是说前面出现过什么方向指令G就沿用那个方向。如果没维护好“当前方向”这个状态连续执行几个G之后蛇就会到处乱跑。这道题送分是因为方向数组加队列人人都会难拿满分是因为边界分支太多少一条就错一个测试用例。2. 规则细节抠细G指令含义与碰撞判定顺序2.1 U/D/L/R 与 G 的真实关系先说结论U、D、L、R 这四个字符每个都包含两层含义——先把当前方向改成对应方向然后蛇头朝这个方向前进一格。而单独的 G 不改变方向只是沿用之前的方向前进一格。比如指令序列是D G R G那实际移动过程是D方向改为下蛇头从 (0,0) 走到 (1,0)G方向仍是下蛇头走到 (2,0)R方向改为右蛇头走到 (2,1)G方向仍是右蛇头走到 (2,2)这段逻辑里最重要的变量就是“当前方向”。每次遇到 U/D/L/R要立刻更新每次遇到 G不能动方向只做移动。我见过不少人把 U/D/L/R 当成“只转向、不移动”然后让 G 承担唯一的前进动作这样也不是完全不行但与原题常见语义不符。考试时如果没把握可以自己在样例上试几种解释看哪种能推出题目对应的输出但那样很浪费时间。更稳妥的做法是第一时间确定题目对 G 的定义再动手写代码。2.2 四类目标的处理优先级蛇每走一步新位置只可能是四种情况墙外、空地、食物、蛇身。判断顺序建议这样先算新头坐标。判断是否越界越界直接结束游戏。如果新位置是食物把这个格子从食物变成空地然后判断新头是否撞到身体没撞到就把新头插到队首蛇尾不动长度自然加 1。如果新位置是空地先把蛇尾从队列里弹出来从身体集合里删掉再判断新头是否撞到剩余的身体没撞到就把新头插到队首。这里有个容易搞错的地方判断是否撞到身体必须在处理完食物或者空地之后再做。因为“空地”分支里蛇尾已经移走了蛇身集合已经缩小如果先判断撞身体很可能会把本来不撞的情况误判成撞死。2.3 尾巴那格到底算不算障碍这个问题值得单独拿出来说。假设蛇身长 2尾巴在蛇头正前方下一步蛇头往前走正好踏进尾巴当前所在的格子。按物理直觉蛇在移动的一瞬间尾巴已经离开头部可以顺利进入所以不算撞死。实现这个效果只需要在“空地”分支里先把尾巴从 body 集合中删掉再检查新头是否在 body 集合里。代码顺序对了这个细节自然就正确。但如果你先判断body.contains(newHead)再删尾巴那尾巴所在的格子还在集合里就会误判死亡。这个顺序问题我之前自己写 C 版本时就错过一次调试了半天才反应过来。3. 数据结构选型双端队列存蛇身哈希集合管碰撞3.1 用数组平移蛇身的致命问题有人第一反应是用一个二维数组模拟整个地图蛇身每个格子都标记一下。蛇移动时把整条蛇的每个坐标都往后平移一格。这个方法在小数据量下也能跑但有两个明显问题每次移动都要遍历整条蛇身长度越长越慢复杂度是 O(蛇长)。代码写起来很啰嗦平移的时候很容易把顺序搞乱。机考场景要求的是尽快写出正确代码而不是炫技。用双端队列加哈希集合就是最省心、最不容易出错的组合。3.2 Deque 与 Set 的分工双端队列负责维护蛇身的顺序队首是蛇头队尾是蛇尾。吃到食物时只往队首插入新头队尾不动没吃到食物时先弹队尾再往队首插新头。哈希集合负责快速判断碰撞。每次移动前把新头坐标转成字符串或者直接存二维坐标放进集合里查一下就能知道是不是撞到自己。这里有个细节为什么不用队列自己来判断碰撞因为队列只能从两端操作要判断某个坐标是否在队列里必须遍历整个队列复杂度又变成了 O(蛇长)。所以必须额外维护一个集合让查询变成 O(1)。3.3 核心流程伪代码把完整流程写成伪代码大概是这样的初始化 dir 无方向 snake 队头(0,0) body {(0,0)} for op in 指令序列: if op 是 U/D/L/R: dir 对应方向 本次移动方向 dir 的方向增量 else if op 是 G: 本次移动方向 dir 的方向增量 else: 跳过 根据蛇头坐标加上方向增量得到新头坐标 if 新头越界: break if 新头位置是食物: 把食物格子改成空地 if 新头在 body 中: break 新头插入队首 新头加入 body else: 弹出队尾并从 body 中删除 if 新头在 body 中: break 新头插入队首 新头加入 body 输出 snake 的长度后面五种语言的代码全部按照这个流程来写保证行为一致。4. 五种语言的实现与各自最容易踩的坑4.1 JavaLinkedList 和 SetStringJava 实现里蛇身队列我用LinkedList因为它实现了Deque接口支持addFirst、pollLast这类两端操作。身体集合用SetString存x,y这样的字符串简单直观。import java.util.*; public class Main { static final int[] DX {-1, 1, 0, 0}; static final int[] DY {0, 0, -1, 1}; public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); sc.nextLine(); char[][] grid new char[n][m]; for (int i 0; i n; i) { String line sc.nextLine().replace( , ); for (int j 0; j m; j) { grid[i][j] line.charAt(j); } } StringBuilder sb new StringBuilder(); while (sc.hasNext()) { sb.append(sc.next()); } String ops sb.toString(); Dequeint[] snake new LinkedList(); SetString body new HashSet(); snake.addFirst(new int[]{0, 0}); body.add(0,0); int dir -1; for (char op : ops.toCharArray()) { if (op U) dir 0; else if (op D) dir 1; else if (op L) dir 2; else if (op R) dir 3; else if (op G) { if (dir -1) break; } else { continue; } int[] head snake.peekFirst(); int nx head[0] DX[dir]; int ny head[1] DY[dir]; if (nx 0 || nx n || ny 0 || ny m) break; if (grid[nx][ny] 1) { grid[nx][ny] 0; if (body.contains(nx , ny)) break; snake.addFirst(new int[]{nx, ny}); body.add(nx , ny); } else { int[] tail snake.pollLast(); body.remove(tail[0] , tail[1]); if (body.contains(nx , ny)) break; snake.addFirst(new int[]{nx, ny}); body.add(nx , ny); } } System.out.println(snake.size()); } }Java 最容易踩的坑是两个一是nextInt()之后直接nextLine()会读到换行符必须先补一次nextLine()二是SetString删除尾巴时要确保字符串格式统一1,2和1, 2是不同字符串很容易栽在这里。4.2 Pythondeque 与元组的天然搭配Python 的collections.deque和元组几乎是给这道题量身定做的。appendleft是头插入pop是尾删除元组可以直接放进set里不需要转字符串。import sys from collections import deque def main(): input sys.stdin.readline n, m map(int, input().split()) grid [] for _ in range(n): line input().strip().replace( , ) grid.append(list(line)) ops .join(line.strip().replace( , ) for line in sys.stdin) delta {U: (-1, 0), D: (1, 0), L: (0, -1), R: (0, 1)} snake deque([(0, 0)]) body {(0, 0)} cur_dir None for op in ops: if op in delta: cur_dir op dx, dy delta[op] elif op G: if cur_dir is None: break dx, dy delta[cur_dir] else: continue hx, hy snake[0] nx, ny hx dx, hy dy if not (0 nx n and 0 ny m): break if grid[nx][ny] 1: grid[nx][ny] 0 if (nx, ny) in body: break snake.appendleft((nx, ny)) body.add((nx, ny)) else: tx, ty snake.pop() body.remove((tx, ty)) if (nx, ny) in body: break snake.appendleft((nx, ny)) body.add((nx, ny)) print(len(snake)) if __name__ __main__: main()Python 要注意的是输入读取。如果题目把指令放在一行直接input()也能读但更稳的写法是像上面这样用sys.stdin把剩余内容全部读出来再拼成一个字符串这样指令即使跨多行也不会出问题。4.3 JavaScript数组模拟队列与 Set 存字符串JS 没有内置双端队列我直接用数组模拟unshift在头部插入pop在尾部弹出。题目数据量一般不大这样写完全够用。身体集合用Set存字符串不能用数组引用。const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); const lines []; rl.on(line, (line) lines.push(line)); rl.on(close, () { const [n, m] lines[0].split( ).map(Number); const grid []; for (let i 0; i n; i) { grid.push(lines[1 i].replace(/ /g, ).split()); } const ops lines.slice(1 n).join().replace(/ /g, ); const delta { U: [-1, 0], D: [1, 0], L: [0, -1], R: [0, 1] }; const snake [[0, 0]]; const body new Set([0,0]); let dir ; for (const op of ops) { let dx, dy; if (delta[op]) { dir op; dx delta[op][0]; dy delta[op][1]; } else if (op G) { if (!dir) break; dx delta[dir][0]; dy delta[dir][1]; } else { continue; } const nx snake[0][0] dx; const ny snake[0][1] dy; if (nx 0 || nx n || ny 0 || ny m) break; if (grid[nx][ny] 1) { grid[nx][ny] 0; if (body.has(nx , ny)) break; snake.unshift([nx, ny]); body.add(nx , ny); } else { const tail snake.pop(); body.delete(tail[0] , tail[1]); if (body.has(nx , ny)) break; snake.unshift([nx, ny]); body.add(nx , ny); } } console.log(snake.length); });JS 最大的坑在Set上。如果你直接body.add([nx, ny])然后再body.has([nx, ny])结果是false因为数组是按引用比较的两个不同的数组对象不是同一个东西。所以必须用字符串nx , ny而且拼接格式要始终一致不能一会儿用逗号一会儿用别的分隔符。4.4 C/Ccin 读字符与 setpairint,int 的便利C 的输入处理有个天然优势cin char会自动跳过空白符。不管地图行是0 1 0还是010连续读 n*m 个字符都能正确读入。指令也一样一直读到文件结束把每个非空白字符收进字符串就行。#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; vectorvectorchar grid(n, vectorchar(m)); for (int i 0; i n; i) { for (int j 0; j m; j) { cin grid[i][j]; } } string ops; char ch; while (cin ch) { ops.push_back(ch); } dequepairint, int snake; setpairint, int body; snake.push_front({0, 0}); body.insert({0, 0}); int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; int dir -1; for (char op : ops) { if (op U) dir 0; else if (op D) dir 1; else if (op L) dir 2; else if (op R) dir 3; else if (op G) { if (dir -1) break; } else { continue; } int nx snake.front().first dx[dir]; int ny snake.front().second dy[dir]; if (nx 0 || nx n || ny 0 || ny m) break; if (grid[nx][ny] 1) { grid[nx][ny] 0; if (body.count({nx, ny})) break; snake.push_front({nx, ny}); body.insert({nx, ny}); } else { auto tail snake.back(); snake.pop_back(); body.erase(tail); if (body.count({nx, ny})) break; snake.push_front({nx, ny}); body.insert({nx, ny}); } } cout snake.size() endl; return 0; }C 里我建议直接用setpairint,int不要转字符串。pair自带比较规则count和erase用起来非常顺手代码读起来也清晰。唯一的坑是dequepairint,int的front()返回的是引用用的时候别不小心改到蛇头就行。4.5 Go切片模拟与结构体 map keyGo 的标准库没有双端队列常见选择是container/list或者直接用切片。为了代码简单可读我这里用切片模拟头部前插用append([]Point{np}, snake...)尾删用snake[:len(snake)-1]。数据量不大的时候这个写法的性能完全够用。package main import ( bufio fmt os strings ) type Point struct{ x, y int } func main() { sc : bufio.NewScanner(os.Stdin) sc.Scan() var n, m int fmt.Sscanf(sc.Text(), %d %d, n, m) grid : make([][]byte, n) for i : 0; i n; i { sc.Scan() grid[i] []byte(strings.ReplaceAll(sc.Text(), , )) } var ops []byte for sc.Scan() { ops append(ops, strings.ReplaceAll(sc.Text(), , )...) } delta : map[byte]Point{ U: {-1, 0}, D: {1, 0}, L: {0, -1}, R: {0, 1}, } snake : []Point{{0, 0}} body : map[Point]bool{{0, 0}: true} var dir byte hasDir : false for _, op : range ops { var step Point if d, ok : delta[op]; ok { dir op hasDir true step d } else if op G { if !hasDir { break } step delta[dir] } else { continue } head : snake[0] np : Point{head.x step.x, head.y step.y} if np.x 0 || np.x n || np.y 0 || np.y m { break } if grid[np.x][np.y] 1 { grid[np.x][np.y] 0 if body[np] { break } snake append([]Point{np}, snake...) body[np] true } else { tail : snake[len(snake)-1] snake snake[:len(snake)-1] delete(body, tail) if body[np] { break } snake append([]Point{np}, snake...) body[np] true } } fmt.Println(len(snake)) }Go 要注意一点map[Point]bool里Point必须是可以比较的类型这里struct{ x, y int }完全满足。如果你图省事想用map[[2]int]bool也可以[2]int同样是可比较类型。我个人倾向用结构体语义更清晰。5. 手算用例推演与机考现场的防呆建议5.1 参考用例手工推演看一个能同时验证指令和食物逻辑的用例3 3 0 1 0 0 0 1 1 0 0 D R G手工推演初始蛇头 (0,0)长度 1。D方向向下蛇头走到 (1,0)该格是空地尾部 (0,0) 移除蛇身只剩 (1,0)长度 1。R方向向右蛇头走到 (1,1)该格是食物长度变成 2蛇身是 [(1,1), (1,0)]。G方向仍是右蛇头走到 (1,2)该格是空地尾部 (1,0) 移除新头加入蛇身是 [(1,2), (1,1)]长度 2。最终输出 2。拿这段样例去测五种语言的代码结果应该完全一致。5.2 撞墙、追尾、连续G的边界场景我把几个容易出问题的场景整理成一张表方便考试前快速过一眼场景输入预期输出说明撞墙结束2 2 地图全0指令D D1第二次向下越界游戏结束追尾不死2 2 地图全0指令D R U2最后一步走到原尾巴位置尾巴已释放不撞连续G沿用方向3 3 地图全0指令R G G1R到(0,1)两个G分别到(0,2)和越界吃到食物后蛇尾不动3 3 地图第二行中间是1指令R D G2R吃到食物变2后续保持长度2追尾那个用例是争议点。按我的实现D R U在 2x2 地图上D头到 (1,0)长度 1R头到 (1,1)长度 2蛇身 [(1,1), (1,0)]U头到 (0,1)该格空地先弹出尾巴 (1,0)再判断 (0,1) 是否在剩余身体中不在加入所以输出 2。如果某个版本把“判断包含尾巴”放在删尾之前这里就会输出 1那就是错的。5.3 输入解析兼容空格的写法机考的输入格式有时候会在数字之间带空格有时候不带。地图行可能是0 1 0也可能是010指令行可能是R G D G也可能是RGDG。我上面五种语言的实现都做了空格兼容。特别提醒两点Java 和 Python 读取地图时先把整行字符串里的空格去掉再去按字符取。JS 用正则replace(/ /g, )只去空格不要把\t之类的也忽略机考输入一般不会有 tab。C 用cin char天然跳过空白这是 C 输入最省心的地方。Go 用strings.ReplaceAll去空格指令部分用循环读取剩余所有行再拼接。5.4 机考现场的几个防呆建议我写这道题踩过的坑集中在下面几点考前看一眼有帮助。第一先确认 G 的语义再动手。如果题目描述里说“G表示沿当前方向前进”就一定要维护方向变量如果 G 不存在那就更简单忽略即可。不要想当然读题比写代码更重要。第二蛇头的碰撞判断永远放在边界判断之后。先算新坐标先查越界再查身体。顺序反了可能出现数组越界访问直接导致程序异常退出这是机考最亏的情况。第三吃食物之后记得把地图上那一格改成 0。不然蛇身离开后那一格会一直被认为是食物下次走到同一个位置又会无脑加长长度就错了。第四调试时别只盯着长度。可以手动把蛇身坐标打印出来一步步看蛇尾有没有正确删除。很多时候长度看起来对但中间状态已经错了只是碰巧没被测试用例抓到。第五不要过度优化。用Deque、用Set、用方向数组这套组合在数据量大的情况下也完全够用。别在考场上为了省一点内存去写链表自实现那不划算。第五点其实也是我个人的体会这道题的价值不在“会不会贪吃蛇”而在“能不能把一个带状态、带边界的模拟过程写稳”。把判断顺序理清楚、把数据结构选对五种语言都是同一套逻辑剩下就是翻译成语法而已。