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