华为 · 计算几何 · 算法编程题
华为 计算几何 n ≤ 256 时限 1 秒 / 256 MB

题目描述

小红在一栋两层楼中寻找最短救援路径。每层都是 m × n 网格：`0` 为空地，`1` 为墙，`2` 为唯一起点，`3` 为唯一终点，`4` 为楼梯。每层恰有一个楼梯。
同层可向上下左右移动一格，耗时 1 ；站在楼梯格时，可以用 1 步到达另一层的楼梯格，两层楼梯坐标不必相同。除楼梯外不能跨层。
求起点到终点的最少步数，无法到达时输出 -1 。

输入输出

输入描述
第一行输入 m,n 。接下来先输入第一层的 m 行，再输入第二层的 m 行，每行 n 个整数。
保证 2 ≤ m,n ≤ 256 ；起点、终点各一个，每层楼梯各一个，三类位置互不重叠。
输出描述
输出最少步数，无法到达输出 -1 。

样例共 2 组

样例 1 · 先到达第一层楼梯，用一步到另一层楼梯，再前往终点。
输入
3 3
2 0 1
0 1 4
0 0 0
0 4 0
1 0 1
1 0 3
输出
9
样例 2 · 墙壁阻断了所有可行路径。
输入
2 2
2 0
4 1
4 1
1 3
输出
-1

算法解析依据一般

考点：计算几何

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

题目画像

  • 数据规模：m ≤ 256，n ≤ 256
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：计算几何

把几何关系转成坐标运算，用整数运算避免浮点误差。

思路框架（计算几何 通法 · 非本题专属）

  1. 把点、向量、线段用坐标表示。
  2. 几何判定（平行、垂直、共线、相交）尽量用叉积/点积的整数形式：叉积为 0 即共线。
  3. 距离用平方比较，避免开方带来的浮点误差。
  4. 面积用叉积（鞋带公式）计算。

实现要点：叉积 cross = x1*y2 - x2*y1；用它判断顺时针/逆时针和共线。

复杂度：时间 O(n) ~ O(n²) ｜ 空间 O(n)

该范式的通法易错点

  • 用浮点相等判断几何关系（应用整数叉积）。
  • 没考虑三点共线、重合等退化情况。

对照本题

  • 数据规模 n ≤ 256，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例解读

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

先到达第一层楼梯，用一步到另一层楼梯，再前往终点。

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

墙壁阻断了所有可行路径。

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

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

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