社区常称:WIFI设备网络规划
通过率 28% · 提交 172 · 通过 48
小慕正在负责一个办公区的WiFi网络规划项目。好的网络规划不仅能提升员工的上网体验,还能降低部署成本。他将办公区抽象成一个 n×m 的网格,网格中的某些格子是墙壁(用字符 # 表示),无法放置无线接入点();其余格子是空地(用字符 . 表示),可以放置AP。 每个AP的覆盖范围是一个 3×3 的正方形区域,包括它自身所在格子以及上下左右和对角线共9个格子。为了保证信号不互相干扰,任意两个AP的。 现在,小慕拿到了一张 n×m(n和m均不超过50)的办公区布局图,请你帮他设计一个算法,计算出最少需要放置多少个AP,才能覆盖所有空地。如果无论如何都无法满足条件完成覆盖,则返回 -1。
这类题属于算法机考高频题型中「200分 / 回溯」方向的高频题型,通常考察对「200分 / 回溯」的建模能力与边界条件处理。掌握本题的解题思路后,可举一反三应对同类真题方向,稳步提升机考通过率。
提示:带虚线的词点一下有通俗解释。
大小为n*m的二维字符串数组grid
最少放置多少数量的AP来覆盖所有空地 如果不能按条件完成覆盖,请返回-1。
示例 1
输入示例
3 3 #.# #.# #.#
输出示例
1
放置一个 AP 在 (1, 1) 位置即可覆盖周围 3x3 区域。
示例 2
输入示例
4 3 #.# #.# #.# #.#
输出示例
2
时间限制 5000 ms · 内存限制 128 MB
本平台为独立第三方培训机构,与华为技术有限公司无任何关联;课程的服务内容与权益以购买协议为准,学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述,相关商标归各自权利人所有。
登录后可查看你在本题的历史提交,以及每次的各用例通过情况。
© 2026 广州慕课网络科技有限公司 · 吴师兄学算法官网 版权所有