2331: [SCOI2011]地板

Time Limit: 5 Sec  Memory Limit: 128 MB

[][]

Description

 

lxhgww的小名叫“小L”，这是因为他总是很喜欢L型的东西。小L家的客厅是一个的矩形，现在他想用L型的地板来铺满整个客厅，客厅里有些位置有柱子，不能铺地板。现在小L想知道，用L型的地板铺满整个客厅有多少种不同的方案？

需要注意的是，如下图所示，L型地板的两端长度可以任意变化，但不能长度为0。铺设完成后，客厅里面所有没有柱子的地方都必须铺上地板，但同一个地方不能被铺多次。

Input

输入的第一行包含两个整数，R和C，表示客厅的大小。

接着是R行，每行C个字符。’_’表示对应的位置是空的，必须铺地板；’*’表示对应的位置有柱子，不能铺地板。

Output

输出一行，包含一个整数，表示铺满整个客厅的方案数。由于这个数可能很大，只需输出它除以20110520的余数。

Sample Input

2 2

*_

__

Sample Output

1

HINT

 

R*C<=100

 

Source

这题是我亲亲亲亲手手手手改了两天的简单的插头dp。。。之所以这么傻逼的原因是因为。。有了终止操作的时候 （Up==2||Left==2)时。。如果已经被换行了。。这个状！态！就！是！错！的！。。还需要重新decode一下。。还有就是。。Ans的问题。。我在下面贴出了几组数据。。

其余的做法都比较简单。。0表示该格无插头，1表示向内，2表示向外。。

那么对于该格如果left插头和up插头都为0 显然有3种插法：从未决策格子引两条箭头（右边和下边两个格子）、从该格向未决策的两个格子引两个外插头（右边和下边）

　　　　　　如果left插头或者up插头为0  自己想

                 如果left插头和up插头均为1 此时闭合，构成一个箭头，状态合法。。

我似乎是第一次写这么详细的题解。。因为我是真·蒟蒻。。这种题都做了两天。。TTTTTTTTTT_______TTTTTTTTTT

数据1：

5 5

*****

*****

*****

*****

****_ 

输出0

3 2

__

__

__

输出2

4 25

*___**_______***_*__**_*_

_______________*_*_**____

*_*_________**___**_____*

__**__*_________*___**___

输出38618

。。反正我是自己做了这三组数据发现的问题。。

 

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 using namespace std; 8 const int N = 531450; 9 const int Hash = 10007; 10 const int Mod = 20110520; 11 #define nxt (cur^1) 12 #define For(i,n) for(int i=1;i<=n;i++) 13 #define Rep(i,l,r) for(int i=l;i<=r;i++) 14 #define Down(i,r,l) for(int i=r;i>=l;i--) 15 16 struct statedp{ 17 int size,st[N],head[Hash],f[N],next[N]; 18 void clear(){size=0;memset(head,-1,sizeof(head));} 19 void push(int state,int ans){ 20 int Key = state % Hash; 21 for(int p = head[Key];p!=-1;p=next[p]) 22 if(st[p]==state) {f[p]=(ans+f[p])%Mod;return;} 23 st[size]=state;f[size]=ans; 24 next[size]=head[Key];head[Key]=size++; 25 } 26 }dp[2]; 27 28 int n,m,Ans,code[110],maze[110][110]; 29 int Endx,Endy; 30 char ch; 31 void init(){ 32 scanf("%d%d",&n,&m); 33 For(i,n){ 34 scanf("\n"); 35 For(j,m){ 36 scanf("%c",&ch); 37 if(ch=='_') {maze[i][j] = 1;Endx=i;Endy=j;} 38 else maze[i][j] = 0; 39 } 40 } 41 if(n
           
            << 2 | code[i]; 54 return ret; 55 } 56 57 void decode(int st){ 58 Down(i,m,0) code[i] = st&3,st>>=2; 59 } 60 61 void shift(){ 62 Down(i,m,1) code[i] = code[i-1];code[0] = 0; 63 } 64 65 void dpblock(int i,int j,int cur){ 66 int Lim = (j==m)?(2):(0); 67 Rep(k,0,dp[cur].size-1) 68 dp[nxt].push(dp[cur].st[k]>>Lim,dp[cur].f[k]); 69 } 70 71 void dpblank(int i,int j,int cur){ 72 Rep(k,0,dp[cur].size-1){ 73 decode(dp[cur].st[k]); 74 int Left = code[j-1] , Up = code[j]; 75 if(!Left&&!Up){ 76 if(maze[i+1][j] && i