poj3254:http://poj.org/problem?id=3254
题意：给以n*m的方格，方格中有1或者0，在1的地方可以放置一个物品，但是在物品的上下左右不能有不物品，也可以不放，问你最够有多少种放法。
题解：很简单的状态dp。这里先统计数最多能放多少个，然后和棋盘放k的kind那题一样，最后的结果就是第n行各种状态以及放置0到最多的种类之和。其实，这一题，个数那一维是完全可以删除的，只要2维就可以了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char mp[][];
int dp[][][];
const int N=(<<);
int n,m;
int total;
int s[N],ct[N],num;
int state[];
bool isok(int x){
if(x&(x<<))return false;
return true;
}
int counts(int x){
int ans=;
while(x){
ans+=(x&);
x/=;
}
return ans;
}
void solve(){
num=;
for(int i=;i<(<<m);i++){
if(isok(i)){
++num;
s[num]=i;
ct[num]=counts(i);
}
}
}
void sum(){
total=;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(mp[i][j]=='')
total++;
}
} }
void input(){
int cs=,ans=;
for(int i=;i<=n;i++){
cs=,ans=;
for(int j=m;j>=;j--){
if(mp[i][j]==''){
ans+=cs;
}
cs*=;
}
state[i]=ans;
}
}
int main(){
while(~scanf("%d%d",&n,&m)){
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++){
for(int j=;j<=m;j++)
cin>>mp[i][j];
}
solve();
sum();
input();
for(int i=;i<=num;i++){
if(state[]&s[i])continue;
dp[][i][]=;
}
for(int i=;i<=n;i++){
for(int j=;j<=num;j++){
if(state[i]&s[j])continue;
for(int k=ct[j];k<=total;k++){
for(int g=;g<=num;g++){
if(state[i-]&s[g])continue;
if(s[j]&s[g])continue;
dp[i][j][]+=dp[i-][g][];
dp[i][j][]%=;
}
}
} }
long long as=;
for(int i=;i<=num;i++){
for(int j=;j<=total;j++){
as+=dp[n][i][];
as%=;
}
}
printf("%I64d\n",as%);
}
}