华为OD机试真题 新系统 2026-04-19 PythonJS 实现【WIFI设备网络规划】

目录

题目

思路

Code

题目

WIFI 网络中，专业的网络规划不仅可以提升业务体验，还可以减少部署成本。把办公区可以看作一个 n * m 的网格，部分网格包含墙壁（无法放置 AP），部分为空地（可以放置 AP）。每个 AP 覆盖范围是一个 3*3 的正方形（包括自身位置、上下左右，以及对角线区域），且 AP 和 AP 的覆盖区域不能重叠，防止相互干扰。

现在给定一个 m x n（不超过 50 * 50）的网格布局图（墙壁用字符表示，空地用字符表示），请设计一个算法，计算最少放置多少数量的 AP 来覆盖所有空地？如果不能按条件完成覆盖，请返回 -1。

输入描述
第一行输入 m n

接下来 m 行输入每一行字符串

输出描述
最少放置多少数量的 AP 来覆盖所有空地？如果不能按条件完成覆盖，请返回 -1。

示例1

输入

3 3
#.#
#.#
#.#

输出

1

示例2

输入

4 3
#.#
#.#
#.#
#.#

输出

2

思路

这题可以把每个空地都看成一个“候选 AP 中心”：

1. 如果在某个空地放一个 AP，它会覆盖以自己为中心的 3*3 区域。
2. 我们预处理出：
   • 每个候选 AP 能覆盖哪些空地
   • 哪些候选 AP 之间会互相冲突（覆盖区域重叠）
3. 然后用回溯搜索：
   • 每次挑一个“当前可选方案最少”的未覆盖空地
   • 尝试用能覆盖它的 AP 去覆盖
   • 同时删掉所有和它冲突的 AP
4. 在搜索过程中用两个剪枝加速：
   • 当前 AP 数已经不优于最优答案，直接返回
   • 一个 AP 最多覆盖 9 个空地，据此估算理论最少还需要多少个 AP

所以，这个做法本质上是在所有合法摆放方案中搜索最优解，并用剪枝减少无效分支。

Code

