题目大意：给定一个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
#include
#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<
//初始化
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<
State_Dp();
for (ans = i = 0; i < (1<
printf("%d\n",ans);
}
作者：woshi250hua