华为 · 穷举 · 算法编程题
华为 穷举 n ≤ 15 时限 2 秒 / 256 MB

题目描述

小红从奇数行列网格的中心出发。每一步先向上下左右之一移动，越界则停在原地；随后在所在格执行增加、减少或无操作。给出一条原轨迹，请求出最短语义等价轨迹长度：所有格子的最终值相同，且最终位置相同。
每次增减参数在 [1,100] 。题目保证最终非零格不超过 12 个，且每个最终非零值的绝对值不超过 100，因此到达该格一次即可完成其净操作。注意起点不能在移动前直接操作。

输入输出

输入描述
第一行输入奇数 n,m ；第二行输入原轨迹长度 K ；随后 K 行输入 `move op param`。
保证 3≤ n,m≤15 ， 1≤ K≤2000 ，move 为 U/D/L/R，op 为 I/D/N；N 的参数为 0，其余参数在 [1,100] 。最终非零格数量不超过 12，绝对值不超过 100。
输出描述
输出最短等价轨迹的步数。

样例共 2 组

样例 1 · 聚合每格净操作后，只需访问非零格并到达原终点。
输入
3 3
5
U I 1
U I 2
R D 1
D I 3
R I 1
输出
3
样例 2 · 存在长度为 4 的等价轨迹。
输入
5 5
6
R I 2
R D 1
U I 3
L I 1
D D 2
R I 4
输出
4

算法解析依据充分

考点：穷举

数据规模 n ≤ 15 ｜ 限制 2 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：K ≤ 2000，n ≤ 15，m ≤ 15
  • 复杂度门槛：允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。
  • 源站时限：2 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：穷举

本题切入点

最终非零格不超过 12 个，等价于「用最短步数依次访问这些格并完成净增减」：枚举访问顺序（可状压 DP 剪枝）+ 累加格间曼哈顿距离，取最小总步数。

把候选答案空间全部列出来逐一检验，靠数据范围小来兜底。

思路框架（穷举 通法 · 非本题专属）

  1. 确定枚举什么（下标区间 / 子集 / 数值）。
  2. 用一层或多层循环（或递归）生成所有候选。
  3. 对每个候选判断是否满足题目条件，满足就统计或更新最优值。
  4. 先按数据范围估算枚举量，确认不会超时。

实现要点：多重循环是最直接的写法；枚举组合时可用递归 + 回溯，或用位掩码代表子集。

复杂度：时间 O(候选数 × 单次校验代价) ｜ 空间 O(1)

该范式的通法易错点

  • 没先估复杂度，枚举量超出时限（这是最常见的超时原因）。
  • 去重没做好，同一种方案被多次统计。

对照本题

  • 数据规模 n ≤ 15，允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。

样例解读

样例 1：输入 3 3 / 5 / U I 1 / U I 2 / R D 1 / D I 3 / R I 1 → 输出 3

聚合每格净操作后，只需访问非零格并到达原终点。

样例 2：输入 5 5 / 6 / R I 2 / R D 1 / U I 3 / L I 1 / D D 2 / R I 4 → 输出 4

存在长度为 4 的等价轨迹。

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2026年-华为-07月15号AI岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解