大厂真题 / 华为

华为 8.26 笔试真题 - 研发岗

本场考试概述

考试时间：2026 年 8 月 26 日

考试岗位：研发岗

难度评级：中等

考点分析：

居民区工厂选址：曼哈顿距离拆维 + 带权中位数。
机器人清洁系统：只能向右或向下的网格路径动态规划。
小鲤鱼荒岛逃生：BFS 最短路 + 多级比较规则下的路径还原。

前两题的重点是识别经典模型；第三题除了求最短距离，还要依次处理出口坐标、路径行坐标和、路径列坐标和四级比较条件。

第 1 题：居民区工厂选址

题目描述

二维平面上有 $n$ 个居民区，第 $i$ 个居民区位于 $({x_i},{y_i})$，共有 $p_i$ 名居民。现在选择一个点 $(X,Y)$ 建设工厂，使所有居民到工厂的加权曼哈顿距离之和最小。

第 $i$ 个居民区产生的代价为：

\[p_i\bigl(\lvert x_i-X\rvert+\lvert y_i-Y\rvert\bigr).\]

求最小总代价。

输入描述

第一行输入整数 $n$，满足 $1\le n\le 10^4$。

接下来 $n$ 行，每行输入三个整数 $x_i,y_i,p_i$，满足 $-10^9\le x_i,y_i\le 10^9$，$1\le p_i\le 10^4$。

输出描述

输出最小的加权曼哈顿距离之和。

样例

输入

输出

思路分析

曼哈顿距离可以按横、纵坐标拆开：

\[\sum_{i=1}^{n}p_i\lvert x_i-X\rvert+\sum_{i=1}^{n}p_i\lvert y_i-Y\rvert.\]

两个部分没有公共变量，因此分别求出一维最优解再相加即可。

考虑一维问题。把所有点按坐标排序，总权重记为 $W$。当选址从左向右移动时，左侧点的距离增大，右侧点的距离减小；一旦左侧累计权重达到总权重的一半，继续右移就不会让总代价更小。因此，首个满足累计权重至少为 $\lceil W/2\rceil$ 的坐标就是带权中位数。

横、纵坐标分别排序并求带权中位数，再扫描所有点累加距离即可。坐标差与总权重的乘积可能达到 $10^{17}$ 量级，计算过程需要使用 64 位整数；Python 整数可直接处理。

题解代码

import sys


def minimum_cost_1d(points):
    points.sort()
    total_weight = sum(weight for _, weight in points)
    target = (total_weight + 1) // 2

    prefix_weight = 0
    median = points[0][0]
    for coordinate, weight in points:
        prefix_weight += weight
        if prefix_weight >= target:
            median = coordinate
            break

    return sum(weight * abs(coordinate - median) for coordinate, weight in points)


def solve():
    input = sys.stdin.buffer.readline
    n = int(input())
    x_points = []
    y_points = []

    for _ in range(n):
        x, y, population = map(int, input().split())
        x_points.append((x, population))
        y_points.append((y, population))

    print(minimum_cost_1d(x_points) + minimum_cost_1d(y_points))


if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度：$O(n\log n)$，主要开销是分别对横、纵坐标排序。

空间复杂度：$O(n)$，用于保存两个维度的坐标和权重。

易错点

普通中位数不考虑居民数量，本题必须求带权中位数。
横、纵坐标应分别处理，但使用同一个居民数量作为权重。
固定宽度语言中需要使用 64 位整数保存答案。

第 2 题：机器人清洁系统

题目描述

机器人位于一个 $m\times n$ 的网格房间，需要从左上角 $(0,0)$ 移动到右下角 $(m-1,n-1)$，每次只能向右或向下移动一格。

每个格子有一个非负整数，表示该处的灰尘浓度。机器人从浓度为 $a$ 的格子移动到浓度为 $b$ 的相邻格子时，需要消耗 $\lvert b-a\rvert$ 单位调节能量。求所有合法路径中的最小总能耗。

输入描述

第一行输入两个整数 $m,n$，满足 $1\le m,n\le 200$。

接下来 $m$ 行，每行输入 $n$ 个整数，表示网格中的灰尘浓度，数值范围为 $[0,10000]$。

输出描述

输出从左上角到右下角的最小总调节能耗。

样例

输入

1 5
1 2 3 4 5

输出

思路分析

每一步的能耗只取决于当前格和前一个格，不依赖更早的移动过程，因此可以使用动态规划。

令 dp[j] 表示处理到当前行时，从起点走到当前列格子的最小能耗。对格子 $(i,j)$：

从上方到达时，候选值是原 dp[j] 加上下两个格子的浓度差；
从左侧到达时，候选值是更新后的 dp[j-1] 加左右两个格子的浓度差。

取两个合法来源中的较小值。按从上到下、从左到右的顺序更新，就能把二维状态压缩为一行。单行、单列和 $1\times1$ 网格都能由同一套边界逻辑处理。

题解代码

import sys


def solve():
    input = sys.stdin.buffer.readline
    m, n = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(m)]

    infinity = 10**30
    dp = [infinity] * n
    dp[0] = 0

    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                continue

            best = infinity
            if i > 0:
                best = dp[j] + abs(grid[i][j] - grid[i - 1][j])
            if j > 0:
                from_left = dp[j - 1] + abs(grid[i][j] - grid[i][j - 1])
                best = min(best, from_left)
            dp[j] = best

    print(dp[-1])


if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度：$O(mn)$，每个格子只进行常数次计算。

空间复杂度：$O(n)$，滚动数组只保存当前行的状态；输入网格占用的存储不计入额外空间。

