题目的关键有两点:
因此,一旦某个 AP 被选中,它对应的整块覆盖区域中的所有格子都不能再被其他 AP 使用。与此同时,所有空地 . 都必须被至少一个 AP 覆盖。
这可以转化为一个带约束的搜索问题:
WIFI 网络中,专业的网络规划不仅可以提升业务体验,还可以减少部署成本。把办公区可以看作一个n∗m 的网格,部分网格包含墙壁(无法放置 AP (WI−FI 设备)),部分为空地(可以放置 AP)。每个AP覆盖范围是一个 3∗3的正方形(包括自身位置、上下左右、以及对角线区域),且 AP 和 AP的覆盖区域不能重叠,防止相互干扰。
现在给定一个 m×n(不超过 50∗50) 的网络布局图(墙壁用字符 # 表示,空地用字符 . 表示),请设计一个算法,计算最少放置多少数量的AP来覆盖所有空地?如果不能按条件完成覆盖,请返回 −1。
输入
[[.,.,.,#,.,.,.],[.,.,.,#,.,.,.],[.,.,.,#,.,.,.],[.,.,.,#,.,.,.],[.,.,.,#,.,.,.],[.,.,.,#,.,.,.],[.,.,.,#,.,.,.]]
输出
6
图示为:
图示为:(A代表AP设备)

输入
[[.,.,#,.,.],[.,.,#,.,.],[.,.,#,.,.],[.,.,#,.,.],[.,.,#,.,.]]
输出
4
图示为:
图示为:(A代表AP设备)

输入
[[.],[.],[.],[.],[.]]
输出
2
图示为:
图示为:(A代表AP设备)

输入
[[.,#,.,#],[#,.,#,.],[.,#,.,#],[#,.,#,.]]
输出
-1
图示为:
无法部署,所有方案都存在有重叠的范围
输入可以传入[[]]