自然友好村庄

对于空地 $c$，令 $w(c)$ 表示其周围至多 $8$ 个格子中的住宅数量。

如果在空地 $c$ 上种一棵树，这棵树会分别计入每个相邻住宅周围的树木数量。因此，总和恰好增加 $w(c)$。不同空地的贡献彼此独立。

于是问题转化为：从若干个介于 $0$ 到 $8$ 的 $w(c)$ 中选择一些，使它们的和至少为 $K$，同时使选择的数量最少。对于固定的选择数量，要使总和最大，应优先选择最大的 $w(c)$。因此，按 $8,7$ 的顺序尽可能选择即可。

如果所有空地的 $w(c)$ 之和小于 $K$，则无法满足条件，应输出 -1。如果 $K=0$，则不需要种任何树，答案为 $0$。

每个空地的 $w(c)$ 都可以通过检查周围至多 $8$ 个格子求出。由于 $w(c)$ 只可能是 $0,1,\ldots,8$，只需统计每个值出现的次数，无需排序。每个测试用例的时间复杂度为 $$，总时间复杂度为 。存储网格需要 的内存。

Solution written by GPT5.6