#714 自然友好村庄

题面

题面语言

有一个大小为 $R \times C$ 的村庄。村庄中的每个格子要么是住宅，要么是空地。

村长希望在空地上种树，使村庄更加自然友好。对于一栋住宅，与它共边或共顶点的至多 $8$ 个格子称为这栋住宅的 周围格子。

种树后必须满足以下两个条件。

种植一棵树需要很高的成本。请计算为了满足条件至少需要种植多少棵树。

输入按照以下格式从标准输入给出。

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

对于每个测试用例，输出一行，为满足条件所需种植的最少树木数量。如果无法通过种树满足条件，输出 -1。

#	分数	数据范围
1	30	$R,C \le 2$ . 모든 테스트 케이스에 대한 $R \times C$ 의 합은 $3\,000$ 을 넘지 않는다.
2

样例输入

3
1 1 0
.
2 3 2
.##
...
2 2 1
..
..

样例输出

0
1
-1

在第二个测试用例中，如果在第二行中间的空地种一棵树，这棵树与两栋住宅都相邻，因此总和变为 $2$ 。

第三个测试用例中没有住宅，所以无论在哪里种树，总和都保持为 $0$ 。