小慕正在负责一个办公区的WiFi网络规划项目。好的网络规划不仅能提升员工的上网体验，还能降低部署成本。他将办公区抽象成一个 n×m 的网格，网格中的某些格子是墙壁（用字符 # 表示），无法放置无线接入点（）；其余格子是空地（用字符 . 表示），可以放置AP。 每个AP的覆盖范围是一个 3×3 的正方形区域，包括它自身所在格子以及上下左右和对角线共9个格子。为了保证信号不互相干扰，任意两个AP的。 现在，小慕拿到了一张 n×m（n和m均不超过50）的办公区布局图，请你帮他设计一个算法，计算出最少需要放置多少个AP，才能覆盖所有空地。如果无论如何都无法满足条件完成覆盖，则返回 -1。
提示：带虚线的词点一下有通俗解释。
输入描述
大小为n*m的二维字符串数组grid
输出描述
最少放置多少数量的AP来覆盖所有空地 如果不能按条件完成覆盖，请返回-1。
示例
示例 1
输入
3 3 #.# #.# #.#
输出
1
说明：放置一个 AP 在 (1, 1) 位置即可覆盖周围 3x3 区域。
示例 2
输入
4 3 #.# #.# #.# #.#
输出
2
时间限制 5000 ms · 内存限制 128 MB