记录编号	158717	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	1938.[CQOI2015]标识设计	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	5.735 s
提交时间	2015-04-17 08:00:25	内存使用	240.56 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <algorithm>
#include <cmath>
using namespace std;
#define USEFREAD
#ifdef USEFREAD
#define InputLen 50000
char *ptr=(char *)malloc(InputLen);
#define getc() (*(ptr++))
#else
#define getc() (getchar())
#endif
#define SetFile(x) (freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout))
template<class T>inline void getd(T &x){
    char ch = getc();bool neg = false;
    while(!isdigit(ch) && ch != '-')ch = getc();
    if(ch == '-')ch = getc(), neg = true;
    x = ch - '0';
    while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
    if(neg)x = -x;
}
/***********************************************************************/
typedef long long LL;
LL f[2][4][31][31][4096], Ans;//f[是否要向右延伸][放了几个][x][y][列覆盖状态] = 方案数
int N, M, ST[4096], Scnt = 1;
#define id(x) (lower_bound(ST, ST + Scnt, x) - ST)
#define bin(x) (1 << x)
bool G[31][31];

inline void init(){
	getd(N), getd(M);
	memset(f, -1, sizeof(f));
	int i, j, k;
	for(i = 0;i < N;++i){
		while((k = getc()) != '.' && k != '#');
		for(j = 0;j < M;++j){
			G[i][j] = (k == '#');
			k = getc();
		}
	}
	for(i = 0;i+1 < M;++i){
		ST[Scnt++] = bin(i);
		for(j = 0;j < i;++j){
			ST[Scnt++] = bin(i) | bin(j);
			for(k = 0;k < j;++k)ST[Scnt++] = bin(i) | bin(j) | bin(k);
		}
	}
}
#define F(a,b,c,d,e) (f[a][b][c][d][e])
LL dfs(bool lk, int cnt, int i, int j, int St){
	LL &ans = F(lk,cnt,i,j,St);
	if(~ans)return ans;
	ans = 0;
	if(i == N)return ans = (!lk && !St && cnt == 3);
	if(j == M){if(!lk)ans = dfs(0,cnt,i+1,0,St);return ans;}
	register int b = bin(j), st = ST[St];
	if(lk && (b & st))return 0;
	if(lk){//from left
		if(G[i][j])return 0;
		ans = dfs(0,cnt,i,j+1,St) + dfs(1,cnt,i,j+1,St);
	}
	else if(b & st){//from above
		if(G[i][j])return 0;
		ans = dfs(1,cnt,i,j+1,id(st^b)) + dfs(0,cnt,i,j+1,St);
	}
	else{
		ans = dfs(0,cnt,i,j+1,St);//skip 
		if(!G[i][j] && cnt < 3 && j+1 < M)ans += dfs(0,cnt+1,i,j+1,id(st^b));// new
	}
	return ans;
}

int main(){
	#ifdef DEBUG
	freopen("test.txt", "r", stdin);
	#else
	SetFile(cqoi15_logo);
	#endif
	#ifdef USEFREAD
	fread(ptr,1,InputLen,stdin);
	#endif
	init();
	printf("%lld\n", dfs(0,0,0,0,0));
	
#ifdef DEBUG
    printf("\n%.3lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
    return 0;
}