一、題目大意

我們要在N * M的田地里種植玉米，有如下限制條件：

1、對已經(jīng)種植了玉米的位置，它的四個相鄰位置都無法繼續(xù)種植玉米。

2、題目中有說一些塊無論如何，都無法種植玉米。

求所有種植玉米的方案數(shù)（不種植也是一種方案）

二、解題思路

不難看出本題目是鋪磚問題，我們可以先寫一個基于遞歸解決的Domo。

可以定義數(shù)組color[i][j]代表該位置是否起初就無法種植

并定義數(shù)組used[i][j]代表該位置是否已經(jīng)被旁邊的塊覆蓋，無法種植。

對于i j 位置，判斷它如果不能種植，就直接計算下一個位置。

如果可以種植，則分別嘗試種植和不種植兩種情況，將計算出的方案數(shù)求和。

寫出遞歸代碼如下：

int rec(int i, int j)
{if (i == n){return 1;}if (j == m){return rec(i + 1, 0);}if (color[i][j] || used[i][j]){return rec(i, j + 1);}int res = 0;bool rt = false, dn = false;if (j + 1 < m){rt = used[i][j + 1];}if (i + 1 < n){dn = used[i + 1][j];}res += rec(i, j + 1);used[i][j] = true;if (j + 1 < m){used[i][j + 1] = true;}if (i + 1 < n){used[i + 1][j] = true;}res += rec(i, j + 1);used[i][j] = false;if (j + 1 < m){used[i][j + 1] = rt;}if (i + 1 < n){used[i + 1][j] = dn;}return res;
}

這個遞歸代碼一定是超時的，那么接下來考慮如何把它轉(zhuǎn)成DP，我們發(fā)現(xiàn)這個遞歸算法是從左上一直算到右下，那么對于i j位置，其實只需要記錄 (row==i+1&&col<j)和(row==i&&col>=j)的一排元素是否可以種植玉米即可，如下圖所示。

所以不難看出，對于同一個位置，且這一排元素確定時，算出的方案數(shù)也是確定的，那么我們就可以從右下角開始，一點點邊計算邊循環(huán)到左上角。

在這個計算的過程中，和遞歸一樣，只需要考慮兩點。

第一，如果i j位置不能種植玉米，則加上i?j位置不種植時的下一塊的值 crt[ S 去掉第 j 塊?]。

第二，如果i j位置能夠種植玉米，則依次加上i j位置種植和不種植情況時下一塊的值，dp[S]?和 crt[S 加上第 j 塊 和 第 j+1 塊]（如果j+1==m，則不用添加第j+1塊）。

初始化時，考慮到最后一塊的情況，如果它能夠種植，則是2，如果不能則是1，那么就可以初始化DP數(shù)組上一行的所有元素為1。

可以使用滑動數(shù)組求解，循環(huán)計算每一塊，之后本次的當前行作為下次計算的上一行即可。

最終輸出的答案為上一行的第一個位置。

三、代碼

#include <iostream>
using namespace std;
const int MAX_M = 12;
const int MAX_N = 12;
int dp[2][1 << MAX_M];
bool color[MAX_N][MAX_M];
int n, m;
void solve()
{int *crt = dp[0], *next = dp[1];fill(crt, crt + (1 << MAX_M), 1);for (int i = n - 1; i >= 0; i--){for (int j = m - 1; j >= 0; j--){for (int used = 0; used < (1 << m); used++){if (color[i][j] || (used >> j & 1)){next[used] = crt[used & ~(1 << j)];}else{int res = crt[used];if (j + 1 < m){res += crt[used | (1 << (j + 1)) | (1 << j)];}else{res += crt[used | (1 << j)];}next[used] = res % 100000000;}}swap(next, crt);}}printf("%d\n", crt[0]);
}
int main()
{scanf("%d%d", &n, &m);int num;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){scanf("%d", &num);color[i][j] = num == 0;}}solve();return 0;
}

四、相關(guān)文獻

《挑戰(zhàn)程序設(shè)計競賽（第二版）》P196-P198 鋪磚問題