Ural 1519 Formula 1 插头DP(单回路)

　　题目链接：http://acm.timus.ru/problem.aspx?space=1&num=1519
　一条哈密顿回路路，反正是写到蛋疼了，不过终于解决了，插头DP这玩意，太容易出错了，要注意block的处理。
  1 //STATUS:C++_AC_343MS_961KB
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 #include<string.h>
  5 #include<math.h>
  6 #include<iostream>
  7 #include<string>
  8 #include<algorithm>
  9 #include<vector>
 10 #include<queue>
 11 #include<stack>
 12 #include<map>
 13 using namespace std;
 14 #define LL long long
 15 #define pii pair<int,int>
 16 #define Max(a,b) ((a)>(b)?(a):(b))
 17 #define Min(a,b) ((a)<(b)?(a):(b))
 18 #define mem(a,b) memset(a,b,sizeof(a))
 19 #define lson l,mid,rt<<1
 20 #define rson mid+1,r,rt<<1|1
 21 const int N=15,INF=0x3f3f3f3f,MOD=4001,STA=1000010;
 22 const double DNF=100000000000;
 23 
 24 int g[N][N],code[N],ma[N];
 25 int n,m,ex,ey;
 26 
 27 struct Hash{
 28     int first[MOD],next[STA],size;
 29     LL f[STA],sta[STA];
 30     void init(){
 31         size=0;
 32         mem(first,-1);
 33     }
 34     void add(LL st,LL ans){
 35         int i,u=st%MOD;
 36         for(i=first[u];i!=-1;i=next[i]){
 37             if(sta[i]==st){
 38                 f[i]+=ans;
 39                 return;
 40             }
 41         }
 42         sta[size]=st;
 43         f[size]=ans;
 44         next[size]=first[u];
 45         first[u]=size++;
 46     }
 47 }hs[2];
 48 
 49 void shift(int p)    //换行移位
 50 {
 51     int k;
 52     LL sta;
 53     for(k=0;k<hs[!p].size;k++){
 54         sta=hs[!p].sta[k]<<3;
 55         hs[p].add(sta,hs[!p].f[k]);
 56     }
 57 }
 58 
 59 LL getsta()    //最小表示法
 60 {
 61     LL i,cnt=1,sta=0;
 62     mem(ma,-1);
 63     ma[0]=0;
 64     for(i=0;i<=m;i++){
 65         if(ma[code[i]]==-1)ma[code[i]]=cnt++;
 66         code[i]=ma[code[i]];
 67         sta|=(LL)code[i]<<(3*i);
 68     }
 69     return sta;
 70 }
 71 
 72 void getcode(LL sta)
 73 {
 74     int i;
 75     for(i=0;i<=m;i++){
 76         code[i]=sta&7;
 77         sta>>=3;
 78     }
 79 }
 80 
 81 void unblock(int i,int j,int p)
 82 {
 83     int k,t;
 84     LL cnt,x,y;
 85     for(k=0;k<hs[!p].size;k++){
 86         getcode(hs[!p].sta[k]);
 87         x=code[j],y=code[j+1];
 88         cnt=hs[!p].f[k];
 89         if(x && y){          //合并连通分量
 90             code[j]=code[j+1]=0;
 91             if(x!=y){
 92                 for(t=0;t<=m;t++)
 93                     if(code[t]==y)code[t]=x;
 94                 hs[p].add(getsta(),cnt);
 95             }
 96             else if(i==ex && j==ey){     //最后一个点特殊处理
 97                 hs[p].add(getsta(),cnt);
 98             }
 99         }
100 
101         else if(x&&!y || !x&&y){    //延续连通分量
102             t=x?x:y;
103             if(g[i+1][j]){
104                 code[j]=t;code[j+1]=0;
105                 hs[p].add(getsta(),cnt);
106             }
107             if(g[i][j+1]){
108                 code[j]=0;code[j+1]=t;
109                 hs[p].add(getsta(),cnt);
110             }
111         }
112         else if(g[i+1][j] && g[i][j+1]){   //创建新连通分量
113             code[j]=code[j+1]=8;
114             hs[p].add(getsta(),cnt);
115         }
116     }
117 }
118 
119 void block(LL j,int p)
120 {
121     int k;
122     for(k=0;k<hs[!p].size;k++){
123         getcode(hs[!p].sta[k]);
124         code[j]=code[j+1]=0;
125         hs[p].add(getsta(),hs[!p].f[k]);
126     }
127 }
128 
129 LL slove()
130 {
131     int i,j,p;
132     hs[0].init();
133     hs[p=1].init();
134     hs[0].add(0,1);
135     for(i=0;i<n;i++){
136         for(j=0;j<m;j++){
137             if(g[i][j])unblock(i,j,p);
138             else block(j,p);    //p=!p优化
139             hs[p=!p].init();
140         }
141         shift(p);   //换行移位
142         hs[p=!p].init();
143     }
144     for(i=0;i<hs[!p].size;i++){
145         if(hs[!p].sta[i]==0)return hs[!p].f[i];
146     }
147 
148     return 0;
149 }
150 
151 int main()
152 {
153  //   freopen("in.txt","r",stdin);
154     int i,j;
155     LL ans;
156     char c;
157     while(~scanf("%d%d",&n,&m) && (n || m))
158     {
159         mem(g,0);
160         ex=-1;
161         for(i=0;i<n;i++){
162             for(j=0;j<m;j++){
163                 scanf(" %c",&c);
164                 g[i][j]=(c=='.');
165                 if(g[i][j])ex=i,ey=j;
166             }
167         }
168         if(ex==-1)ans=0;
169         else ans=slove();
170 
171         printf("%I64d\n",ans);
172     }
173     return 0;
174 }