#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MOD = 100000000;

int main() {
    int M, N;
    bool bbb;
    cin >> M >> N; 
    vector<vector<int>> grid(M, vector<int>(N));
    for (int i = 0; i < M; ++i) 
    for (int j = 0; j < N; ++j) cin >> grid[i][j];          
    vector<vector<int>> v(M);
    for (int i = 0; i < M; ++i) 
    for (int mask = 0; mask < (1 << N); ++mask) {
        bbb = 1;
        for (int j = 0; j < N - 1; ++j) 
        if ((mask & (1 << j)) && (mask & (1 << (j + 1)))) {
            bbb = 0;
            break;
        }          
        for (int j = 0; j < N; ++j) 
        if ((mask & (1 << j)) && grid[i][j] == 0) {
            bbb = 0;
            break;
        }           
        if (bbb) v[i].push_back(mask);           
    }   
    vector<vector<int>> dp(M, vector<int>(1 << N, 0));
    for (int mask : v[0]) dp[0][mask] = 1;  
    for (int i = 1; i < M; ++i) 
    for (int j : v[i]) 
    for (int k : v[i - 1]) 
	if ((j & k) == 0) dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;   
    int ans = 0;
    for (int mask : v[M - 1]) ans = (ans + dp[M - 1][mask]) % MOD;    
    cout << ans;  
}

代码解释 ​​输入处理​​：读取网格大小和每个格子的状态（可种植或需要休养）。 ​​预处理合法状态​​： 对于每一行，枚举所有可能的种植状态（位掩码） 检查每个状态是否合法（没有相邻种植且不在休养土地上种植） ​​动态规划初始化​​： 初始化第一行的所有合法状态的方案数为1 ​​状态转移​​： 对于每一行，检查当前行状态与上一行状态是否兼容（没有上下相邻种植） 累加兼容状态的方案数 ​​结果计算​​：将所有可能的最后一行状态的方案数相加，得到总方案数