1.搜索

#include <iostream>
#include <vector>
using namespace std;
int n,m;
vector<int> state;//行状态
int res;
int a[6];//二维数组
void dfs(int u) //第几行
{
    if(u>=n)
    {
        res++;
        return;
    }
    for(int i=0; i<state.size(); i++) //枚举每个状态
    {
        if(u>=2)//已有行数大于3个才判断
        {
            bool flag=true;
            for(int j=0; j<m; j++)
            {
                if(a[u-2]>>j&1&&a[u-1]>>j&1&&state[i]>>j&1)
                {
                    flag=false;
                    break;
                }
            }
            if(!flag) continue;
        }
        a[u]=state[i];
        dfs(u+1);
    }
}
int main()
{
    cin>>n>>m;
    //预处理每一行，将符合要求的行状态放进数组
    for(int i=0; i<1<<m; i++)
    {
        bool flag=true;;
        for(int j=0; j<m-2; j++)
        {
            if(i>>j&1&&i>>j+1&1&&i>>j+2&1)
            {
                flag=false;
                break;
            }
        }
        if(flag)
            state.push_back(i);
    }
    dfs(0);
    cout<<res;
    //cout << "Hello world!" << endl;
    return 0;
}

2.状态压缩dp  三维

f(i,j,k)表示已经将前i列摆好，第i列状态为j，第i-1列状态为k

状态转移
f(i,j,k)=sum(f(i-1,k,u))

#include <iostream>
#include <vector>
using namespace std;
const int N=35;
vector<int> state;
int n,m;
int f[N][N][N];//已经摆好前i列，第i列状态为j，第i-1列状态为k
int main()
{
    cin>>n>>m;
    for(int i=0; i<1<<n; i++) //预处理每一列
    {
        bool flag=true;
        for(int j=0; j<n-2; j++)
        {
            if(i>>j&1&&i>>j+1&1&&i>>j+2&1)
            {
                flag=false;
                break;
            }
        }
        if(flag)
            state.push_back(i);
    }
    //前2列，初始化为1，因为不会有xxx出现
    for(int i=0; i<state.size(); i++)
    {
        for(int j=0; j<state.size(); j++)
        {
            f[1][i][j]=1;
        }
    }
    //
    for(int i=2; i<m; i++)//从第3列开始，只有此时才会出现不符合条件的情况
    {
        for(int j=0; j<state.size(); j++)//第i列
        {
            for(int k=0; k<state.size(); k++)//i-1
            {
                for(int u=0; u<state.size(); u++)//i-2
                {
                    if(!(state[j]&state[k]&state[u]))
                        f[i][j][k]+=f[i-1][k][u];
                }
            }

        }
    }
    int res=0;
    for(int i=0; i<state.size(); i++)
    {
        for(int j=0; j<state.size(); j++)
        {
            res+=f[m-1][i][j];
        }
    }
    if(m==1) cout<<state.size();
    else
    cout<<res;
    return 0;
}