分数: 425 点
问题陈述
有一个网格 H 行和 W 列,每个单元格都涂成白色或黑色。
让我们表示位于 i从顶部算起的第行 (1\leq i\leq H) 和 j左起第 列 (1\leq j\leq W) 按单元格 (i,j).
网格状态由下式给出 H 字符串 S_1,S_2,\ldots,S_H 长度 W 组成 . 和 #.
如果 j- 第一个字符 S_i is .,然后是单元格 (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 测试用例;回答他们每个人。
约束
- 1\leq T\leq 100
- 2\leq H\leq 7
- 2\leq W\leq 7
- 每个 S_i 是一个长度为的字符串 W 组成
.和#. - T,H,W 是整数。
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
\mathrm{case}_i 代表 i- 第一个测试用例。 每个测试用例均按以下格式给出:
H W S_1 S_2 \vdots S_H
输出
输出 T 行。 上 i第行 (1\leq i\leq T),输出答案 i- 第一个测试用例。
示例输入 1
2 5 5 ####. ##.## ##### .#### ##.#. 2 2 .. ..
示例输出 1
3 0
对于第一个测试用例,网格的初始状态如下左图所示。 例如,将下右图中有数字的三个单元格从黑色重新绘制为白色,即可满足条件。

从初始状态重新绘制两个或更少的单元格不可能满足条件,因此输出 3 上 1-st 行。
对于第二个测试用例,网格从一开始就已经满足条件。 因此,输出 0 上 2-nd 行。