#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 番目のテストケースでは、2 行目の中央の空き地に木を一本植えると、その木は二つの家の両方に隣接するため、総和は $2$ になる。

3 番目のテストケースには家がないため、どこに木を植えても総和は $0$ のままである。