牧场种植方案数问题题解

一、题目分析

农夫约翰需在M×N牧场中选择肥沃地块种植玉米，要求：

• 贫瘠地块（0）不可种植；
• 种植地块不能相邻（上下左右相邻）；
• 计算所有可能的种植方案数（含不种植），结果对10⁸取模。

二、算法思路

采用状态压缩动态规划求解：

1. 状态表示：用二进制数表示每行种植方案（如N=3时，101表示种植第1、3块地）。
2. 合法状态筛选：通过ok()函数筛选无相邻1的状态（如110因相邻1非法）。
3. 行内兼容检查：通过fit()函数排除在贫瘠地块种植的状态。
4. 行间兼容检查：相邻行状态不能有上下相邻种植（即二进制位不能同时为1）。

三、代码实现

#include <cstdio>
#include <cstring>
using namespace std;
 
#define mod 100000000
int M,N,top = 0;
// top表示每行最多的状态数

int state[600],num[110];  
// state存放每行所有无相邻1的可行状态

int dp[20][600];
// dp[i][j]：前i行中，第i行采用第j种状态的方案数
int cur[20];
// cur[i]：第i行的限制条件（二进制，1表示不可种植）

inline bool ok(int x){	// 判断状态x是否无相邻1
   if(x & (x << 1)) return false;
   return true;
}
void init(){			// 生成所有合法状态
   top = 0;
   int total = 1 << N;
   for(int i = 0; i < total; ++i){
       if(ok(i)) state[++top] = i;	
   }
}
inline bool fit(int x, int k){ // 判断状态x与第k行限制是否兼容
   if(x & cur[k]) return false; // x若在不可种植位为1则非法
   return true;  
}
 
int main(){
    while(scanf("%d%d", &M, &N) != EOF){
       init();
       memset(dp, 0, sizeof(dp));
       for(int i = 1; i <= M; ++i){
           cur[i] = 0;
           int val;
           for(int j = 1; j <= N; ++j){  
                scanf("%d", &val);  
                if(val == 0)	// 不可种植位标记为1（逆映射）
				   cur[i] += (1 << (N - j)); 
           }
       }
       // 初始化第一行合法状态
       for(int i = 1; i <= top; i++){
           if(fit(state[i], 1)){  
                dp[1][i] = 1;  
           }
       }

       // 状态转移：dp[i][k] = Σ dp[i-1][j]（j为合法前序状态）
       for(int i = 2; i <= M; ++i){  
           for(int k = 1; k <= top; ++k){ 
                if(!fit(state[k], i)) continue; 
                for(int j = 1; j <= top; ++j){ 
                   if(!fit(state[j], i-1)) continue;  
                   if(state[k] & state[j]) continue;  
                   dp[i][k] = (dp[i][k] + dp[i-1][j]) % mod;  
                }
           }
       }
       // 累加最后一行所有状态方案数
       int ans = 0;
       for(int i = 1; i <= top; ++i){ 
           ans = (ans + dp[M][i]) % mod;
       }
       printf("%d\n", ans);
   }
   return 0;
}

四、代码核心逻辑解析

1. 状态预处理：
   • init()函数生成所有无相邻1的状态（如N=3时，000、001、010、100、101等），存入state数组。
2. 行限制处理：
   • 输入时将不可种植的位置（0）转换为二进制1存入cur[i]（如输入0 1 0对应101，表示第1、3列不可种植）。
3. 动态规划初始化：
   • 第一行中，所有与cur[1]无冲突的合法状态方案数初始化为1。
4. 状态转移：
   • 对于第i行的状态k，若其与第i行限制兼容，且与第i-1行的状态j兼容（state[k] & state[j] == 0），则将j的方案数累加到k上。
5. 结果计算：
   • 最后一行所有合法状态的方案数之和即为总方案数。

五、复杂度与优化点

• 时间复杂度：O(M×top²)，其中top≤2¹²=4096（N≤12时），总复杂度约12×4096²=1.97×10⁸，可通过模运算高效计算。
• 空间复杂度：O(M×top)，数组空间占用可控。
• 核心优化：通过位运算快速判断状态合法性，避免枚举所有种植组合，大幅减少计算量。

六、样例输入输出解析

输入样例：

2 3  
1 1 1  
0 1 0  

处理过程：

1. 第一行限制cur[1]=0（全肥沃），合法状态为000、001、010、011（非法，相邻1）、100、101、110（非法）、111（非法）→ 合法状态为000、001、010、100、101。
2. 第二行限制cur[2]=101（第1、3列不可种植），合法状态需满足二进制位在1、3列不为1 → 合法状态为010。
3. 状态转移时，第一行状态与第二行状态010兼容的有000、001、100、101，对应方案数累加：
   • 000→010：合法，方案数+1；
   • 001→010：合法，方案数+1；
   • 100→010：合法，方案数+1；
   • 101→010：合法，方案数+1；
     最终总方案数为9（包含不种植的1种方案）。