Corn Fields 玉米地種植方案數 - 狀態壓縮 DP 經典題解

問題描述

M×N (1≤M,N≤12) 的矩形草地，每格標記為肥沃(1)或貧瘠(0)。需選擇若干肥沃格種植玉米，滿足：

• 不相鄰原則：任兩選格不共用邊（上下左右四連通）
• 允許選 0 格（空方案合法）
• 求合法選擇方案數，模 100,000,000

算法核心：狀態壓縮 DP + 逐行轉移

狀態定義

• M ≤ 12 → 每行狀態用 int 位圖表示 (0~2^M-1)
• dp[row][state]：前 row 行，第 row 行狀態為 state 的方案數

合法狀態判定 (預處理)

// 條件 1：無相鄰 1 (無連續種植)
bool validState(int s) {
    return (s & (s << 1)) == 0;
}

// 條件 2：僅在肥沃地種植
bool matchLand(int s, int landRow) {
    return (s & ~landRow) == 0;  // s 的 1 必須是 landRow 的子集
}

狀態轉移方程

相鄰兩行狀態 s1 (上行)、s2 (當前行) 需滿足：

• 垂直不相鄰：(s1 & s2) == 0
• 對角線不影響（題目僅限制共邊）

dp[i][s2] = Σ dp[i-1][s1]，對所有合法 s1 求和。

完整 C++ 實現

#include <bits/stdc++.h>
using namespace std;
const int MOD = 100000000;

int M, N;
int land[13];  // 每行肥沃狀態位圖
vector validStates;  // 所有合法狀態
int dp[13][1<<12];  // dp[row][state]

int main() {
    cin >> M >> N;
    for (int i = 1; i <= M; i++) {
        int rowMask = 0;
        for (int j = 0; j < N; j++) {
            int x; cin >> x;
            if (x == 1) rowMask |= (1 << j);
        }
        land[i] = rowMask;
    }

    // 預處理所有合法狀態
    for (int s = 0; s < (1 << N); s++) {
        if (validState(s)) validStates.push_back(s);
    }

    // 初始化第 0 行（虛擬行，狀態為 0）
    dp[0][0] = 1;

    for (int i = 1; i <= M; i++) {
        for (int s2 : validStates) {
            if (!matchLand(s2, land[i])) continue;
            for (int s1 : validStates) {
                if ((s1 & s2) == 0) {  // 垂直不相鄰
                    dp[i][s2] = (dp[i][s2] + dp[i-1][s1]) % MOD;
                }
            }
        }
    }

    // 答案：最後一行所有合法狀態之和
    long long ans = 0;
    for (int s : validStates) {
        ans = (ans + dp[M][s]) % MOD;
    }
    cout << ans << endl;
    return 0;
}

複雜度分析

• 狀態數：O(2^N)，N≤12 時最大 4096
• 合法狀態：無相鄰 1 的狀態約 O(1.618^N) (斐波那契數列)，N=12 時約 377 個
• 時間：O(M * |valid|²) ≈ 12 × 377² ≈ 1.7×10⁶，極快
• 空間：O(M * 2^N) 可優化為滾動數組 O(2^N)

關鍵優化點

1. 預計算兼容列表：對每個 s2 存儲兼容的 s1 列表，避免重複位運算
2. 滾動數組：dp[2][1< 節省空間
3. 按行處理：M 為行數，N 為列數，通常令 N 為較小維度作狀態位寬