題目描述
Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can't be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.
Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.
農(nóng)場主John新買了一塊長方形的新牧場糊肤，這塊牧場被劃分成M行N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)，每一格都是一塊正方形的土地。John打算在牧場上的某幾格里種上美味的草毫捣，供他的奶牛們享用棺亭。
遺憾的是穿铆，有些土地相當(dāng)貧瘠彰触，不能用來種草都许。并且褂萧，奶牛們喜歡獨占一塊草地的感覺押桃，于是John不會選擇兩塊相鄰的土地，也就是說导犹，沒有哪兩塊草地有公共邊唱凯。
John想知道羡忘，如果不考慮草地的總塊數(shù)，那么磕昼，一共有多少種種植方案可供他選擇卷雕？（當(dāng)然，把新牧場完全荒廢也是一種方案）
輸入輸出格式
輸入格式
第一行：兩個整數(shù)M和N掰烟，用空格隔開爽蝴。
第2到第M+1行：每行包含N個用空格隔開的整數(shù)，描述了每塊土地的狀態(tài)纫骑。第i+1行描述了第i行的土地蝎亚，所有整數(shù)均為0或1，是1的話先馆，表示這塊土地足夠肥沃发框，0則表示這塊土地不適合種草。
輸出格式
一個整數(shù)煤墙，即牧場分配總方案數(shù)除以100,000,000的余數(shù)梅惯。
輸入輸出樣例
輸入樣例#1
2 3
1 1 1
0 1 0
輸出樣例#1
9
解題思路
這顯然又是一道狀態(tài)壓縮
根據(jù)題意，我們的狀態(tài)變量就設(shè)為 f [ i ] [ j ] 表示第 i 行種草的狀態(tài)為 j 時的方案數(shù)
那么很顯然仿野，我們的狀態(tài)轉(zhuǎn)移方程就是 f [ i ] [ j ] += f [ i - 1 ] [ k ] 铣减，其中 k 表示的是上一行與狀態(tài) j 不相沖突的一種狀態(tài)
但是我們需要考慮到的是，玉米田中有些位置能種草而有些位置不能脚作，那么我們就需要再預(yù)處理出來一個狀態(tài)數(shù)組 cant [ i ] 表示第 i 行能否種草的狀態(tài)葫哗，在對 f 狀態(tài)轉(zhuǎn)移地時候?qū)τ诿恳粋€狀態(tài) j 就需要判斷一下，如果說( j & cnat [ i ] ) == j 的時候就表示狀態(tài) j 符合第 i 行對能否種草的限制球涛，即可轉(zhuǎn)移
具體實現(xiàn)細(xì)節(jié)見代碼注釋
C++代碼
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=20;
const int mod=1e9;
int n,m,cnt,ans=0;
int cant[maxn];
int f[maxn][1<<13];
inline int read() {//珂朵莉版快讀~~~~
int chtholly=0,william=1;
char c=getchar();
while(c<'0' || c>'9') {
if(c=='-')william=-1;
c=getchar();
}
while(c<='9' && c>='0') {
chtholly=chtholly*10+(int)(c-'0');
c=getchar();
}
return chtholly*william;
}
inline bool check(int x) {//檢查狀態(tài)x是否滿足沒有相鄰的位置種草
return (!((x<<1)&x) && !((x>>1)&x));
}
int main() {
m=read(),n=read();
for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++) {
int x=read();
cant[i]=(cant[i]<<1)+x;//預(yù)處理cant數(shù)組
}
f[0][0]=1;
cnt=(1<<n)-1;//預(yù)處理出總共有哪些可能的狀態(tài)
for(int i=1; i<=m; i++)
for(int j=0; j<=cnt; j++)
if(check(j) && (j&cant[i])==j)
for(int k=0; k<=cnt; k++)
if(!(j&k)) f[i][j]+=f[i-1][k];
//如果兩種狀態(tài)不相沖突即可轉(zhuǎn)移
for(int i=0; i<=cnt; i++)
ans=(ans+f[m][i])%mod;
printf("%d\n",ans);
return 0;
}
