Sgu/132

典型的状态压缩 用f[i][j][k]表示前i-1行已符合要求，第i-1行和第i行状态为j和k时所需最小数目

//by hza
#include<cstdio>
#include<cstring>
 
const int INF=100000;
const int maxN=80;
const int maxM=8;
const int MAX=128;
char graph[maxN][maxM];
int map[maxN];
int f[4][MAX][MAX];
int n,m;
 
inline int made(int a,int i){return a|1<<i;}
inline int get(int a,int i){return (a>>i)&1;}
void print(int now)
{
	int i;
	for(i=0;i<m;++i)
		printf("%d",get(now,i));
	printf("\n");
}
 
void init()
{
	int i,j;
	scanf("%d %d\n",&n,&m);
	for(i=1;i<=n;++i)
		scanf("%s",graph[i]);
	for(i=1;i<=n;++i)
		for(j=0;j<m;++j)
		{
			map[i]<<=1;
			if(graph[i][j]=='*')
				map[i]+=1;
		}
}
 
void dfs(int i,int j,int od0,int od1,int f0,int f1,int f2,int sum)
{
	if(j>0&&!get(f0,j-1)&&!get(f1,j-1))return;
	if(j>1&&!get(f1,j-1)&&!get(f1,j-2))return;
	if(j>=m)
	{
		if(f[i&1][od0][od1]+sum<f[(i+1)&1][f1][f2])
			f[(i+1)&1][f1][f2]=f[i&1][od0][od1]+sum;
		return;
	}
	if(!get(f1,j)&&!get(f2,j))
		dfs(i,j+1,od0,od1,f0,made(f1,j),made(f2,j),sum+1);
	if(j+1<m&&!get(f2,j)&&!get(f2,j+1))
		dfs(i,j+1,od0,od1,f0,f1,made(made(f2,j),j+1),sum+1);
	dfs(i,j+1,od0,od1,f0,f1,f2,sum);
}
 
void solve()
{
	int i,j,k;
	for(j=0;j<(1<<m);++j)
		for(k=0;k<(1<<m);++k)
			f[1][j][k]=INF;
	f[0][(1<<m)-1][(1<<m)-1]=0;
	for(i=0;i<=n;++i)
	{
		for(j=0;j<(1<<m);++j)
			for(k=0;k<(1<<m);++k)
				f[(i+1)&1][j][k]=INF;
		for(j=0;j<(1<<m);++j)
			for(k=0;k<(1<<m);++k)
				if(f[i&1][j][k]!=INF)
				{
					//if(j==(1<<m)-1&&k==map[1])print(map[1]);
					dfs(i,0,j,k,j,k,map[i+1],0);
				}
	}
	int answer=INF;
	for(j=0;j<(1<<m);++j)
		if(f[(n+1)&1][j][0]<answer)
			answer=f[(n+1)&1][j][0];
	printf("%d\n",answer);
}
 
int main()
{
	freopen("132.in","r",stdin);
	freopen("132.out","w",stdout);
	init();
	solve();
}