題目大意：給定一個n*m的矩陣，矩陣上有數值有0和1，1表示這個坐標可以放置東西，要求放置的東西不能相鄰，問有多少種放法？n,m<=12
解題思路：簡單狀態DP，dp[i][j]表示第i行放置東西的狀態為j的方法數，j是一個若干個二進制數的和，表示哪些列放置了東西。
然後進行遞推，dp[i][j] = sum(dp[i-1][k]) (k狀態和j狀態不沖突)
測試數據：
2 3
1 1 1
0 1 0
代碼：
[cpp]
#include <stdio.h>
#include <string.h>
#define MIN 15
#define MAX (1<<13)
#define MOD 100000000
int dp[MIN][MAX],n,m;
int ans,map[MIN][MIN],state[MIN];
int CheckAdj(int st) {
return !(st & (st>>1));
}
int CheckPre(int cur,int pre) {
return !(cur & pre);
}
void State_Dp() {
int i,j,k,st = (1<<m);
//初始化
for (i = 0; i < st; ++i)
if (i == (i & state[0]) && CheckAdj(i))
dp[0][i] = 1;//printf("0 %d %d\n",i,dp[0][i]);
//狀態轉移 dp[i][j] = sum(dp[i-1][k]) (!(j&k)即j狀態和k狀態不沖突)
for (i = 1; i < n; ++i)
for (j = 0; j < st; ++j)
if (j == (j & state[i]) && CheckAdj(j)) {
int sum = 0;
for (k = 0; k < st; ++k)
if (CheckPre(j,k)) sum = (sum + dp[i-1][k]) % MOD;
dp[i][j] = sum;//printf("i=%d j=%d %d\n",i,j,dp[i][j]);
}
}
int main()
{
int i,j,k;
scanf("%d%d",&n,&m);
for (i = 0; i < n; ++i)
for (j = 0; j < m; ++j) {
scanf("%d",&map[i][j]);
if (map[i][j] == 1)
state[i] |= (1<<j);
}
State_Dp();
for (ans = i = 0; i < (1<<m); ++i)
ans = (ans + dp[n-1][i]) % MOD;
printf("%d\n",ans);
}
