sxczf's Blog

1519. Formula 1

Background

Regardless of the fact, that Vologda could not get rights to hold the Winter Olympic games of 20**, it is well-known, that the city will conduct one of the Formula 1 events. Surely, for such an important thing a new race circuit should be built as well as hotels, restaurants, international airport - everything for Formula 1 fans, who will flood the city soon. But when all the hotels and a half of the restaurants were built, it appeared, that at the site for the future circuit a lot of gophers lived in their holes. Since we like animals very much, ecologists will never allow to build the race circuit over the holes. So now the mayor is sitting sadly in his office and looking at the map of the circuit with all the holes plotted on it.

Problem

Who will be smart enough to draw a plan of the circuit and keep the city from inevitable disgrace? Of course, only true professionals - battle-hardened programmers from the first team of local technical university!.. But our heroes were not looking for easy life and set much more difficult problem: "Certainly, our mayor will be glad, if we find how many ways of building the circuit are there!" - they said.

It should be said, that the circuit in Vologda is going to be rather simple. It will be a rectangleN*M cells in size with a single circuit segment built through each cell. Each segment should be parallel to one of rectangle's sides, so only right-angled bends may be on the circuit. At the picture below two samples are given for N = M = 4 (gray squares mean gopher holes, and the bold black line means the race circuit). There are no other ways to build the circuit here.

Input

The first line contains the integer numbers N and M (2 ≤ N, M ≤ 12). Each of the next N lines contains M characters, which are the corresponding cells of the rectangle. Character "." (full stop) means a cell, where a segment of the race circuit should be built, and character "*" (asterisk) - a cell, where a gopher hole is located.

Output

You should output the desired number of ways. It is guaranteed, that it does not exceed 263-1.

Samples

input	output
4 4 **.. .... .... ....	2
4 4 .... .... .... ....	6

 TM写了半天调了半天的题= =

orz给我们讲课的李洋

插头dp

cdq论文里讲的题

cdq论文->http://wenku.baidu.com/view/ed2b3e23482fb4daa58d4b74.html

好吧不得不承认神犇的论文。。。看不懂。。。

然后搜题解搜到了->http://blog.sina.com.cn/s/blog_51cea4040100gmky.html

请看完那篇再来看这篇

写的详细多了。。

只是后面的代码。。有点小问题。。

注意的地方：状态不用long long

4^12离long long还很远

但是答案要long long。。详见题面最后一行

额然后好像没了。

注意常数。。内存。。

从9点的讲课到下午3点半。。

纪念。。。。。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#define N 15
#define hs 1000000
using namespace std;
int a[N][N],b,c,d,e,f,g,i,j,k,l,m,n,nn,mm,J,p,q;
int tot[2],state[2][400005],s,S;
int hash[hs+5],jz[N];
char ch[N];
long long ans,sum[2][400005],h;
void init(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++){
		scanf("%s",ch+1);
		for(j=1;j<=m;j++)if(ch[j]=='.'){
			a[i][j]=1;
			nn=i;mm=j;
			//nn,mm表示最后一个空的格子
			//最后一对联通只能在最后一个格子进行合并 
		}
	}
	//jz[i]表示状态的第i位->左移jz[i]位…… 
	for(i=1;i<=12;i++)jz[i]=i<<1;
}

inline void in(int s,long long h){//s：状态，h：方案
	int hashs=s%hs;
	while(hash[hashs]){
		if(state[k][hash[hashs]]==s){//找到了 
			sum[k][hash[hashs]]+=h;
			return ;
		}
		hashs++;
		if(hashs>=hs)hashs-=hs;
	}
	//找不到（新建） 
	hash[hashs]=++tot[k];
	state[k][tot[k]]=s;
	sum[k][tot[k]]=h;
}

void work(){
	tot[0]=1;state[0][1]=0;sum[0][1]=1;
	for(i=1;i<=n;i++){//第i行 
		for(j=1;j<=m;j++){//第j个 
			k^=1;
			memset(hash,0,sizeof(hash));
			tot[k]=0;
			for(l=1;l<=tot[k^1];l++){//枚举上一状态 
				//p：左边的插头，q：右边的插头 s:状态 h:状态s的方案数 
				s=state[k^1][l];
				h=sum[k^1][l];
				p=(s>>jz[j-1])&3;
				q=(s>>jz[j])&3;
				//1:(   2:)   0:    
				if(!a[i][j]){//障碍 
					if(!p&&!q)in(s,h);
					continue;
				}
				if(!p&&!q){//状态
					if(a[i+1][j]&&a[i][j+1]){//是否能转移 
						S=s+(1<<jz[j-1])+(2<<jz[j]);//新状态 
						in(S,h);//转移 
					}
					continue;
				}
				if(!p&&q){
					if(a[i][j+1]){
						in(s,h);
					}
					if(a[i+1][j]){
						S=s-(q<<jz[j])+(q<<jz[j-1]);
						in(S,h);
					}
					continue;
				}
				if(p&&!q){
					if(a[i+1][j]){
						in(s,h);
					}
					if(a[i][j+1]){
						S=s-(p<<jz[j-1])+(p<<jz[j]);
						in(S,h);
					}
					continue;
				}
				//if(p&&q)<--懒得写了，本来后面的状态外面要套这只 
				if(p==1&&q==1){
					S=s-(p<<jz[j-1])-(q<<jz[j]);
					for(J=j+1,g=1;J<=n;J++){
						d=(S>>jz[J])&3;
						if(d==1)g++;
						if(d==2)g--;
						if(!g)break;
					}
					S=S-(2<<jz[J])+(1<<jz[J]);
					in(S,h);
					continue;
				}
				if(p==2&&q==1){
					S=s-(p<<jz[j-1])-(q<<jz[j]);
					in(S,h);
					continue;
				}
				if(p==2&&q==2){
					S=s-(p<<jz[j-1])-(q<<jz[j]);
					for(J=j-2,g=1;J;J--){
						d=(S>>jz[J])&3;
						if(d==1)g--;
						if(d==2)g++;
						if(!g)break;
					}
					S=S-(1<<jz[J])+(2<<jz[J]);
					in(S,h);
				}
				if(p==1&&q==2){
					if(i==nn&&j==mm)ans+=h;
					//只能在最后一格合并 
					continue;
				}
			}
		}
		for(register int j=1;j<=tot[k];j++)state[k][j]<<=2;
		//上一行末尾状态到下一行。
		//自己想下。。显然要左移一位对不对 
	}
}

void out(){
	cout<<ans<<endl;
}

int main(){
	init();
	work();
	out();
	return 0;
}