网易雷火-游戏研发第五题

#include <bits/stdc++.h>

using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 2e3 + 10;
int cnt=0;
int data[2000][32];
int dp_map[15][2000][32];
ll dp[15][2000];
int w,h;
int dfs(int x,int vis[32])
{
    if(x==w)
    {
        for(int i=0;i<=30;i++)
        {
            data[cnt][i]=vis[i];
        }
        cnt++;
    }
    if(x>30)return 0;
    vis[x+2]=1;
    dfs(x+2,vis);
    vis[x+2]=0;
    vis[x+3]=1;
    dfs(x+3,vis);
    vis[x+3]=0;
    return 0;
}
int main()
{
    int ini[32];
    memset(ini,0,sizeof ini);

    cin>>w>>h;
    if(w==3||w==2)
    {
        cout<<1<<endl;
        return 0;
    }
    dfs(0,ini);
    for(int i=0;i<cnt;i++)
    {
        dp[1][i]=1;
        for(int j=0;j<31;j++)dp_map[1][i][j]=data[i][j];
    }
    for(int i=2;i<=h;i++)
    {
        for(int j=0;j<cnt;j++)
        {
            if(dp[i-1][j]==0)continue;
            for(int k=0;k<cnt;k++)
            {
                int flag=0;
                for(int p=0;p<w;p++)
                {
                    if(dp_map[i-1][j][p]==data[k][p]&&data[k][p]==1)
                    {
                        flag=1;
                        break;
                    }
                }
                if(flag==0)
                {
                    dp[i][k]+=dp[i-1][j];
                    for(int p=0;p<31;p++)
                    {
                        dp_map[i][k][p]=data[k][p];
                    }
                }
            }
        }
    }
    ll ret=0;
    for(int i=0;i<cnt;i++)
    {
        ret+=dp[h][i];
    }
    cout<<ret<<endl;
    return 0;
}