Description

题意：在n*m(1<=N, M<=11 )的矩阵中，有些格子有树，没有树的格子不能到达，找一条或多条回路，吃完所有的树，求有多少种方法。

Solution

插头DP入门题，\(dp[i][j][k]\)表示\(G_{i,j}\)且轮廓线状态为\(k\)时的方案数

转移有6种，

Code

#include 
    
     #include 
     
      #include 
      
       #define N 14#define ll long longusing namespace std;int T,n,m,g[N][N];ll dp[N][N][1<
       
        '9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}int main(){    T=read();    for(int ca=1;ca<=T;++ca){        memset(g,0,sizeof(g));        memset(dp,0,sizeof(dp));        n=read(),m=read();        for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)g[i][j]=read();                dp[0][m][0]=1;        for(int i=1;i<=n;++i){            for(int j=0;j<(1<