Submission #40342667

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN=110,MAXM=4510,INF=1e9;
void tomin(int& x,int y){x=min(x,y);}
void tomax(int& x,int y){x=max(x,y);}
int n,m;
char s[MAXN][MAXN];

int r[MAXN],cnt,lim[MAXN],pcnt[1<<7];
int trans[MAXM][1<<7];

struct Node{
	int a[10];
	bool operator<(const Node& n2)const{
		rep(i,1,m)if(a[i] != n2.a[i])return a[i] < n2.a[i];
		return 0;
	}
}res[MAXM];
map<Node,int>conv; 

int dp[MAXN][MAXM],ans=INF;

void dfs(int cur,int mx){
	if(cur > m){
		Node node;
		rep(i,1,m)node.a[i]=r[i];
		conv[node]=++cnt;
		res[cnt]=node;

		return;
	}
	r[cur]=-1;
	dfs(cur+1,mx);

	r[cur]=mx+1;
	dfs(cur+1,mx+1);

	rep(i,1,mx)r[cur]=i,dfs(cur+1,mx);
}

struct DSU{
	int fa[MAXN];
	void init(int n){iota(fa+1,fa+1+n,1);}
	int find(int x){return (fa[x]==x)?(x):(fa[x]=find(fa[x]));}
	void merge(int x,int y){fa[find(x)]=find(y);}
}dsu;	

void calc(int x,int mask){
	dsu.init(2*m);
	rep(i,1,m)rep(j,i+1,m)if(res[x].a[i] == res[x].a[j] && res[x].a[i] != -1)dsu.merge(i,j);
	rep(i,1,m-1){
		if((mask>>i&1) && (mask>>(i-1)&1))dsu.merge(m+i,m+i+1);
	}
	rep(i,1,m){
		if((mask>>(i-1)&1) && res[x].a[i] != -1)dsu.merge(i,m+i);
	}

	int mx=0;
	rep(i,1,m){
		if((mask>>(i-1)&1)){
			int flag=0;
			rep(j,1,i-1)if(dsu.find(m+i) == dsu.find(m+j)){flag=1;r[i]=r[j];break;}
			if(!flag)r[i]=++mx;
		}else r[i]=-1;	
	}
	int flag=1;
	rep(i,1,m)if(res[x].a[i] != -1){
		int tmpflag=0;
		rep(j,1,m)tmpflag |= (dsu.find(i) == dsu.find(m+j) );
		flag &= tmpflag;
	}

	if(!flag)return;

	Node node;
	rep(i,1,m)node.a[i]=r[i];

	int idx=conv[node];

	trans[x][mask]=idx;
}

int check(int x){
	rep(i,1,m)if(res[x].a[i] > 1)return 0;

	return 1;
}

int main(){

	cin>>n>>m;
	rep(i,0,(1<<m)-1)pcnt[i]=__builtin_popcount(i);

	rep(i,1,n)cin>>(s[i]+1);
	rep(i,1,n)rep(j,1,m)if(s[i][j] == '#')lim[i] |= (1<<(j-1));

	int ed=0;
	per(i,n,1)if(lim[i]){ed=i;break;}

	dfs(1,0);

	rep(i,1,cnt)rep(j,0,(1<<m)-1)calc(i,j);
	
	rep(i,0,n)rep(j,1,cnt)dp[i][j]=INF;

	dp[0][1]=0;

	rep(i,0,ed-1)rep(j,1,cnt)if(dp[i][j] < INF){
		int tmp=dp[i][j];

		rep(mask,0,(1<<m)-1)if((mask & lim[i+1]) == lim[i+1]){
			tomin(dp[i+1][trans[j][mask]],tmp + pcnt[mask] - pcnt[lim[i+1]]);
		}
	}

	rep(j,1,cnt)if(check(j)){tomin(ans,dp[ed][j]);}
	cout<<ans<<endl;

    return 0;
}

Submission Info

Judge Result