➢ 题目大意：有一个m*n的矩阵,每一个方格就是一块牧场,每一个牧场适合种玉米用1表示,不适合用0表示,放牧时相邻的两块玉米地只能有一头牛,求有多少种放牧方案,一头牛也不放也是一种
➢ 数据范围: (1 ≤ m ≤ 12; 1 ≤ n ≤ 12)
➢ 输入:第一行 n,m,接下来是m*n的矩阵,1表示适合种玉米,0表示不适合
➢ 输出:一行,放牧的方案数mod 1e8.
➢ Hint:放牧1头牛有4种方案,2头牛有3种,3头牛1种,一头牛不放1种=4+3+1+1=9
输入样例
2 3
1 1 1
0 1 0
输出样例
9
这是一道很基础的状压dp，通过枚举每一行的状态和上一行的状态，有上一行推知此行即可，枚举状态时注意限制
➢ 假设f[i][j]表示前i行且第i行的状态为j时合法放牧方案数。
➢ 转移方程:f[i][j]+=f[i-1][k],((j & k)==0)