华为非AI方向机考9月23日笔试：YANG模型清洗与迷宫救援

《面试题目》

1. 编程题「边缘模型清洗」（150 分）：云网络设备做自动化部署时要尽快把 YANG 模型装进内存，需要先清掉模型文件里多余的说明文字与初始取值。给定一段多行文本，按以下规则清洗并返回字符串。规则一，删掉关键字 remark、preset、required 所在的整句，删除跨度从关键字第一个字符起到本句结束的 ;（分号也删掉），中间可以跨行。规则二，被删区间内保留换行符 \n，其余字符（空格、正文、分号）全部丢弃；关键字左侧尚未进入区间的缩进原样保留；每一行的条数不增不减。规则三，注释必须原样保留：// 起到行尾为单行注释，/* 到 */ 为可跨行的多行注释。规则四，关键字左侧只能是行首、空格、制表符、{ 或 ;，右侧只能是空格、制表符、换行或 ;，两侧对不上就当成普通名字不删（例如 myremark）。
2. 编程题「迷宫最短救援」（150 分）：给定 h×w 地图，王子从 S 出发要走到公主所在的 P，每次只允许上下左右走一格，越界按墙处理。地图上有若干怪物 M 和一把宝剑 W：未持剑时怪物自身及其上下左右紧邻格都不能踏入；踏入宝剑格即可拾剑；持剑后这些危险格均可进入，踩进怪物格只击倒脚下这一只，其余怪物原地不动；宝剑若正好放在怪物紧邻格上仍可进入拾取；出发格本身位于危险格也不妨碍起步。求到达公主格的最少移动次数，无法到达输出 -1。

《参考解析》

边缘模型清洗：考点是「扫描过程中要同时处理注释、关键字边界、跨行删除三种状态」，本质是一个手写词法扫描器。用一个下标 i 从左往右走：

1. 先看当前位置是不是注释起始。遇到 /* 就一路抄到 */ 并把 i 跳到其后；遇到 // 就抄到这一行的换行（换行也属于这一行）再跳过。注释内部绝对不找关键字，这是正确性的关键——否则注释里写一句「不要设置 remark」也会被误删。
2. 正文里如果从 i 起正好匹配 remark、preset 或 required，还要核对两侧边界。左侧合法字符是行首、空格、制表符、{、;；右侧合法字符是空格、制表符、换行、;。任一侧不满足就当作普通标识符，比如 myremark、remarkable 都不能删。
3. 两侧都合法时，从 i 找到后面第一个 ;，把闭区间 [i, 分号] 里的换行符逐个写进结果、其余字符全部丢弃，然后把 i 设为分号后一位。这样跨行删除时行数不变（空行留着），关键字左侧的缩进因为在区间之外也得以保留。
4. 以上都不命中，就把当前字符原样写入结果，i 前进一格。

复杂度 O(n) 时间、O(n) 空间（n 为输入串长度）。实现上最容易错的三处：忘记处理 find 返回 npos（注释或分号缺失时应直接抄完剩余内容并退出）；把右侧边界写成「非字母数字」而不是白名单（remark: 这种应当不删）；以及读取输入时用 getline 循环拼行会丢掉文件末尾没有换行的最后一行，需要单独处理。

迷宫最短救援：这是一道带状态维度的 BFS，状态设计成 (r, c, sword)，其中 sword 取 0/1 表示尚未持剑与已经持剑。

1. 预处理：先扫一遍地图，把每只怪物所在格及其上下左右相邻格标成危险格，并记下起点 S 的坐标。注意「宝剑格」是个例外——即使它落在危险区里，未持剑时也可进入并拾取。
2. 起点特殊处理：题面明确说出发点就在危险格上也允许，所以初始状态 (sr, sc, 0) 直接入队、距离记 0，不做危险格校验。
3. 扩展时四方向检查：越界与 # 直接跳过；目标格是 W 则新状态 sword = 1；若当前 sword = 0 且目标格是危险格则不能进。持剑进入怪物格不需要额外标记——持剑后所有危险格都开放，哪只怪物被踩死不影响可达性，所以不必记录每只怪物的存活状态。
4. 边权全为 1，用普通 BFS 队列即可。第一次从队列取出写有 P 的格子时，其距离就是最短步数；队列空仍未到达则输出 −1。

复杂度 O(h·w) 时间与空间。这里的思维陷阱是：直觉上会想把「已经杀掉几只怪物」也塞进状态，但那会让状态数爆炸；而题目规则保证了持剑即全图怪物威胁解除，所以 sword 一个 bit 就够了。另一个坑是宝剑格位于危险区时的判定顺序——先后顺序写反（先判危险再判宝剑）会把唯一入口堵死。