AT_abc424_d [ABC424D] 2x2 Erasing 2

给定一个由 $H$ 行 $W$ 列组成的网格，每个格子要么是白色，要么是黑色。 我们用第 $i$ 行（自上而下，$1\leq i\leq H$）、第 $j$ 列（自左而右，$1\leq j\leq W$）的格子，记作格子 $(i,j)$。 网格的状态由 $H$ 个长度为 $W$ 的字符串 $S_1,S_2,\ldots,S_H$ 给出，每个字符串只包含字符 `.` 和 `#`。 如果 $S_i$ 的第 $j$ 个字符是 `.`，则格子 $(i,j)$ 是白色；如果是 `#`，则格子 $(i,j)$ 是黑色。 高桥希望通过将一些黑色格子（可以为零个）变为白色，使整个网格中不存在仅由黑色格子组成的 $2\times 2$ 子网格。更具体地说，要满足下面的条件： > 对于任意整数对 $(i,j)$，其中 $1\leq i\leq H-1$ 且 $1\leq j\leq W-1$，在格子 $(i,j)$、$(i,j+1)$、$(i+1,j)$ 和 $(i+1,j+1)$ 中，**至少有一个是白色的**。 请计算至少需要将多少个黑色格子变为白色，才能使高桥达成目标。 输入包含 $T$ 组测试用例。请分别输出每组测试用例的答案。

输入按如下格式给出： > $T$ > $\mathrm{case}_1$ > $\mathrm{case}_2$ > $\vdots$ > $\mathrm{case}_T$ 每组测试用例的格式为： > $H$ $W$ > $S_1$ > $S_2$ > $\vdots$ > $S_H$

输出 $T$ 行，第 $i$ 行（$1\leq i\leq T$）输出第 $i$ 组测试用例的答案。

### 样例解释 1 对于第一个测试用例，初始网格如下图左所示。 例如，将右图中标有数字的三个黑色格子变为白色即可满足条件。  无法通过涂白两格或更少格子就满足题意，所以第一组输出应为 $3$。 对于第二组测试用例，初始网格已经满足条件，因此输出 $0$。 ### 数据范围 - $1\leq T\leq 100$ - $2\leq H\leq 7$ - $2\leq W\leq 7$ - 每个 $S_i$ 是长度为 $W$，由 `.` 和 `#` 组成的字符串。 - $T,H,W$ 均为整数。 由 ChatGPT 5 翻译