解题思路

题目的关键有两点：

1. 一个 AP 会覆盖自己所在位置周围的 3 × 3 区域。
2. 任意两个 AP 的覆盖区域不能重叠。

因此，一旦某个 AP 被选中，它对应的整块覆盖区域中的所有格子都不能再被其他 AP 使用。与此同时，所有空地 . 都必须被至少一个 AP 覆盖。

这可以转化为一个带约束的搜索问题：

题目内容

$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

说明

图示为： 无法部署，所有方案都存在有重叠的范围 输入可以传入[[]]