Consider determining whether to paint each square from the top row to bottom, and within the same row, from left to right. (Precisely speaking, let’s manage the state when we determine them in that order.)

When the painting of the squares before one square has been determined, the later squares are adjacent only to bottommost determined square in each column. Thus, the intermediate painting should be managed by the following states:

• The last square which you determined the color
• The color of bottommost determined square for each column
• Among black such squares, whether they belong to the same connected component

Note that, regarding whether an isolated connected component is completed or not, in the state where for each column, among the completed i.e. determined square, the bottommost one painted white but there is a connected component of black squares, if there is a later square that is originally painted black, the condition is satisfied; otherwise, the other squares have to be painted white, so the process on that state can immediately be terminated.

There are \(2^7\) ways to paint the bottommost column, and at most about \(4!\) states of the connected component because adjacent black squares in the same column always belong to the same connected component. Thus, for each “last square”, there are at most \(2^7\cdot 24\sim 3000\) states in total. (In fact, it is far less.)

Given a state and the new square to paint, the next state is uniquely determined, so the answer can be found by performing transition from each state, finding the minimum number of squares to paint to reach that state (or \(\infty\) etc. if impossible).

There are various ways of implementation. Since there are at most about \(3000\cdot (NM)\sim 2\times 10^6\) states in total, even using map will easily fit in the time limit.

Sample code in C++:

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

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

int n,m;
vector<vector<int> >state[M];
map<vector<int>,int>rev[M];
vector<int>tmp;

void make_state(int cut,int k,bool pre,int nxt){
	if(k==m){
		rev[cut][tmp]=state[cut].size();
		state[cut].push_back(tmp);
		return;
	}
	tmp.push_back(0);
	make_state(cut,k+1,false,nxt);
	tmp.pop_back();
	if(pre&&(k!=cut)){
		tmp.push_back(tmp[k]);
		make_state(cut,k+1,true,nxt);
		tmp.pop_back();
	}
	else {
		rep(i,nxt){
			tmp.push_back(i+1);
			make_state(cut,k+1,true,max(nxt,i+2));
			tmp.pop_back();
		}
	}
	return;
}

void renumbering(void){
	int sz=tmp.size();
	int c[10],nxt=1;
	rep(i,10)c[i]=0;
	rep(i,sz){
		if(tmp[i]>0){
			if(c[tmp[i]]==0)c[tmp[i]]=nxt,nxt++;
			tmp[i]=c[tmp[i]];
		}
	}
}

int judge(int k){
	int sz=tmp.size();
	int cnt=0,mx=0;
	rep(i,sz){
		mx=max(mx,tmp[i]);
		if(tmp[i]==tmp[k])cnt++;
	}
	if(cnt>1)return 0;
	if(mx>1)return -1;
	return 1;
}






int main() {

	vector<int>dp,dp2;
	int sz,x;
	int mx=0;
	int cnt=0;
    int ans=INF;

	cin>>n>>m;
	vector<string> s(n);
	rep(i,n){
		cin>>s[i];
		rep(j,m)if(s[i][j]=='#')mx=max(mx,i*m+j),cnt++;
	}

	tmp.push_back(0);
	rep(j,m)make_state(j,0,false,1);
	
	sz=state[0].size();
	rep(_,sz)dp.push_back(INF);
  
	dp[0]=0;
	rep(i,n){
		rep(j,m){
			sz=state[(j+1)%m].size();
			rep(_,sz)dp2.push_back(INF);
			sz=state[j].size();
			rep(idx,sz){
				tmp=state[j][idx];
				if((tmp[j]==0)&&(tmp[j+1]==0)){
					if(s[i][j]=='.')dp2[rev[(j+1)%m][tmp]]=min(dp2[rev[(j+1)%m][tmp]],dp[idx]);
					tmp[j+1]=9;
					renumbering();
					dp2[rev[(j+1)%m][tmp]]=min(dp2[rev[(j+1)%m][tmp]],dp[idx]+1);

				}
				else if((tmp[j]==0)&&(tmp[j+1]>0)){
					if(s[i][j]=='.'){
						x=judge(j+1);
						if(x==0){
							tmp[j+1]=0;
							renumbering();
							dp2[rev[(j+1)%m][tmp]]=min(dp2[rev[(j+1)%m][tmp]],dp[idx]);
						}
						if((x==1)&&((i*m+j)>=mx))ans=min(ans,dp[idx]);
					}
					tmp=state[j][idx];
					dp2[rev[(j+1)%m][tmp]]=min(dp2[rev[(j+1)%m][tmp]],dp[idx]+1);


				}
				else if((tmp[j]>0)&&(tmp[j+1]==0)){
					if(s[i][j]=='.')dp2[rev[(j+1)%m][tmp]]=min(dp2[rev[(j+1)%m][tmp]],dp[idx]);
					tmp[j+1]=tmp[j];
					dp2[rev[(j+1)%m][tmp]]=min(dp2[rev[(j+1)%m][tmp]],dp[idx]+1);
				}
				else if(tmp[j]==tmp[j+1]){
					if(s[i][j]=='.'){
						tmp[j+1]=0;
						dp2[rev[(j+1)%m][tmp]]=min(dp2[rev[(j+1)%m][tmp]],dp[idx]);
					}
					tmp=state[j][idx];
					dp2[rev[(j+1)%m][tmp]]=min(dp2[rev[(j+1)%m][tmp]],dp[idx]+1);
				}
				else{
					if(s[i][j]=='.'){
						x=judge(j+1);
						if(x==0){
							tmp[j+1]=0;
							renumbering();
							dp2[rev[(j+1)%m][tmp]]=min(dp2[rev[(j+1)%m][tmp]],dp[idx]);
						}
						if((x==1)&&((i*m+j)>=mx))ans=min(ans,dp[idx]);
					}
					tmp=state[j][idx];
					x=tmp[j+1];
					rep(ii,m+1)if(tmp[ii]==x)tmp[ii]=tmp[j];
					renumbering();
					dp2[rev[(j+1)%m][tmp]]=min(dp2[rev[(j+1)%m][tmp]],dp[idx]+1);
                }

			}
			dp=dp2;
			dp2.clear();
		}
	}

	sz=dp.size();
	rep(idx,sz){
		x=0;
		rep(j,m+1)x=max(x,state[0][idx][j]);
		if(x<=1){
			ans=min(ans,dp[idx]);
		}
	}

	cout<<(ans-cnt)<<endl;
	return 0;
}