$\LARGE\color{orange}{刷题日记(算法提高课)}$

这道题 AcWing 1064. 小国王 的变式

$f[i][j]$ 的定义为：考虑前 $i$ 行，当第 $i$ 行状态为 $j$ 时的方案数

对于任意两状态 $a,\ b$ ，需要满足的条件如下：

• 任意一个状态不能有两个相邻的 1

• $a\& b == 0$

状态转移方程为：

$$ f[i][j]+=f[i-1][k],\ 其中\ j,\ k\ 均表示状态 $$

在地图的处理上，我们用一维数组 $g[i]$ 表示第 $i$ 行的二进制状态

即我们将第 $i$ 行的所有数看成二进制，将其存入 $g[i]$ 中

如果原先为 1 ，说明该地合法，因此我们应当将其设置为 0

如果原先为 0 ，说明该地不合法，我们需要将其设置为 1

之后用移位来解决

完整代码：

#include <iostream>
#include <vector>

using namespace std;

const int N = 15, M = 1 << 12, mod = 1e8;

int f[N][M];
int g[N];
int n, m;

vector<int> states;
vector<int> heads[M];

bool check(int t)
{
    for(int i = 0; i < m; i++)
        if(t >> i & 1 && t >> i + 1 & 1)
            return false;
    return true;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j < m; j++)
        {
            int t = 0;
            cin >> t;
            g[i] += !t * (1 << j);
        }

    for(int i = 0; i < 1 << m; i++)
        if(check(i))
        {
            states.push_back(i);
        }

    for(int i = 0; i < states.size(); i++)
        for(int j = 0; j < states.size(); j++)
            {
                int a = states[i], b = states[j];
                if((a & b) == 0)
                    heads[i].push_back(j);
            }

    f[0][0] = 1;//记得初始化

    for(int i = 1; i <= n + 1; i++)
        for(int j = 0; j < states.size(); j++)
            if((states[j] & g[i]) == 0)
                for(int k : heads[j])
                    f[i][j] = (f[i][j] + f[i - 1][k]) % mod;
    cout << f[n + 1][0] << endl;
    return 0;
}