题目大意：要求你将全部非障碍格子都走一遍，形成回路（能够多回路），问有多少种方法

解题思路：

參考基于连通性状态压缩的动态规划问题 - 陈丹琦

下面为代码

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

#define N 12

#define S (1 << 12)

int n, m;

long long dp[N][N][S];

int cas = 1;

void solve() {

    scanf("%d%d", &n, &m);

    memset(dp, 0, sizeof(dp));

    int num;

    dp[0][0][0] = 1;

    for(int i = 0; i < n; i++) {

        for(int j = 0; j < m; j++) {

            scanf("%d", &num);

            for(int k = 0; k < (1 << (m + 1)); k++) {

                int left = k & (1 << m);

                int up = k & (1 << j);

                int l = (1 << m);

                int u = (1 << j);

                //假设是障碍

                if(num == 0) {

                    if(!left && !up)

                        dp[i][j + 1][k] += dp[i][j][k];

                    continue;

                }

                //假设有左边那一个有右插头。上面那一个有下插头,那么当前格子仅仅能是L的镜像了，也就是左上型

                if(left && up) {

                    dp[i][j + 1][k - l - u] += dp[i][j][k];

                }//假设仅仅有左边那个有左插头。上面那个没有下插头，那么当前的可能有右插头，或者左下型插头

                else if(left) {

                    dp[i][j + 1][k] += dp[i][j][k];

                    dp[i][j + 1][k - l + u] += dp[i][j][k];

                }//假设仅仅有上面那个有下插头。左边那个没有右插头,那么当前的可能有下插头，或者上右型插头

                else if(up) {//

                    dp[i][j + 1][k] += dp[i][j][k];

                    dp[i][j + 1][k - u + l] += dp[i][j][k];

                }//假设上面没有下插头，左边没有右插头。那么仅仅能是下右型插头了

                else {

                    dp[i][j + 1][k + l + u] += dp[i][j][k];

                }

            }

        }

        for(int j = 0; j < (1 << m); j++)

            dp[i + 1][0][j] = dp[i][m][j];

    }

    printf("Case %d: There are %I64d ways to eat the trees.\n", cas++, dp[n][0][0]);

}

int main() {

    int test;

    scanf("%d", &test);

    while(test--) {

        solve();

    }

    return 0;

}