WIFI设备网络规划
华为OD机试真题 华为OD上机考试真题 4月19号 200分题型
华为OD机试真题目录点击查看: 华为OD机试真题题库目录|机考题库 + 算法考点详解
题目描述
WIFI网络中,专业的网络规划不仅可以提升业务体验,还可以减少部署成本。把办公区可以看作一个n* m的网格,部分网格包含墙壁(无法放置AP(WI一FI设备),部分为空地(可以放置AP)。每个AP覆盖范围是一个3*3的正方形(包括自身位置、上下左右、以及对角线区域),且AP和AP的覆盖区域不能重叠,防止相互干扰。
现在给定一个m x n(不超过50 * 50)的网络布局图(墙壁用字符#表示,空地用字符.表示),请设计一个算法,计算最少放置多少数量的AP来覆盖所有空地?如果不能按条件完成覆盖,请返回-1。
输入描述
第一行输入 m n
接下来m行输入每一行字符
输出描述
最少放置多少数量的AP来覆盖所有空地?如果不能按条件完成覆盖,请返回-1。