题目链接：http://poj.org/problem?id=3254
给你n*m的菜地，其中1是可以种菜的，而菜与菜之间不能相邻。问有多少种情况。
状压dp入门题，将可以种菜的状态用一个数的二进制表示。第i行的状态只与上一行有关。
此blog讲的很清楚：传送门
//#pragma comment(linker, "/STACK:102400000, 102400000")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
int dp[][ << ], mod = 1e8, state[]; int main()
{
int n, m;
while(~scanf("%d %d", &n, &m)) {
int num;
for(int i = ; i <= n; ++i) {
state[i] = ;
for(int j = ; j <= m; ++j) {
scanf("%d", &num);
state[i] = (state[i] << ) + num; // 初始可行状态
}
}
memset(dp, , sizeof(dp));
for(int i = ; i < ( << m); ++i) { // 初始化第一行
if((i & (i << )) == && (i & state[]) == i) { // 相邻没菜 且在可行状态中
dp[][i] = ;
}
}
for(int i = ; i <= n; ++i) {
for(int j = ; j < ( << m); ++j) {
if((j & (j << )) == && (j & state[i]) == j) {
for(int k = ; k < ( << m); ++k) {
if((j & k) == && (k & state[i - ]) == k) { //上下行菜不相邻 且上行可行
dp[i][j] = (dp[i][j] + dp[i - ][k]) % mod;
}
}
}
}
}
int ans = ;
for(int i = ; i < ( << m); ++i) {
ans = (dp[n][i] + ans) % mod;
}
printf("%d\n", ans);
}
return ;
}