题目链接: https://www.luogu.org/problemnew/show/P1879

具体思路: 我们可以先把所有合法的情况枚举出来,然后对第一行判断有多少种情况满足,然后对于剩下的行数,我们可以继续枚举,但是枚举的时候要注意,要判断一下和它的上面一行的各种情况会不会冲突,然后一直枚举就可以了.

注意点:位运算符的优先级比等号之类的低,所以如果要判断的话,最好放在括号里面判断.

AC代码:

#include<bits/stdc++.h>

using namespace std;

# define ll long long

const int maxn = 10000+100;

# define inf 0x3f3f3f3f

const int mod = 1e9;

int Map[maxn];

int a[maxn][maxn];

int dp[maxn][maxn];

int ok[maxn];

int main()

{

    int n,m;

    scanf("%d %d",&n,&m);

    for(int i=1; i<=n; i++)

    {

        for(int j=1; j<=m; j++)

        {

            scanf("%d",&a[i][j]);

            Map[i]=(Map[i]<<1)+a[i][j];//把初始的图存起来

        }

    }

    int maxstate=(1<<m)-1;//所有情况

    for(int i=0; i<=maxstate; i++)

    {

        if((((i<<1)&i)==0)&(((i>>1)&i)==0))//如果当前这种情况符合,只有他的左边和右边都不会有相邻的1

        {

            ok[i]=1;

        }

    }

    for(int i=0; i<=maxstate; i++)

    {

        if((ok[i]==1)&(((i&Map[1])==i)))

        {

            dp[1][i]=1;

        }

    }//枚举第一行

    for(int i=2; i<=n; i++)

    {

        for(int j=0; j<=maxstate; j++)

        {

            if(ok[j]&((j&Map[i])==j))

            {

                for(int k=0; k<=maxstate; k++)

                {

                    if(((j&k)==0)&ok[k])

                        dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;

                }

            }

        }

    }

    ll sum=0;

    for(int i=0; i<=maxstate; i++)

    {

        sum=(sum+dp[n][i])%mod;

    }

    printf("%lld\n",sum);

    return 0;

}