记录编号	87041	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[Ural 1519] 一级方程式赛车	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.737 s
提交时间	2014-01-29 22:11:53	内存使用	21.29 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<queue>
#include<deque>
#include<set>
using namespace std;
typedef long long ll;
const int SIZEN=15,HASHVAL=1999997;//hash值
int N,M;
int lastn=0,lastm=0;
bool board[SIZEN][SIZEN]={0};//=1表示可以放
int hash[HASHVAL];
vector<pair<ll,ll> > f[2];//first是状态,second是个数
void hashpush(vector<pair<ll,ll> > &st,ll s,ll data){//给now里面的s状态加上data
	int hashpos=s%HASHVAL;
	while(hash[hashpos]){
		if(st[hash[hashpos]].first==s){
			st[hash[hashpos]].second+=data;
			return;
		}
		hashpos++;
		if(hashpos==HASHVAL) hashpos=0;
	}
	hash[hashpos]=st.size();
	st.push_back(make_pair(s,data));
}
//M+1个插头从左到右编号为1~M+1
int getdig(ll s,int k){//取s中的第k位,即它的右起第k-1个四进制位
	return (s>>((k-1)<<1))&3;
}
void printdig(ll s){//调试接口,输出s的所有四进制位信息
	for(int i=1;i<=M+1;i++){cout<<getdig(s,i);}
}
int changedig(ll s,int k,int t){//将s的第k位改成t
	int temp=(k-1)<<1;
	s&=~(3<<temp);
	return s|(t<<temp);
}
int rightmatch(ll s,int k){//与s的第k位匹配的右插头
	int dta=1,temp;
	while(k<=M+1){
		k++;
		temp=getdig(s,k);
		if(temp==1) dta++;
		else if(temp==2) dta--;
		if(dta==0) return k;
	}
	cout<<"bracket match error!"<<endl;
	return -1;
}
int leftmatch(ll s,int k){
	int dta=-1,temp;
	while(k>=1){
		k--;
		temp=getdig(s,k);
		if(temp==1) dta++;
		else if(temp==2) dta--;
		if(dta==0) return k;
	}
	cout<<"bracket match error!"<<endl;
	return -1;
}
ll ans=0;
void work(void){
	int k=0,temp;
	f[k].push_back(make_pair(0,1));//最初没有任何插头
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++){
			k^=1;
			memset(hash,0,sizeof(hash));
			f[k].clear();
			//现在k^1就是上一个状态
			for(int km=0;km<f[k^1].size();km++){
				ll s=f[k^1][km].first,data=f[k^1][km].second;
				int p=getdig(s,j),q=getdig(s,j+1);
				if(!board[i][j]){//此处有障碍
					if(!p&&!q) hashpush(f[k],s,data);
					continue;
				}
				//无障碍的情况
				if(!p&&!q){
					//此时,唯一的情况是该格子既有下插头又有右插头
					if(board[i][j+1]&&board[i+1][j]){
						//j插头和j+1插头是一对匹配的括号
						temp=changedig(s,j,1);temp=changedig(temp,j+1,2);
						hashpush(f[k],temp,data);
					}
				}
				else if(!p&&q){
					if(board[i][j+1]){
						//向右延伸,这个插头相当于原来的上插头
						hashpush(f[k],s,data);
					}
					if(board[i+1][j]){
						//向下延伸,占用j号插头,而j+1号插头则为空
						//j号插头相当于原来的q插头
						temp=changedig(s,j,q);temp=changedig(temp,j+1,0);
						hashpush(f[k],temp,data);
					}
				}
				else if(p&&!q){
					if(board[i+1][j]){
						//向下延伸,这个插头相当于原来的左插头
						hashpush(f[k],s,data);
					}
					if(board[i][j+1]){
						//向右延伸,j号插头为空,占用j+1号插头
						//j+1号插头相当于原来的p插头
						temp=changedig(s,j,0);temp=changedig(temp,j+1,p);
						hashpush(f[k],temp,data);
					}
				}
				else if(p==1&&q==1){
					//此时,插头j和j+1均应为0,同时q对应的右括号应改为左括号
					temp=changedig(s,rightmatch(s,j+1),1);
					temp=changedig(temp,j,0),temp=changedig(temp,j+1,0);
					hashpush(f[k],temp,data);
				}
				else if(p==2&&q==2){
					//此时,插头j和j+1均应为0,同时p所对应的左括号应改为右括号
					temp=changedig(s,leftmatch(s,j),2);
					temp=changedig(temp,j,0),temp=changedig(temp,j+1,0);
					hashpush(f[k],temp,data);
				}
				else if(p==2&&q==1){
					//此时,插头j和j+1均应为0,其余插头不受影响
					temp=changedig(s,j,0),temp=changedig(temp,j+1,0);
					hashpush(f[k],temp,data);
				}
				else if(p==1&&q==2){
					//此时形成了一个完整的哈密尔顿回路,当且仅当这是最后一个状态才是合法的
					if(i==lastn&&j==lastm){
						ans+=data;//我承认我是懒得再写个hash找0了!
					}
				}
			}
		}
		for(int km=0;km<f[k].size();km++) f[k][km].first<<=2;//将行末的状态转成下一行初的状态
		//这个转的方法是:1号插头为空,后面的依次赋值为原来的1~N号插头,即乘4
	}
}
void read(void){
	scanf("%d%d",&N,&M);
	string str;
	for(int i=1;i<=N;i++){
		cin>>str;
		for(int j=1;j<=M;j++){
			if(str[j-1]=='.'){
				board[i][j]=1;
				lastn=i;
				lastm=j;
			}
			else board[i][j]=0;
		}
	}
}
int main(){
	freopen("formula1.in","r",stdin);
	freopen("formula1.out","w",stdout);
	read();
	work();
	cout<<ans<<endl;
	return 0;
}