Nature-Friendly Village

For an empty lot $c$, let $w(c)$ be the number of houses among its at most $8$ neighboring cells.

If one tree is planted on $c$, that tree is counted once for every adjacent house. Therefore it increases the required total by exactly $w(c)$. Contributions from different empty lots are independent.

The task is thus to choose some values $w(c)$, each between $0$ and $8$, so that their sum is at least $K$ while minimizing how many values are chosen. For any fixed number of chosen lots, the largest possible sum is obtained by taking the largest values first. Hence it is optimal to take lots in the order $8,7,\ldots,1$.

If the sum of $w(c)$ over all empty lots is smaller than $K$, the requirement is impossible and the answer is -1. If $K=0$, the answer is $0$.

Each $w(c)$ is found by checking at most $8$ neighboring cells. Since only the values $0,1,\ldots,8$ are possible, it is enough to count the frequency of each value; sorting is unnecessary. The time complexity is $O(RC)$ per test case and overall. The grid uses memory.

Solution written by GPT5.6