易错点

起点不产生移动能耗，初始值应为 0。
更新当前行时，dp[j] 仍代表上方状态，而 dp[j-1] 已代表左侧状态。
移动代价是相邻格数值之差的绝对值，不是目标格自身的数值。

第 3 题：小鲤鱼荒岛逃生

题目描述

给定一个 $m\times n$ 的岛屿地图：0 表示水域，1 表示陆域。小鲤鱼从指定位置出发，只能在水域中向上、下、左、右移动。如果到达矩阵边界上的水域格，就能逃回河流。

需要输出最短逃生路径。如果存在多条候选路径，按以下优先级选择：

移动步数更少；
最终出口坐标按行、列字典序更小；
路径上所有点的行坐标之和更小；
路径上所有点的列坐标之和更小。

题目保证无需处理以上四项全部相同但路径仍不同的情况。

输入描述

第一行输入两个整数 $m,n$，满足 $3\le m\le 20$，$3\le n\le 30$。

第二行输入起点坐标 $p_0,p_1$，坐标从 0 开始。

接下来 $m$ 行，每行输入 $n$ 个 0 或 1。

输出描述

如果无法逃生，输出 -1。

否则第一行输出最少移动步数 $d$，随后输出 $d+1$ 行路径坐标，其中第一行为起点，最后一行为出口。

样例

输入

输出

思路分析

所有移动的代价都是 1，因此先从起点执行 BFS，得到每个可达水域格的最短距离 dist。在所有可达边界格中，按 (距离, 行, 列) 取最小值，就确定了题目规则中的最短步数和出口坐标。

出口确定后，还要在所有通向该出口的最短路径中比较坐标和。BFS 距离把图划分成若干层，一条最短路径只能从距离为 $d-1$ 的格子走向距离为 $d$ 的格子。

对每个格子 $v$，记录从起点到它的最优 (行坐标和, 列坐标和)，并保存对应前驱。处理 $v$ 时，只枚举满足 dist[u] + 1 == dist[v] 的相邻格 $u$。所有候选都会加上同一个当前坐标，所以直接选前驱累计坐标和字典序最小者即可。按照 BFS 发现顺序处理时，前一层状态必定已经完成。

最后从出口沿前驱回溯，再反转得到完整路径。若起点是陆域，或起点所在水域与任意边界都不连通，则输出 -1。

题解代码

import sys
from collections import deque


def solve():
    input = sys.stdin.buffer.readline
    m, n = map(int, input().split())
    start_row, start_col = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(m)]

    if grid[start_row][start_col] == 1:
        print(-1)
        return

    directions = ((-1, 0), (1, 0), (0, -1), (0, 1))
    dist = [[-1] * n for _ in range(m)]
    queue = deque([(start_row, start_col)])
    order = [(start_row, start_col)]
    dist[start_row][start_col] = 0

    while queue:
        row, col = queue.popleft()
        for delta_row, delta_col in directions:
            next_row = row + delta_row
            next_col = col + delta_col
            if not (0 <= next_row < m and 0 <= next_col < n):
                continue
            if grid[next_row][next_col] == 1 or dist[next_row][next_col] != -1:
                continue
            dist[next_row][next_col] = dist[row][col] + 1
            queue.append((next_row, next_col))
            order.append((next_row, next_col))

    exits = []
    for row, col in order:
        if row == 0 or row == m - 1 or col == 0 or col == n - 1:
            exits.append((dist[row][col], row, col))

    if not exits:
        print(-1)
        return

    _, target_row, target_col = min(exits)

    best_sum = [[None] * n for _ in range(m)]
    parent = [[None] * n for _ in range(m)]
    best_sum[start_row][start_col] = (start_row, start_col)

    for row, col in order[1:]:
        best_candidate = None
        best_parent = None
        for delta_row, delta_col in directions:
            prev_row = row + delta_row
            prev_col = col + delta_col
            if not (0 <= prev_row < m and 0 <= prev_col < n):
                continue
            if dist[prev_row][prev_col] != dist[row][col] - 1:
                continue

            prev_sum = best_sum[prev_row][prev_col]
            candidate = (prev_sum[0] + row, prev_sum[1] + col)
            if best_candidate is None or candidate < best_candidate:
                best_candidate = candidate
                best_parent = (prev_row, prev_col)

        best_sum[row][col] = best_candidate
        parent[row][col] = best_parent

    path = []
    current = (target_row, target_col)
    while current is not None:
        path.append(current)
        row, col = current
        current = parent[row][col]
    path.reverse()

    print(len(path) - 1)
    for row, col in path:
        print(row, col)


if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度：$O(mn)$，BFS 和分层前驱转移都只检查每个格子的四个方向。

空间复杂度：$O(mn)$，用于保存距离、累计坐标和、前驱与队列。

易错点

题目坐标从 0 开始，输出时不要额外加一。
不能只依赖 BFS 邻居访问顺序决定路径，多级比较规则必须显式计算。
选择出口时先比较距离，再比较出口的行、列；路径坐标和只在出口确定后参与比较。
输出的步数不包含起点，但路径坐标包含起点，因此共输出 d + 1 个坐标。

小结

第一题利用曼哈顿距离可拆维的性质，把二维选址转化为两个一维带权中位数问题。
第二题识别每步代价只依赖相邻格，使用滚动数组完成网格路径动态规划。
第三题先用 BFS 固定最短距离与出口，再在最短路分层图上按坐标和选择前驱。

这篇文章有帮助吗？

| GitHub 留言