记录编号	186406	评测结果	AAAAAAAAAA
题目名称	[UVa 10572] 黑和白	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.163 s
提交时间	2015-09-12 17:49:02	内存使用	0.32 MiB

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<map>
#include<cstring>
using namespace std;
typedef long long LL;
int N,M,P[10][10];//0代表无染色，1代表白色，2代表黑色
bool g[10][10]={0};
//状态用一个64位的整数表示，其中，前8个bit表示颜色，后24个表示连通分量的编号，每个连通分量用3个bit
class miku
{
public:
	short comp[10];//每个连通分两的编号
	bool co[10];//每个格子的颜色
	bool L;//左上的格子
	short sum[2];//两种连通分量的个数
	void print()//调试接口
	{
		cout<<"白:"<<sum[0]<<endl;
		cout<<"黑:"<<sum[1]<<endl;
		for(int i=1;i<=N;i++)
			cout<<co[i]<<" ";
		cout<<endl;
		for(int i=1;i<=N;i++)
			cout<<comp[i]<<" ";
		cout<<endl;
		cout<<"L:"<<L<<endl;
	}
	void make()//将每个连通分量重新编号
	{
		int tem[10];
		int tot=0;
		memset(tem,-1,sizeof(tem));
		sum[0]=sum[1]=0;
		for(int i=1;i<=N;i++)
		{
			if(tem[comp[i]]==-1)
			{
				tem[comp[i]]=tot++;
				sum[co[i]]++;
			}
			comp[i]=tem[comp[i]];
		}
	}
	void clear()
	{
		memset(co,0,sizeof(co));
		L=0;
		memset(comp,0,sizeof(comp));
		sum[0]=sum[1]=0;
	}
	LL mul()//状态码
	{
		LL re=0;
		for(int i=1;i<=N;i++)
			re=(re<<1)+co[i];
		for(int i=1;i<=N;i++)
			re=(re<<3)+comp[i];
		return re;
	}
	void change(int a,int b)//把comp为b的全部修改为a
	{
		for(int i=1;i<=N;i++)
			if(comp[i]==b)
				comp[i]=a;
	}
	bool find_comp(int a)
	{
		for(int i=1;i<=N;i++)
			if(comp[i]==a) return 1;
		return 0;
	}
	bool find_co(bool a)
	{
		for(int i=1;i<=N;i++)
			if(co[i]==a) return 1;
		return 0;
	}
};
map<LL,int> f[10][10][2];
int DP(int x,int y,miku &S,int now)//这三个参数分别代表了纵，横，状态,是否需强制染色
{
	if(y==N+1)
	{
		x++;y=1;
	}
	S.make();
	if(x==M+1)
	{
		if(S.sum[0]>1||S.sum[1]>1) return 0;//不满足四连通
		/*S.print();
		for(int i=1;i<=M;i++)
		{
			for(int j=1;j<=N;j++)
				cout<<g[i][j]<<" ";
			cout<<endl;
		}
		cout<<endl;*/
		return 1;
	}
	LL q;
	if(now<0)
	{
		q=S.mul();
		if(f[x][y][S.L].count(q)) 
		{
			/*cout<<x<<" "<<y<<endl;S.print();
			for(int i=1;i<=M;i++)
			{
				for(int j=1;j<=N;j++)
					cout<<g[i][j]<<" ";
				cout<<endl;
			}
			cout<<endl;*/
			return f[x][y][S.L][q];
		}
	}
	miku T;
	int ans=0;
	for(int i=0;i<=1;i++)
	{
		if(x>1&&y>1&&S.L==i&&S.co[y-1]==i&&S.co[y]==i) continue;//四个方块颜色相同
		if(now>=0&&i!=now) continue;
		if(P[x][y]!=0&&P[x][y]-1!=i) continue;
		T=S;
		T.co[y]=i;
		T.L=S.co[y];
		T.comp[y]=T.sum[0]+T.sum[1];
		if(x>1&&T.co[y]==S.co[y]) T.comp[y]=S.comp[y];
		if(y>1&&T.co[y-1]==T.co[y]) T.change(T.comp[y-1],T.comp[y]);
		if(x>1&&T.co[y]!=S.co[y])
		{
			if(!T.find_comp(S.comp[y]))//由于新加的格子，原先的连通块消失
			{
				if(T.find_co(S.co[y])||x<M-1) 
					continue;
				g[x][y]=i;
				ans+=DP(x,y+1,T,i);
				continue;
			}
		}
		g[x][y]=i;
		ans+=DP(x,y+1,T,now);
	}
	if(now<0)
	{
		f[x][y][S.L][S.mul()]=ans;
	}
	return ans;
}
void work()
{
	miku S;
	S.clear();
	int ans=DP(1,1,S,-1);
	printf("%d\n",ans);
}
int main()
{
	freopen("blackandwhite.in","r",stdin);
	freopen("blackandwhite.out","w",stdout);
	scanf("%d%d",&M,&N);
	char s[10];
	for(int i=1;i<=M;i++)
	{
		scanf("%s",s);
		for(int j=1;j<=N;j++)
		{
			if(s[j-1]=='o')
				P[i][j]=1;
			else if(s[j-1]=='#') P[i][j]=2;
			else if(s[j-1]=='.') P[i][j]=0;
			else printf("error\n");
		}
	}
	work();
	return 0;
}