Description

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.

Input

Output

Sample Input

2 31 1 10 1 0
Sample Output
9
Hint
Number the squares as follows:
1 2 3  4  There are four ways to plant only on one squares (1, 2, 3, or 4), three ways to plant on two squares (13, 14, or 34), 1 way to plant on three squares (134), and one way to plant on no squares. 4+3+1+1=9.
題目大意：農(nóng)夫有一塊地，被劃分為m行n列大小相等的格子，其中一些格子是可以放牧的（用1標(biāo)記），農(nóng)夫可以在這些格子里放牛，其他格子則不能放牛（用0標(biāo)記），并且要求不可以使相鄰格子都有牛。現(xiàn)在輸入數(shù)據(jù)給出這塊地的大小及可否放牧的情況，求該農(nóng)夫有多少種放牧方案可以選擇（注意：任何格子都不放也是一種選擇，不要忘記考慮！
解題思路：以樣例數(shù)據(jù)第一行為例，三個(gè)格子都可以放牧，即每個(gè)格子都可以選擇放，或不放。再考慮附加條件“相鄰格子不可同時(shí)放牧”，那么我們可以列出單看第一行時(shí)的所有可行狀態(tài)如下（1代表放牧，0代表不放牧）
編號(hào)
狀態(tài)
1
0 0 0 
2
0 0 1
3
0 1 0
4
1 0 0
5
1 0 1
（表1）
由此，可將表中的狀態(tài)看作二進(jìn)制表示，那么，只需將每種狀態(tài)轉(zhuǎn)化為相應(yīng)的十進(jìn)制數(shù)，即可只用一個(gè)數(shù)字，就能表示某一種狀態(tài)，如下表：
編號(hào)
二進(jìn)制
十進(jìn)制
1
0 0 0
0
2
0 0 1
1
3
0 1 0
2
4
1 0 0
4
5
1 0 1
5
（表2）這種用一個(gè)數(shù)來(lái)表示一組數(shù)，以降低表示狀態(tài)所需的維數(shù)的解題手段，就叫做狀態(tài)壓縮。
至此我們看到，在只考慮第一行的時(shí)候，有5種可行的放牧方案，但這只是我們要做的第一步。接下來(lái)要將第二行納入考慮：
首先思考：納入第二行后，會(huì)對(duì)當(dāng)前問(wèn)題造成什么樣的影響？
答案還是那句話：“相鄰格子不可同時(shí)放牧”！
也就是說(shuō)，不止左右相鄰不可以，上下之間也不能存在相鄰的情況。
首先觀察第二行，只有中間的格子可以放牧，那么我們的狀態(tài)表格就可以相對(duì)簡(jiǎn)單些了～如下：
編號(hào)
二進(jìn)制
十進(jìn)制
1
0 0 0
0
2
0 1 0
2
（表3）只有兩種可行狀態(tài)，那么我們不妨一個(gè)一個(gè)來(lái)考察： 
1、當(dāng)?shù)诙械臓顟B(tài)為編號(hào)1時(shí)，第二行的三個(gè)格子都沒(méi)有放牧，那么就不會(huì)與第一行的任何情況有沖突，第一行的5種方案都可行，即：第二行選用編號(hào)1的狀態(tài)時(shí)，結(jié)合第一行，可得到5種可行的放牧方案；
2、當(dāng)?shù)诙械臓顟B(tài)為編號(hào)2時(shí)，第二行中間的格子已經(jīng)放牧了，那么第一行中間的格子就不可以放牧。看表2，發(fā)現(xiàn)其中第3種狀態(tài)與當(dāng)前第二行沖突，那么第一行只有4種方案是可行的，即：第二行選用編號(hào)2的狀態(tài)時(shí)，結(jié)合第一行，可得到4種可行的放牧方案；
那么，在樣例數(shù)據(jù)給出的情況下，我們的最終答案即為5+4=9；
通過(guò)對(duì)樣例數(shù)據(jù)的分析即可以發(fā)現(xiàn)不同狀態(tài)之間的關(guān)系：
以dp[i][state(j)]來(lái)表示對(duì)于前i行，第i行采用第j種狀態(tài)時(shí)可以得到的可行方案總數(shù)！
例如：回頭看樣例數(shù)據(jù)，dp[2][1]即代表第二行使用第2中狀態(tài)（0 1 0）時(shí)可得的方案數(shù)，即為4；
那么，可得出狀態(tài)轉(zhuǎn)移方程為：
dp[i][state(j)]=dp[i-1][state(k1)]+dp[i-1][state(k2)]+......+dp[i-1][state(kn)](kn即為上一行可行狀態(tài)的編號(hào)，上一行共有n種可行狀態(tài)）
最終ans=dp[m][state(k1)]+dp[m][state(k2)]+......+dp[m][state(kn)]; (kn即為最后一行（第m行）可行狀態(tài)的編號(hào)）
#include <cstdio>#include <cstring>using namespace std;#define mod 100000000int M,N,top = 0;//top表示每行最多的狀態(tài)數(shù)int state[600],num[110];//state存放每行所有的可行狀態(tài)（即沒(méi)有相鄰的狀態(tài)int dp[20][600];//dp[i][j]:對(duì)于前i行數(shù)據(jù)，每行有前j種可能狀態(tài)時(shí)的解int cur[20];//cur[i]表示的是第i行整行的情況inline bool ok(int x) 	//判斷狀態(tài)x是否可行{    if(x&x<<1)	return false;//若存在相鄰兩個(gè)格子都為1，則該狀態(tài)不可行    return true;}void init() 			//遍歷所有可能的狀態(tài){    top = 0;    int total = 1 << N; //遍歷狀態(tài)的上界    for(int i = 0; i < total; ++i)    {        if(ok(i))state[++top] = i;    }}inline bool fit(int x,int k)  //判斷狀態(tài)x 與第k行的實(shí)際狀態(tài)的逆的二進(jìn)制中是否有‘重合’的1{    if(x&cur[k])return false; //若有重合，（即x不符合要求）    return true;  //若沒(méi)有，則可行}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 num;            for(int j = 1; j <= N; ++j)   //輸入時(shí)就要按位來(lái)存儲(chǔ)，cur[i]表示的是第i行整行的情況，每次改變?cè)摂?shù)字的二進(jìn)制表示的一位            {                scanf("%d",&num);  //表示第i行第j列的情況（0或1）                if(num == 0)//若該格為0                {                    cur[i] +=(1<<(N-j)); //則將該位置為1（注意要以相反方式存儲(chǔ)，即1表示不可放牧                }            }        }        for(int i = 1; i <= top; i++)        {            if(fit(state[i],1))   //判斷所有可能狀態(tài)與第一行的實(shí)際狀態(tài)的逆是否有重合            {                dp[1][i] = 1;  //若第1行的狀態(tài)與第i種可行狀態(tài)吻合，則dp[1][i]記為1            }        }        /*        狀態(tài)轉(zhuǎn)移過(guò)程中，dp[i][k] =Sigma dp[i-1][j] （j為符合條件的所有狀態(tài)）        */        for(int i = 2; i <= M; ++i)   //i索引第2行到第M行        {            for(int k = 1; k <= top; ++k)  //該循環(huán)針對(duì)所有可能的狀態(tài)，找出一組與第i行相符的state[k]            {                if(!fit(state[k],i))continue; //判斷是否符合第i行實(shí)際情況                for(int j = 1; j <= top ; ++j) //找到state[k]后，再找一組與第i-1行符合，且與第i行（state[])不沖突的狀態(tài)state[j]                {                    if(!fit(state[j],i-1))continue;  //判斷是否符合第i-1行實(shí)際情況                    if(state[k]&state[j])continue;  //判斷是否與第i行沖突                    dp[i][k] = (dp[i][k] +dp[i-1][j])%mod;  //若以上皆可通過(guò)，則將'j'累加到‘k'上                }            }        }        int ans = 0;        for(int i = 1; i <= top; ++i)  //累加最后一行所有可能狀態(tài)的值，即得最終結(jié)果！！！泥馬寫(xiě)注釋累死我了終于寫(xiě)完了！        {            ans = (ans + dp[M][i])%mod;        }        PRintf("%d/n",ans);    }}轉(zhuǎn)自：點(diǎn)擊打開(kāi)鏈接各種位運(yùn)算：戳這里