この問題にはいくつかの解法が考えられます。

• bitDP を用いて、マス目を上から順に、各行の状態を管理しつつ走査する解法
• bitDP を用いて、マス目をマス番号 \((i,j)\) の辞書順に、最後の \((W+1)\) マスの状態を管理しつつ走査する解法
• 問題の制約下で答えが高々 \(9\) であること\(^*\) を用いて、枝刈りを含む全探索を行う解法

\(^*\): \(1\leq i\leq H\), \(1\leq j\leq W\) をみたす偶数の組 \((i,j)\) について、マス \((i,j)\) がすべて白く塗られているならば、他のマスの状態によらず、条件をみたします。問題の制約 \(H,W\leq 7\) の下においてそのようなマスは高々 \(9\) 個であり、それらのマスがすべて白く塗られているように塗り替える必要のあるマスの個数も高々 \(9\) 個となります。よって、\(9\) 個以下のマスを白く塗り替えて条件をみたすようにする方法が存在し、塗り替える必要のあるマスの個数の最小値は高々 \(9\) であることがわかります。

ここでは、\(1\) つめの解法のみを紹介します。
以下、行 \(i\) \((1\leq i\leq H)\) の状態を、\(x_{i,1}+2\cdot x_{i,2}+2^2\cdot x_{i,3}+\cdots+2^{W-1}\cdot x_{i,W}\) で定義します。ここで、\(x_{i,j}\) \((1\leq j\leq W)\) は、マス \((i,j)\) が白く塗られているとき \(x_{i,j}=0\)、黒く塗られているとき \(x_{i,j}=1\) と定義します。このとき、任意の行の状態は \(0\) 以上 \(2^W\) 未満の整数のいずれかで表されます。

さて、\(dp[i][j]\) \((1\leq i\leq H,0\leq j\leq 2^W-1)\) を、次の \(2\) つの条件をともにみたすようにするために白く塗り替える必要のある黒マスの個数の最小値（そのように塗り替える方法が存在しない場合は \(+\infty\)）で定義します。

• 塗り替えた後のマス目の \(1\) 行目から \(i\) 行目までを考えた時に、黒く塗られたマスのみからなる \(2\times 2\) の部分が存在しない。
• \(i\) 行目の状態が \(j\) である。

まず、\(dp[1][j]\) について、\(2\) つめの条件はつねにみたされていることから、\(1\) つめの条件についてのみ考えれば良いです。マス目の \(1\) 行目の最初の状態から、いくつかの黒く塗られたマスを白く塗りかえることで、状態 \(j\) にできるならば、\(dp[1][j]\) の値はその塗り替える必要のある個数であり、そうでないならば \(+\infty\) です。

つぎに、任意の \(0\leq j'<2^W\) について \(dp[i][j']\) が求まっているとき、\(dp[i+1][j]\) を求める方法について考えます。まず、\((i+1)\) 行目の最初の状態から、いくつかの黒く塗られたマスを白く塗りかえることで、状態 \(j\) にできないならば、\(dp[i+1][j]=+\infty\) です。そうでないとき、\(i\) 行目の状態が \(j'\), \((i+1)\) 行目の状態が \(j\) のとき、マス目の \(i,(i+1)\) 行目のみを考えたときに 黒く塗られたマスのみからなる \(2\times 2\) の部分が存在しないような \(j'\) の集合を \(S\) とします。このとき、\((i+1)\) 行目を状態 \(j\) にするために塗り替える必要のある個数を \(x\) として、\(\displaystyle dp[i+1][j]=\min_{j'\in S}dp[i][j']+x\) が成り立ちます。
ここで、\(dp[i][j']\) および \(S\) の定義より、 \(dp[i][j']+x\) 回で \(1\) 行目から \((i+1)\) 行目には黒く塗られたマスのみからなる \(2\times 2\) の部分が存在せず、かつ \(i\) 行目の状態が \(j'\) かつ \((i+1)\) 行目の状態が \(j\) であるようにすることができ、かつそのための最小の塗り替え回数となっていることに注意します。 \(i\) 行目の状態としてあり得るものすべてにわたって、その値の最小値をとることで \(dp[i+1][j]\) の定義に従った値が求まっていることになります。

答えは \(\displaystyle\min_{0\leq j<2^W} dp[H][j]\) で求めることができます。

さて、計算量は \(dp\) 配列の要素数が \(H\cdot 2^W\), 更新にそれぞれ最大 \(2^W\) 個の最小値を取る必要があることから、テストケースあたり\(O(H\cdot 4^W)\) となります。よって、全体で \(O(TH\cdot 4^W)\) となりますが、\(TH\cdot 4^W\leq 100\cdot 7\cdot2^{14}\sim 10^7\) より、今回の制約下で十分高速です。
よって、この問題を解くことができました。

なお、\(2\) つめの解法では、 \(O(THW\cdot 2^W)\) の時間計算量でより高速にこの問題を解くことができます。

c++ による実装例:

#include <bits/stdc++.h>
using namespace std;

#define INF (int)1e+9
#define rep(i, n) for(int i = 0; i < n; ++i)

int main(void){
	int t;
	cin>>t;
	rep(_,t){
		int h,w,k;
		cin>>h>>w;
		k=1<<w;

		vector<string>s(h);
		rep(i,h)cin>>s[i];

		vector<vector<bool> >allow(k,vector<bool>(k,true));
		rep(i,k){
			rep(j,k){
				rep(ii,w-1){
					if((((i>>ii)&3)==3)&&(((j>>ii)&3)==3)){
						allow[i][j]=false;
						break;
					}
				}
			}
		}

		vector<int>dp(k,INF);
		dp[0]=0;
		rep(i,h){
			int state=0;
			rep(j,w)if(s[i][j]=='#')state+=(1<<j);
			vector<int>dp2(k,INF);
			rep(j,k){
				if((j|state)==state){
					rep(jj,k){
						if(allow[jj][j])dp2[j]=min(dp2[j],dp[jj]+std::popcount(((unsigned int)(j^state))));
					}
				}
			}
			dp=dp2;
		}

		int ans=INF;
		rep(i,k)ans=min(ans,dp[i]);
		cout<<ans<<endl;
	}
	
	return 0;
}