def solve(): # 读取网格大小 m, n = map(int, input().split()) grid = [input().strip() for _ in range(m)] # 收集所有空地位置，题目示例中 '.' 表示空地，'#' 表示墙 empties = [] empty_id = {} for i in range(m): for j in range(n): if grid[i][j] == '.': empty_id[(i, j)] = len(empties) empties.append((i, j)) # 如果没有空地，不需要放置 AP if not empties: print(0) return e_cnt = len(empties) # --------------------------------------------------------- # 1. 枚举所有候选 AP # AP 只能放在空地上，所以每个空地都可以作为候选中心 # cover_masks[k] 表示第 k 个候选 AP 能覆盖哪些空地 # --------------------------------------------------------- centers = empties[:] c_cnt = len(centers) cover_masks = [0] * c_cnt for idx, (x, y) in enumerate(centers): mask = 0 # AP 覆盖中心周围 3*3 for dx in (-1, 0, 1): for dy in (-1, 0, 1): nx, ny = x + dx, y + dy if (nx, ny) in empty_id: mask |= 1 << empty_id[(nx, ny)] cover_masks[idx] = mask # --------------------------------------------------------- # 2. 预处理每个空地可以被哪些候选 AP 覆盖 # cell_to_centers[e] 是一个 bitmask，表示哪些候选中心能覆盖空地 e # --------------------------------------------------------- cell_to_centers = [0] * e_cnt for c in range(c_cnt): mask = cover_masks[c] tmp = mask while tmp: lowbit = tmp & -tmp e = lowbit.bit_length() - 1 cell_to_centers[e] |= 1 << c tmp ^= lowbit # --------------------------------------------------------- # 3. 预处理候选 AP 之间的冲突关系 # 如果两个 AP 的 3*3 覆盖区域有重叠，就不能同时选 # # 两个中心分别为 (x1, y1), (x2, y2) # 当且仅当 abs(x1-x2) <= 2 且 abs(y1-y2) <= 2 时， # 两个 3*3 正方形会重叠 # --------------------------------------------------------- conflict_masks = [0] * c_cnt for i in range(c_cnt): x1, y1 = centers[i] mask = 1 << i # 自己也算冲突，方便后面直接删除 for j in range(c_cnt): if i == j: continue x2, y2 = centers[j] if abs(x1 - x2) <= 2 and abs(y1 - y2) <= 2: mask |= 1 << j conflict_masks[i] = mask # 当前所有空地都还没被覆盖 full_uncovered = (1 << e_cnt) - 1 # 当前所有候选 AP 都可用 full_available = (1 << c_cnt) - 1 # 记录最优答案 best = [float('inf')] # --------------------------------------------------------- # 4. 回溯搜索 # # uncovered_mask：哪些空地还没被覆盖 # available_mask：哪些候选 AP 还能选 # used：当前已经用了多少个 AP # --------------------------------------------------------- def dfs(uncovered_mask, available_mask, used): # 剪枝：当前方案已经不优于最优答案 if used >= best[0]: return # 所有空地都覆盖完成，更新答案 if uncovered_mask == 0: best[0] = used return # 剪枝：理论下界 # 一个 AP 最多覆盖 9 个空地，因此至少还需要 ceil(剩余空地数 / 9) 个 AP remain_cells = uncovered_mask.bit_count() lower_bound = (remain_cells + 8) // 9 if used + lower_bound >= best[0]: return # ----------------------------------------------------- # 选一个“候选最少”的未覆盖空地优先处理 # 这样能更快触发剪枝 # ----------------------------------------------------- pick_cell = -1 pick_candidates = 0 min_choice = float('inf') tmp = uncovered_mask while tmp: lowbit = tmp & -tmp e = lowbit.bit_length() - 1 # 当前还能覆盖该空地的候选 AP candidates = cell_to_centers[e] & available_mask cnt = candidates.bit_count() # 如果一个未覆盖空地已经没有任何可选 AP，则当前分支无解 if cnt == 0: return if cnt < min_choice: min_choice = cnt pick_cell = e pick_candidates = candidates # 已经是最小可能值，没必要继续找 if cnt == 1: break tmp ^= lowbit # ----------------------------------------------------- # 枚举所有可以覆盖 pick_cell 的 AP # ----------------------------------------------------- candidates = pick_candidates while candidates: lowbit = candidates & -candidates c = lowbit.bit_length() - 1 # 选择第 c 个 AP 后： # 1. 它覆盖到的空地从 uncovered 中删掉 # 2. 与它冲突的 AP 全部从 available 中删掉 new_uncovered = uncovered_mask & ~cover_masks[c] new_available = available_mask & ~conflict_masks[c] dfs(new_uncovered, new_available, used + 1) candidates ^= lowbit dfs(full_uncovered, full_available, 0) print(-1 if best[0] == float('inf') else best[0]) if __name__ == "__main__": solve()

JS

