[UVa 10572] 黑和白 - cstdio - 87048

记录编号	87048	评测结果	AAAAAAAAAA
题目名称	[UVa 10572] 黑和白	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.125 s
提交时间	2014-01-30 16:22:29	内存使用	0.32 MiB
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<queue>
#include<deque>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
//规定黑为1白为0
//采用一个64位整数储存,从左到右依次排放:8bit轮廓线上的格子颜色,24bit轮廓线上格子连通状态的最小表示法
//把这个64位整数叫做"状态码"
//在轮廓线上的格子颜色和连通状态的最小表示法中,从低位到高位依次存储从左到右的格子状态
//本题的下标从0开始
const int SIZEN=10;
const ll comp_ext=(1<<24)-1;//将状态码按位与这个数后得到连通状态的最小表示法
const ll col_ext=(1<<8)-1;//将状态码右移24位,按位与这个数得到轮廓线上格子颜色
int ROW,COLU;//行数和列数
class STATE{
public:
	bool color[SIZEN];//轮廓线上格子颜色
	bool upleft;//左上方格子颜色
	short comp[SIZEN];//各格子的连通分量
	short numcomp;//连通分量总数
	short ncolorcomp[2];//白黑连通分量个数
	void relable(void){//将comp(其实是一个深度为1的并查集)改成最小表示法
		//这实际上是一个重新指定连通分量编号的过程
		int atp[SIZEN]={0};
		memset(atp,-1,sizeof(atp));
		numcomp=ncolorcomp[0]=ncolorcomp[1]=0;
		for(int i=0;i<COLU;i++){
			if(atp[comp[i]]==-1){//如果这个连通分量尚未标号
				atp[comp[i]]=numcomp++;
				ncolorcomp[color[i]]++;
			}
			comp[i]=atp[comp[i]];
		}
	}
	void merge(int a,int b){//将所有编号为b的连通分量改成a
		if(a==b) return;
		for(int i=0;i<COLU;i++){
			if(comp[i]==b) comp[i]=a;
		}
	}
	void clear(void){
		memset(color,0,sizeof(color));
		upleft=0;
		memset(comp,0,sizeof(comp));
		numcomp=0;
		memset(ncolorcomp,0,sizeof(ncolorcomp));
	}
	ll mdl(void){//调制成状态码
		ll com=0,col=0;
		ll ans=0;
		for(int i=COLU-1;i>=0;i--) col=(col<<1)+color[i];
		ans=(ans<<8)+col;
		for(int i=COLU-1;i>=0;i--) com=(com<<3)+comp[i];
		ans=(ans<<24)+com;
		return ans;
	}
};
int board[SIZEN][SIZEN]={0};
bool nowgrid[SIZEN][SIZEN]={0},ansgrid[SIZEN][SIZEN]={0};
map<ll,int> f[SIZEN][SIZEN][2];
bool legal=0;//是否存在合法方案
int DP(int x,int y,STATE &S,int forcecol){
	if(y==COLU){y=0;x++;}//计算行末相当于计算下一行初
	S.relable();
	if(x==ROW){//已经计算完成了
		if(S.ncolorcomp[0]>1||S.ncolorcomp[1]>1) return 0;//未成连通块
		if(!legal){
			legal=true;
			for(int i=0;i<ROW;i++){
				for(int j=0;j<COLU;j++) ansgrid[i][j]=nowgrid[i][j];
			}
		}
		return 1;
	}
	//如果左和上不同色,左上不必考虑,认为是0
	if(x&&y&&S.color[y]!=S.color[y-1]) S.upleft=0;
	ll scode;
	if(forcecol<0){//如果不指定颜色就试图调用之前的状态
		scode=S.mdl();
		if(f[x][y][S.upleft].count(scode)) return f[x][y][S.upleft][scode];
	}
	int ans=0;
	for(int nowc=0;nowc<=1;nowc++){
		if(forcecol==1-nowc||board[x][y]==1-nowc) continue;//与确定的冲突,这旨在让指定颜色的状况也是用不指定颜色的计算通道,从而减少代码量
		if(x&&y&&S.color[y-1]==nowc&&S.color[y]==nowc&&S.upleft==nowc) continue;
		STATE T=S;
		T.color[y]=nowc;//将其染色
		T.upleft=S.color[y];//得出左上方格子的状态
		T.comp[y]=S.numcomp;//标号设为S的最大连通分量编号+1
		if(x>0&&S.color[y]==nowc) T.comp[y]=S.comp[y];//若与上方格子颜色相同,则它们处于同一分量
		nowgrid[x][y]=nowc;
		if(y>0&&T.color[y-1]==nowc) T.merge(T.comp[y-1],T.comp[y]);//若和左边颜色相同,则合并
		if(x>0&&S.color[y]==1-nowc){//如果上方格子以后无法在以后连上
			if(find(T.comp,T.comp+COLU,S.comp[y])==T.comp+COLU){//如果该连通分量消失
				if(S.ncolorcomp[1-nowc]>1||x<ROW-2) continue;
				//如果还有其他这个颜色的连通分量,或还有至少两行,显然是不合法的
				ans+=DP(x,y+1,T,nowc);//以后强制涂nowc
				continue;
			}
		}
		ans+=DP(x,y+1,T,forcecol);
	}
	if(forcecol<0){
		f[x][y][S.upleft][scode]=ans;
	}
	return ans;
}
int main(){
	freopen("blackandwhite.in","r",stdin);
	freopen("blackandwhite.out","w",stdout);
	int T;
	//scanf("%d",&T);
	T=1;
	for(int kase=1;kase<=T;kase++){
		scanf("%d%d",&ROW,&COLU);
		for(int i=0;i<ROW;i++){
			string str;
			cin>>str;
			for(int j=0;j<COLU;j++){
				if(str[j]=='o') board[i][j]=0;
				else if(str[j]=='#') board[i][j]=1;
				else if(str[j]=='.') board[i][j]=-1;
			}
		}
		STATE S;
		S.clear();
		S.relable();
		for(int i=0;i<8;i++){
			for(int j=0;j<8;j++){
				for(int k=0;k<2;k++) f[i][j][k].clear();
			}
		}
		legal=0;
		printf("%d\n",DP(0,0,S,-1));
		/*if(legal){
			for(int i=0;i<ROW;i++){
				for(int j=0;j<COLU;j++){
					if(ansgrid[i][j]==0) cout<<"o";
					else if(ansgrid[i][j]==1) cout<<"#";
				}
				cout<<endl;
			}
		}
		cout<<endl;*/
	}
	return 0;
}