[ZJ a228] 就少一個插座用很不方便

作法：

這題是輪廓線DP的最簡單的題型（插頭DP好像是專指要把輪廓線上的連通性壓成狀態的DP，不過名詞似乎沒那麼重要），這裡大概提一下輪廓線DP一般的想法。首先我們知道，「多段圖的決策問題」是最好DP的東西，具體來說就是，想像現在有好幾陀節點，第 $i$ 陀節點只有連往第 $i+1$ 陀節點的邊，問起點走到終點總共有多少條路徑。這顯然可以一陀一陀算，第 $i$ 陀所有節點的答案只和第 $i-1$ 陀所有節點的答案有關，並且轉移式是顯然的。也就是當我們現在要DP的圖是多段圖時，只要確定好每陀中有哪些節點，還有知道這些節點會連向哪些節點（也就是這個狀態可以轉移到哪些狀態，或稱為這個節點的所有決策），那麼就可以簡單的DP了。至於原本的問題我們也可以把他看成一個多段圖決策問題，假設現在已經有一條路徑滿足題目要求了，那麼考慮把所有格子拆開，每個格子只會是以下六種可能之一：

或是空白的（圖中的障礙），因此我們可以把這個問題看成「拼拼圖」的問題，考慮從上而下，從左而右一塊一塊把拼圖放上去（如果這格是障礙格那就只能放沒有線的拼圖），因此我們可以用「當前要放拼圖的格子」來劃分多段圖的每個階段，並且每個節點的決策就是放上一塊拼圖。至於每一陀中到底有哪些節點，總不能把當前格之前的所有格子的每一種放法都開一個節點。而觀察下圖可以發現，如果當前格是綠色叉叉所在的格子，那麼會對之後狀態有影響的只有「紅色的邊上是否有線通過」，不管紅線以上的路徑長成什麼歪來歪去的樣子。

因此我們可以用一個長$m+1$的$01$字串代表一個狀態。而在轉移時還要注意一些事情，以上圖為例，當前格就不能放下第 $1,3,4,5$ 種拼圖，因為第 $1,4,5$ 種拼圖的左邊有線，但這個狀態相應的位子沒有線，所以不能放。而第 $3,4,5$ 種拼圖的上面沒有線，但當前狀態相應的位子有線，所以也不能放。最後也要注意到：如果當前格在盤面的右邊界，那麼就不可以放右邊有線的拼圖，同理在下邊界時也不能放下面有線的拼圖。

code :

#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
const int maxn=11+1 ;
 
bool f(int x,char c)
{
    if(c=='U') return x==1||x==3||x==6 ;
    if(c=='D') return x==2||x==4||x==6 ;
    if(c=='L') return x==1||x==2||x==5 ;
    if(c=='R') return x==3||x==4||x==5 ;
}
 
int dp[2][1<<maxn] ;
int G[maxn][maxn] ;
void solve(int tc)
{
    int n,m ; scanf("%d%d",&n,&m) ;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
        scanf("%d",&G[i][j]) ;
 
    memset(dp,0,sizeof(dp)) ;
    dp[1][0]=1 ;
    int Ma=1<<(m+1),cur=0 ;
    for(int i=0;i<n;i++) for(int j=0;j<=m;j++,cur^=1)
    {
        fill(dp[cur],dp[cur]+Ma,0) ;
        if(j==m)
        {
            for(int S=0;S<(1<<m);S++) dp[cur][S]=dp[cur^1][S<<1] ;
            continue ;
        }
        for(int S=0;S<Ma;S++) if(dp[cur^1][S])
        {
            bool L=(S&(1<<(m-j))) , U=(S&(1<<(m-j-1))) ;
            int lo=(G[i][j]?1:0) , hi=(G[i][j]?6:0) ;
            for(int x=lo;x<=hi;x++)
            {
                if(L!=f(x,'L') || U!=f(x,'U')) continue ;
                if(i==n-1 && f(x,'D')) continue ;
                if(j==m-1 && f(x,'R')) continue ;
                bool n1=f(x,'D') , n2=f(x,'R') ;
                int nS=S ;
                if(L!=n1) nS^=(1<<(m-j)) ;
                if(U!=n2) nS^=(1<<(m-j-1)) ;
                dp[cur][nS]+=dp[cur^1][S] ;
                dp[cur][nS]%=MOD ;
            }
        }
    }
    printf("Case %d: %d\n",tc,dp[cur^1][0]) ;
}
 
main()
{
    int T,tc=0 ; scanf("%d",&T) ;
    while(T--) solve(++tc) ;
}