华为 · 动态规划 · 算法编程题
华为 动态规划 n ≤ 100 时限 1 秒 / 256 MB

题目描述

十六夜咲夜正准备为蕾米莉亚大小姐端上红茶。红魔馆的走廊可以看作一个 m 行 n 列的网格图。由于大小姐对红茶的平稳度有极高的要求，咲夜在移动时必须遵循极其严格的规则：她只能向右或向下移动。
走廊的每个格点 (i, j) 可能放置了不同的物件。具体定义如下：
- 若格点数值为 0 ，表示该处为空旷的走廊，可以通行。
- 若格点数值为 1, 2, 3, 4 中的任意一种，分别代表家具、电源、孔洞或地线，这些均被视为障碍物，无法通行。
咲夜需要从左上角的厨房 (0, 0) 出发，到达右下角的大小姐房间 (m-1, n-1) 。为了保证红茶不溢出，她希望在移动过程中尽可能减少转向的次数。所谓“转向”，是指移动方向从“向右”变为“向下”，或从“向下”变为“向右”。
请你计算在保证只经过数值为 0 的格点，且仅向右或向下移动的前提下，从起点到终点所需的最少转向次数。

输入输出

输入描述
输入包含一个测试用例。
第一行包含两个整数 m 和 n ( 0 < m, n ≤ 100 )，分别表示走廊的行数和列数。
若 m 和 n 在合法范围内，接下来将有 m 行输入，每行包含 n 个整数，代表网格中每个位置的数值 p_i,j ( 0 ≤ p_i,j ≤ 4 )。
特别地，如果 m 或 n 的取值范围不在 (0, 100] 之内，则视为无效输入。
输出描述
输出一个整数，表示从 (0, 0) 到 (m-1, n-1) 所需的最少转向次数。
如果无法到达终点，或输入维度无效，请输出 -1 。

样例共 1 组

样例 1 · 样例中走廊为 3 × 3 的矩阵。其中 (0, 1) 和 (2, 0) 为障碍物。 从起点 (0, 0) 到终点 (2, 2) 存在以下两条路径： 1. (0,0) → (1,0) → (1,1) → (1,2) → (2,2) ： - 方向变化为：下 → 右（第 1 次转向） → 右 → 下（第 2 次转向）。共转向 2 次。 2. (0,0) → (1,0) → (1,1) → (2,1) → (2,2) ： - 方向变化为：下 → 右（第 1 次转向） → 下（第 2 次转向） → 右（第 3 次转向）。共转向 3 次。 因此，最少转向次数为 2。
输入
3 3
0 1 0
0 0 0
2 0 0
输出
2

算法解析依据充分

考点：动态规划

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

题目画像

  • 数据规模：m ≤ 100，n ≤ 100
  • 元素值域：p_i ≤ 4，j ≤ 4（注意整数类型选择，避免溢出）
  • 复杂度门槛：允许 O(n³) ~ O(n⁴) 的多重循环，可以放心枚举。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：动态规划

本题切入点

只能向右/向下且要最少转向：状态记「到达 (i,j) 时的方向」，转移时若方向改变则计数 +1，障碍格不可达；取两条方向路径的最小转向数，无解输出 −1。

把问题拆成子问题，用状态表示「已处理到哪儿」，靠转移方程递推。

思路框架（动态规划 通法 · 非本题专属）

  1. 定义状态：dp[i] / dp[i][j] 表示什么（这是最关键的一步，状态定义错就全错）。
  2. 写转移方程：当前状态由哪些更小的状态推来。
  3. 确定初始条件与遍历顺序（保证用到的状态已算好）。
  4. 确定答案取哪个状态；数值大时全程取模。

实现要点：一般是「先枚举阶段，再枚举状态，最后枚举决策」三层循环；空间大时可滚动数组优化。

复杂度：时间 O(状态数 × 转移代价) ｜ 空间 O(状态数)

该范式的通法易错点

  • 状态定义不完整（漏了必要维度），导致子问题之间有后效性。
  • 初始化写错（尤其「恰好」与「至多」的初值差别）。
  • 遍历顺序与依赖方向不一致。

对照本题

  • 数据规模 n ≤ 100，允许 O(n³) ~ O(n⁴) 的多重循环，可以放心枚举。
  • 元素值域最大到 4 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 3 3 / 0 1 0 / 0 0 0 / 2 0 0 → 输出 2

样例中走廊为 3 × 3 的矩阵。其中 (0, 1) 和 (2, 0) 为障碍物。

从起点 (0, 0) 到终点 (2, 2) 存在以下两条路径：

  1. (0,0) → (1,0) → (1,1) → (1,2) → (2,2) ：
    • 方向变化为：下 → 右（第 1 次转向） → 右 → 下（第 2 次转向）。共转向 2 次。
    • (0,0) → (1,0) → (1,1) → (2,1) → (2,2) ：
    • 方向变化为：下 → 右（第 1 次转向） → 下（第 2 次转向） → 右（第 3 次转向）。共转向 3 次。

因此，最少转向次数为 2。

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

本题来源：2026年-华为-04月22号开发岗。

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