4.19华为OD机试真题 新系统 - WIFI设备网络规划 (JavaPyCC++JsGo)

WIFI设备网络规划2026 华为OD机试真题 4月19日华为OD上机新系统考试真题 200 分题型点击查看华为 OD 机试真题完整目录2026最新华为OD机试新系统卷 双机位C卷 真题题库目录全覆盖题库 逐点算法考点详解题目描述WIFI网络中专业的网络规划不仅可以提升业务体验还可以减少部署成本。把办公区可以看作一个n* m的网格部分网格包含墙壁(无法放置AP(WI一FI设备)部分为空地(可以放置AP)。每个AP覆盖范围是一个3*3的正方形(包括自身位置、上下左右、以及对角线区域)且AP和AP的覆盖区域不能重叠防止相互干扰。现在给定一个mx n(不超过50 * 50)的网络布局图(墙壁用字符#表示空地用字符.表示)请设计一个算法计算最少放置多少数量的AP来覆盖所有空地?如果不能按条件完成覆盖请返回-1。2026 华为OD机试真题 4月19日华为OD上机新系统考试真题 200 分题型输入描述第一行输入 m n接下来m行输入每一行字符输出描述最少放置多少数量的AP来覆盖所有空地?如果不能按条件完成覆盖请返回-1。示例1输入7 7 ....... ....... ....... ...#... ....... ....... .......输出1说明放置一个 AP 在 (1, 1) 位置即可覆盖周围 3x3 区域。示例2输入5 5 ..#.. ..#.. ..#.. ..#.. ..#..输出4说明解题思路核心思想该问题可以建模为一个精确覆盖问题Exact Cover Problem的变体。我们需要在网格中的空地.上放置最少数量的 AP使得 1. 每个 AP 覆盖其中心周围的 $3 \times 3$ 区域。 2. 任意两个 AP 的覆盖区域不得重叠。 3. 所有空地必须被覆盖。算法步骤1.预处理 - 记录所有空地的位置并分配唯一的 ID。 - 遍历每个空地位置 $(i, j)$将其作为 AP 的潜在中心。计算该 AP 覆盖的空地集合以及它在网格中占用的所有位置用于重叠检查。 - 建立映射关系每个空地 ID 对应哪些潜在的 AP 中心可以覆盖它。搜索逻辑 (DFS 回溯) - 使用深度优先搜索寻找最小的 AP 数量。 -启发式策略每次选择一个尚未被覆盖且“可选覆盖方案最少”的空地进行处理。这种“最少选择优先”的策略能极大地压缩搜索空间。 -冲突检查在放置一个 AP 时检查其 $3 \times 3$ 的覆盖范围是否与已放置的 AP 覆盖范围重叠。 -剪枝如果当前已使用的 AP 数量已经达到或超过已找到的最优解则停止当前分支的搜索。结果判断 - 如果搜索能覆盖所有空地记录最小值。 - 如果无法覆盖所有空地返回 -1。复杂度分析时间复杂度最坏情况下是指数级的但由于网格大小限制$50 \times 50$以及“不重叠”的强约束实际搜索空间会被大幅削减。启发式搜索在处理此类精确覆盖问题时通常表现良好。空间复杂度$O(M \times N)$用于存储网格状态、空地索引及递归