比赛 2024暑假C班集训A 评测结果 RRRRRRRRRR
题目名称 轮子的旋转 最终得分 0
用户昵称 djyqjy 运行时间 0.041 s
代码语言 C++ 内存使用 4.21 MiB
提交时间 2024-07-10 11:51:07
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=15,M=4500;
const long long MOD=100000000;
int m,n;
int mapp[N][N];
long long dp[N][M];
long long ans;
int main()
{
    freopen("cowfood.in","r",stdin);
    freopen("cowfood.out","w",stdout);
    memset(dp,-1,sizeof(dp));
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&mapp[i][j]);
        }
    }
    for(int i=0;i<pow(2,n);i++)
    {
        bool flag=1;
        for(int j=1;j<=n;j++)
        {
            if(j!=n&&((i>>(j-1))&1)&&((i>>j)&1))
            {
                flag=0;
                break;
            }
            if(mapp[1][j]==0&&((i>>(j-1))&1))
            {
                flag=0;
                break;
            }
        }
        if(flag) dp[1][i]=1;
    }
    for(int i=1;i<m;i++)
    {
        for(int j=0;j<pow(2,n);j++)
        {
            if(dp[i][j]==-1) continue;
            for(int k=0;k<pow(2,n);k++)
            {
                if(j&k) continue;
                bool flag=1;
                for(int a=1;a<=n;a++)
                {
                    if(a!=n&&((k>>(a-1))&1)&&((k>>a)&1))
                    {
                        flag=0;
                        break;
                    }
                    if(mapp[i+1][a]==0&&((k>>(a-1))&1))
                    {
                        flag=0;
                        break;
                    }
                }
                if(flag&&dp[i+1][k]==-1) dp[i+1][k]=0;
                if(flag) dp[i+1][k]=(dp[i+1][k]+dp[i][j])%MOD;
                if(flag&&i==m-1) ans=(ans+dp[i][j])%MOD;
            }
        }
    }
    printf("%lld",ans);
    return 0;
}