来学插头DP了= =
GDKOI前觉得不会考数位DP，GDOI前觉得插头DP用不上。。
结果令人伤感>_<
这题并不用增加状态。。
只要在形成环的时候，让形成环的位置在最后一个必走点之后，并且此时只有一个联通分量。
因为必走点处肯定有插头。。所以只有一个联通分量就意味着所有必走点都连在一起了。
选择经过的点就在转移的时候多一种方法。。。
学的是最小表示法。。又长又慢TAT。。跳错坑了= =
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #define ull unsigned long long 5 using namespace std; 6 const int modd=2333,maxzt=123333; 7 struct zs{ 8 struct hash{ 9 ull too;int pre; 10 }e[maxzt];int tot,last[modd]; 11 ull f[maxzt],zt[maxzt]; 12 13 inline int get(ull v){ 14 int i,x=v%modd; 15 for(i=last[x];i&&e[i].too!=v;i=e[i].pre); 16 if(i&&e[i].too==v)return i; 17 e[++tot].too=v,e[tot].pre=last[x],last[x]=tot; 18 zt[tot]=v;f[tot]=0; 19 return tot; 20 } 21 }hm[2]; 22 int i,j,k,n,m,tx,ty; 23 int can[14][14]; 24 ull ans; 25 char s[23]; 26 int v[2333]; 27 28 inline void clr(bool now){ 29 memset(hm[now].last,0,modd<<2), 30 hm[now].tot=0; 31 } 32 33 bool u[8];int id[8],mp[13]; 34 inline ull encode(){ 35 memset(u,0,8); 36 ull x=0;int tt=0; 37 for(int i=0;i<=m;mp[i]=id[mp[i]],x=x<<3|mp[i],i++) 38 if(mp[i]&&!u[mp[i]])u[mp[i]]=1,id[mp[i]]=++tt; 39 return x; 40 } 41 inline void decode(ull x){ 42 for(int i=m;i>=0;i--)mp[i]=x&7,x>>=3; 43 } 44 inline void shift(){ 45 for(int i=m;i;i--)mp[i]=mp[i-1]; 46 mp[0]=0; 47 } 48 49 inline void dp_blank(int x,int y,bool pre){ 50 int i,left,up,j;bool now=pre^1;ull zt,f; 51 clr(now); 52 for(i=1;i<=hm[pre].tot;i++){ 53 zt=hm[pre].zt[i],f=hm[pre].f[i], 54 decode(zt); 55 left=mp[y-1],up=mp[y]; 56 if(!left&&!up){ 57 if(can[x+1][y]&&can[x][y+1]){ 58 mp[y-1]=mp[y]=7; 59 if(y==m)shift(); 60 hm[now].f[ hm[now].get(encode()) ]+=f; 61 } 62 if(can[x][y]==2){ 63 mp[y-1]=mp[y]=0; 64 if(y==m)shift(); 65 hm[now].f[ hm[now].get(encode()) ]+=f; 66 } 67 } 68 if((!left)^(!up)){ 69 j=left|up; 70 if(can[x+1][y]){ 71 mp[y-1]=j,mp[y]=0; 72 if(y==m)shift(); 73 hm[now].f[ hm[now].get(encode()) ]+=f; 74 } 75 if(can[x][y+1]){ 76 mp[y-1]=0,mp[y]=j; 77 if(y==m)shift(); 78 hm[now].f[ hm[now].get(encode()) ]+=f; 79 } 80 } 81 if(left&&up){ 82 if(left==up) 83 if(x>tx||(x==tx&&y>=ty)){ 84 mp[y-1]=mp[y]=0; 85 if(encode()==0)ans+=f; 86 }else; 87 else{ 88 mp[y-1]=mp[y]=0; 89 for(j=0;j<=m;j++)if(mp[j]==up)mp[j]=left; 90 if(y==m)shift(); 91 hm[now].f[ hm[now].get(encode()) ]+=f; 92 } 93 } 94 } 95 } 96 inline void dp_bar(int x,int y,bool pre){ 97 int i,left,up;bool now=pre^1;ull f,zt; 98 clr(now); 99 for(i=1;i<=hm[pre].tot;i++){ 100 zt=hm[pre].zt[i],f=hm[pre].f[i]; 101 decode(zt); 102 left=mp[y-1],up=mp[y]; 103 if(!left&&!up){ 104 if(y==m)shift(); 105 hm[now].f[ hm[now].get(encode()) ]+=f; 106 } 107 } 108 } 109 110 int main(){ 111 int TT; 112 scanf("%d",&TT);v['X']=0,v['O']=1,v['*']=2; 113 for(int TTT=1;TTT<=TT;TTT++){ 114 scanf("%d%d",&n,&m); 115 memset(can,0,sizeof(can)); 116 for(i=1;i<=n;i++) 117 for(scanf("%s",s+1),j=1;j<=m;j++){ 118 can[i][j]=v[s[j]]; 119 if(s[j]=='O')tx=i,ty=j; 120 } 121 122 for(i=n,j=0;i;i--){ 123 for(j=m;j;j--)if(can[i][j]==1)break; 124 if(j>0)break; 125 } 126 tx=i,ty=j; 127 128 bool now=1,pre=0;ans=0; 129 clr(0),hm[pre].f[ hm[pre].get(0) ]=1; 130 for(i=1;i<=n;i++)for(j=1;j<=m;j++,swap(now,pre)) 131 if(can[i][j])dp_blank(i,j,pre);else dp_bar(i,j,pre); 132 printf("Case %d: %I64u ",TTT,ans); 133 } 134 return 0; 135 }