/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 425 点
問題文
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) が黒く塗られていることを表します。
高橋君はいくつか（0 個でも良い）の黒く塗られたマスを白に塗り替えることで、 マス目が黒く塗られたマスのみからなる 2\times 2 の部分を持たないようにしたいです。 より厳密には、次の条件をみたすようにしたいです。
1\leq i\leq H-1, 1\leq j\leq W-1 をみたす任意の整数の組 (i,j) について、 マス (i,j), マス (i,j+1), マス (i+1,j), マス (i+1,j+1) のうち 少なくとも 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
1 つめのテストケースについて、マス目の最初の状態は、下図左のようになっています。
このマス目の黒いマスのうち、例えば下図右の番号が入っている 3 つのマスを白く塗り替えることで、条件をみたすようにできます。
最初の状態から 2 個以下のマスを白く塗ることで条件をみたすようにすることはできないため、3 を 1 行目に出力します。
2 つめのテストケースについて、マス目は最初から条件をみたしています。
よって、0 を 2 行目に出力します。
Score : 425 points
Problem Statement
There is a grid with H rows and W columns, and each cell is painted white or black.
Let us denote the cell at the i-th row from the top (1\leq i\leq H) and the j-th column from the left (1\leq j\leq W) by cell (i,j).
The state of the grid is given by H strings S_1,S_2,\ldots,S_H of length W consisting of . and #.
If the j-th character of S_i is ., then cell (i,j) is white; if it is #, then cell (i,j) is black.
By repainting some black cells (possibly zero) to white, Takahashi wants to make the grid have no 2\times 2 subgrid consisting only of black cells. More precisely, he wants to satisfy the following condition.
For any integer pair (i,j) with 1\leq i\leq H-1 and 1\leq j\leq W-1, among cells (i,j), (i,j+1), (i+1,j), and (i+1,j+1), at least one is white.
Find the minimum number of cells that need to be repainted white in order for Takahashi to achieve his goal.
You are given T test cases; answer each of them.
Constraints
- 1\leq T\leq 100
- 2\leq H\leq 7
- 2\leq W\leq 7
- Each S_i is a string of length W consisting of
.and#. - T,H,W are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
\mathrm{case}_i represents the i-th test case. Each test case is given in the following format:
H W S_1 S_2 \vdots S_H
Output
Output T lines. On the i-th line (1\leq i\leq T), output the answer for the i-th test case.
Sample Input 1
2 5 5 ####. ##.## ##### .#### ##.#. 2 2 .. ..
Sample Output 1
3 0
For the first test case, the initial state of the grid is as shown in the left figure below. By repainting, for example, the three cells with numbers in the right figure below from black to white, the condition can be satisfied.
It is impossible to satisfy the condition by repainting two or fewer cells from the initial state, so output 3 on the 1-st line.
For the second test case, the grid already satisfies the condition from the beginning. Thus, output 0 on the 2-nd line.