记录编号	159486	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[CQOI2015]标识设计	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	5.804 s
提交时间	2015-04-21 17:22:44	内存使用	240.64 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
typedef long long LL;
const LL INF=1e18;
const int SIZEN=31,SIZES=4097;
int N,M;
int tot;
char board[SIZEN][SIZEN];
map<int,int> id_lis;
int state[SIZES];
LL F[SIZEN][SIZEN][4][SIZES][2];
int getdig(int s,int i){
	return (s>>i)&1;
}
void add_state(int x){
	id_lis[x]=tot;
	state[tot++]=x;
}
void prepare(void){
	memset(F,-1,sizeof(F));
	add_state(0);
	for(int i=0;i<M-1;i++){
		add_state(1<<i);
		for(int j=i+1;j<M-1;j++){
			add_state((1<<i)|(1<<j));
			for(int k=j+1;k<M-1;k++){
				add_state((1<<i)|(1<<j)|(1<<k));
			}
		}
	}
}
LL DFS(int x,int y,int res,int id,int lim){
	//还有res个L没有放,当前放下的L状态为id,lim为当前格是否需要向右延伸
	LL &ans=F[x][y][res][id][lim];
	if(ans!=-1) return ans;
	int s=state[id];
	ans=0;
	if(x==N) return ans=(!res&&!id)?1:0;
	if(y==M){
		if(lim) return ans=0;
		else return ans=DFS(x+1,0,res,id,0);
	}
	if(getdig(s,y)){//某个L的竖线经过这一列
		if(board[x][y]=='#'||lim) return ans=0;
		else{
			int t=s^(1<<y);
			ans+=DFS(x,y+1,res,id_lis[t],1);//让这个L转而向右
			ans+=DFS(x,y+1,res,id,0);//继续向下什么都不干
			return ans;
		}
	}
	if(lim){//必须放,接着左边的
		if(board[x][y]=='#') return ans=0;
		else return ans=DFS(x,y+1,res,id,1)+DFS(x,y+1,res,id,0);//下一格可以接着放也可以不放
	}
	ans=DFS(x,y+1,res,id,0);//什么也不干......
	if(res>0&&y+1<M&&board[x][y]=='.'){//放下一个L的竖线
		int t=s|(1<<y);
		ans+=DFS(x,y+1,res-1,id_lis[t],0);
	}
	return ans;
}
int main(){
	freopen("cqoi15_logo.in","r",stdin);
	freopen("cqoi15_logo.out","w",stdout);
	scanf("%d%d",&N,&M);
	for(int i=0;i<N;i++) scanf("%s",board[i]);
	prepare();
	LL ans=DFS(0,0,3,0,0);
	cout<<ans<<endl;
	return 0;
}