这题对我真的非常难。实在做不出来，就去百度了，搜到了一种状压DP的方法。这是第一种
详细见凝视
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <string>
#include <iostream>
#include <cstdlib>
#include <list>
#include <set>
#include <queue>
#include <stack>
using namespace std;
#define mod 100000000
int n,m,map[15];//map数组用来存图
int cnt[10000],dp[15][10000];//cnt存当一层每处都能够放置东西时，全部满足题意的情况
int k;
bool ok(int x)//推断某种方法是否满足题意
{
if(x&(x<<1)) return false; //假设某点左右有点的话，返回false
return true;
}
void find()
{
for(int i=0;i<(1<<m);i++) //从0開始到1<<m。找到全部单层满足题意的情况
{
if(ok(i)) cnt[k++]=i;
}
}
int main()
{
int i,j,temp;
while(cin>>n>>m)
{
memset(map,0,sizeof(map));
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
cin>>temp;
if(!temp) map[i]|=1<<j;//此处存图应该注意。与题中相反的是，当某点不能够放置东西时，应该置为1。便于兴许操作
}
}
k=0;
memset(dp,0,sizeof(dp));
memset(cnt,0,sizeof(cnt));
find();
for(i=0;i<k;i++)//初始化第一行
{
if(!(map[0]&cnt[i]))
{
dp[0][i]=1;
}
}
for(i=1;i<n;i++)//从第二行開始进行递推
{
for(j=0;j<k;j++)
{
if(map[i-1]&cnt[j]) continue;
for(int p=0;p<k;p++)
{
if((map[i]&cnt[p])||(cnt[p]&cnt[j])) continue;
dp[i][p]=(dp[i][p]+dp[i-1][j])%mod;
}
}
}
int ans=0;
for(i=0;i<k;i++)//算出全部的情况
{
ans=(ans+dp[n-1][i])%mod;
}
cout<<ans<<endl;
}
return 0;
}
另外一种方法是状态压缩+记忆化搜索。这是我从瓜神那看来的记忆化搜索，然后依据我从上个代码中学来的东西改进了下，QAQ。要学的东西还有非常多。慢慢来吧
主要思路是从第一层開始向下搜索，假设搜到符合条件的就继续向下搜索，直到最后一行为止
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 20
#define mod 100000000
int map[maxn];
int dp[maxn][1<<12];
int n,m;
bool ok(int i,int state,int cur)
{
if(map[cur]&i) return false;//推断是否会把东西放在不能放东西的地方
if(i&(i<<1)) return false;//推断东西的左右是否放置了东西
if(cur)
{
if(state&i) return false;//推断东西的上边是否放置了东西
}
return true;
}
int dfs(int cur,int state)
{
if(cur==n) return dp[cur][state]=1;
if(dp[cur][state]!=-1) return dp[cur][state];//记忆化搜索
int ret=0;
for(int i=0;i<(1<<m);i++)
{
if(ok(i,state,cur))//推断下一条边能否够增加
{
ret+=dfs(cur+1,i);
ret%=mod;
}
}
return dp[cur][state]=ret%mod;
}
int main()
{
int t;
cin>>n>>m;
memset(map,0,sizeof(map));
memset(dp,-1,sizeof(dp));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>t;
if(!t) map[i]|=1<<j;
}
}
cout<<dfs(0,0)<<endl;
return 0;
}