题目描述

$5 \times 5$ 的 $01$ 矩阵，求不能同一行或者同一列连续 $3$ 个 $1$ 的矩阵个数

预处理单行合法状态，逐行枚举

C++ 代码

#include<cstdio>
#include<vector>

using namespace std;

int n, m, res;
vector<int> v;      //  单行合法的状态

int a[5];
void dfs(int r)
{
    if(r >= n)
    {
        res ++;
        return;
    }

    for(int i : v)
    {
        if(r >= 2)
        {
            bool flag = true;
            for(int j = 0; j < m; j ++)
                if(a[r - 2] >> j & 1 and a[r - 1] >> j & 1 and i >> j & 1)
                {
                    flag = false;
                    break;
                }
            if(!flag)  continue;
        }
        a[r] = i;
        dfs(r + 1);
    }
}

int main()
{
    scanf("%d%d", &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 and i >> j + 1 & 1 and i >> j + 2 & 1)
            {
                flag = false;
                break;
            }
        if(flag)  v.push_back(i);
    }
    dfs(0);
    printf("%d\n", res);
    return 0;
}