目录题目思路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 中心”如果在某个空地放一个 AP它会覆盖以自己为中心的 3*3 区域。我们预处理出每个候选 AP 能覆盖哪些空地哪些候选 AP 之间会互相冲突覆盖区域重叠然后用回溯搜索每次挑一个“当前可选方案最少”的未覆盖空地尝试用能覆盖它的 AP 去覆盖同时删掉所有和它冲突的 AP在搜索过程中用两个剪枝加速当前 AP 数已经不优于最优答案直接返回一个 AP 最多覆盖 9 个空地据此估算理论最少还需要多少个 AP所以这个做法本质上是在所有合法摆放方案中搜索最优解并用剪枝减少无效分支。Codedef 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()JSfunction 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机试真题PythonJSJavaGo合集】【超值优惠】Py/JS/Java/Go合集【华为od机试真题Python】Python真题题库【华为od机试真题JavaScript】JavaScript真题题库【华为od机试真题JavaGo】JavaGo真题题库【华为od机试真题C】C真题题库【华为od机试真题C语言】C语言真题题库【华为od面试手撕代码题库】面试手撕代码题库【华为od机试面试交流群】【文章底部有二维码链接可扫码加交流群】华为OD机试:二本院校有机会吗?有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。