还不太会做这类题，总之感觉有点难啊。
用深搜代替打表求出一行所有的可行状态，注意要进行剪枝
这是自己理解的代码，但是tle了
#include<bits/stdc++.h> using namespace std; #define mod 1000000007 #define maxn 600005 int n,m,dp[2][maxn],sum; char mp[15][15][15]; int a[200],tag,flag,s[15]; // void dfs(int r,int num,int up,int down,int right){//用dfs搜索出第r行的下状态，上状态 和右侧颜色 int xx,rr,yy,ll,i; if(num==m){//搜满了一行 if(r==0)dp[flag][down]+=tag;//如果是第一行，那么只要把组成这种状态的方案数加上即可 else { dp[flag][down]+=dp[(flag+1)%2][up]*tag;//加上上一行下状态为up的计数值 dp[flag][down]%=mod; } return; } for(int i=1;i<4;i++)//判断改行第i个方块是不是四方相同的 if(mp[r][num][i]!=mp[r][num][0])break; if(i==4){//四方相同的块直接跳过即可，并且这一行的结果要加上4 tag*=4; xx=a[mp[r][num][0]]; if(xx==right || right==-1)dfs(r,num+1,up*3+xx,down*3+xx,xx); tag/=4; return; } for(int i=0;i<4;i++){//枚举该方块的安放方式，符合条件的进入下一轮深搜 xx=a[mp[r][num][i]];//下一格上方 rr=a[mp[r][num][(i+1)%4]];//下一格右侧 yy=a[mp[r][num][(i+2)%4]];//下一格下放 ll=a[mp[r][num][(i+3)%4]];//下一格左侧 if(right==-1 || ll==right)//如果是第一格或者左侧对上这一格的右侧，就可以往下搜了 dfs(r,num+1,up*3+xx,down*3+yy,rr); } } int ncase,t; void init(){ cin>>ncase;a['F']=0,a['C']=1,a['R']=2; s[0]=1; for(int i=1;i<=12;i++)s[i]=s[i-1]*3;//使用三进制 flag=0; memset(dp,0,sizeof dp); } int main(){ init(); for(int t=1;t<=ncase;t++){ cin>>n>>m; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>mp[i][j]; for(int i=0;i<n;i++){//利用滚动数组，dp[flag][s]表示第i行状态s下的方案数 tag=1;flag^=1; memset(dp[flag],0,sizeof dp[flag]); dfs(i,0,0,0,-1); } sum=0; for(int i=0;i<s[m];i++)//求和 sum+=dp[flag][i],sum%=mod; printf("Case %d: %lld ",t,sum); } }