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 翻译