function solve() { const fs = require("fs"); const input = fs.readFileSync(0, "utf8").trim().split("\n"); // 读取网格大小 const [m, n] = input[0].trim().split(/\s+/).map(Number); const grid = []; for (let i = 1; i <= m; i++) { grid.push(input[i].trim()); } // 收集所有空地位置，题目示例中 '.' 表示空地，'#' 表示墙 const empties = []; const emptyId = new Map(); for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (grid[i][j] === ".") { emptyId.set(`${i},${j}`, empties.length); empties.push([i, j]); } } } // 如果没有空地，不需要放置 AP if (empties.length === 0) { console.log(0); return; } const eCnt = empties.length; // 1. 枚举所有候选 AP // AP 只能放在空地上，所以每个空地都可以作为候选中心 // coverList[k] 表示第 k 个候选 AP 能覆盖哪些空地 const centers = empties.slice(); const cCnt = centers.length; const coverList = Array.from({ length: cCnt }, () => []); for (let idx = 0; idx < cCnt; idx++) { const [x, y] = centers[idx]; // AP 覆盖中心周围 3*3 for (let dx = -1; dx <= 1; dx++) { for (let dy = -1; dy <= 1; dy++) { const nx = x + dx; const ny = y + dy; const key = `${nx},${ny}`; if (emptyId.has(key)) { coverList[idx].push(emptyId.get(key)); } } } } // 2. 预处理每个空地可以被哪些候选 AP 覆盖 // cellToCenters[e] 表示哪些候选中心能覆盖空地 e const cellToCenters = Array.from({ length: eCnt }, () => []); for (let c = 0; c < cCnt; c++) { for (const e of coverList[c]) { cellToCenters[e].push(c); } } // 3. 预处理候选 AP 之间的冲突关系 // 如果两个 AP 的 3*3 覆盖区域有重叠，就不能同时选 // // 两个中心分别为 (x1, y1), (x2, y2) // 当且仅当 abs(x1-x2) <= 2 且 abs(y1-y2) <= 2 时， // 两个 3*3 正方形会重叠 const conflictList = Array.from({ length: cCnt }, () => []); for (let i = 0; i < cCnt; i++) { const [x1, y1] = centers[i]; conflictList[i].push(i); for (let j = 0; j < cCnt; j++) { if (i === j) { continue; } const [x2, y2] = centers[j]; if (Math.abs(x1 - x2) <= 2 && Math.abs(y1 - y2) <= 2) { conflictList[i].push(j); } } } // 记录最优答案 let best = Infinity; // 4. 回溯搜索 // // uncovered：哪些空地还没被覆盖 // available：哪些候选 AP 还能选 // uncoveredCount：当前未覆盖空地数 // used：当前已经用了多少个 AP function dfs(uncovered, available, uncoveredCount, used) { // 剪枝：当前方案已经不优于最优答案 if (used >= best) { return; } // 所有空地都覆盖完成，更新答案 if (uncoveredCount === 0) { best = used; return; } // 剪枝：理论下界 // 一个 AP 最多覆盖 9 个空地，因此至少还需要 ceil(剩余空地数 / 9) 个 AP const lowerBound = Math.floor((uncoveredCount + 8) / 9); if (used + lowerBound >= best) { return; } // 选一个“候选最少”的未覆盖空地优先处理 let pickCell = -1; let pickCandidates = []; let minChoice = Infinity; for (let e = 0; e < uncovered.length; e++) { if (!uncovered[e]) { continue; } const candidates = []; for (const c of cellToCenters[e]) { if (available[c]) { candidates.push(c); } } const cnt = candidates.length; // 如果一个未覆盖空地已经没有任何可选 AP，则当前分支无解 if (cnt === 0) { return; } if (cnt < minChoice) { minChoice = cnt; pickCell = e; pickCandidates = candidates; if (cnt === 1) { break; } } } // 枚举所有可以覆盖 pickCell 的 AP for (const c of pickCandidates) { // 选择第 c 个 AP 后： // 1. 它覆盖到的空地从 uncovered 中删掉 // 2. 与它冲突的 AP 全部从 available 中删掉 const newUncovered = uncovered.slice(); let newUncoveredCount = uncoveredCount; for (const e of coverList[c]) { if (newUncovered[e]) { newUncovered[e] = false; newUncoveredCount--; } } const newAvailable = available.slice(); for (const x of conflictList[c]) { newAvailable[x] = false; } dfs(newUncovered, newAvailable, newUncoveredCount, used + 1); } } const fullUncovered = new Array(eCnt).fill(true); const fullAvailable = new Array(cCnt).fill(true); dfs(fullUncovered, fullAvailable, eCnt, 0); console.log(best === Infinity ? -1 : best); } solve();

【华为od机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集

【华为od机试真题Python】：Python真题题库

【华为od机试真题JavaScript】：JavaScript真题题库

【华为od机试真题Java&Go】：Java&Go真题题库

【华为od机试真题C++】：C++真题题库

【华为od机试真题C语言】：C语言真题题库

【华为od面试手撕代码题库】：面试手撕代码题库

【华为od机试面试交流群】【文章底部有二维码链接，可扫码加交流群】

华为OD机试:二本院校有机会吗?
有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。