算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
// 思路:f(i, j)表示i-1列状态已经确定,此时第i列的状态时j的所有方案数
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 12, M = 1 << N;
// 使用二进制保存每一列的状态
int n, m;
LL f[N][M]; // 注意方案数可能会爆int,需要LL来保存,最多有1 << N种状态
vector<int> state[M]; // state[i]表示第i列的上一列,也就是i-1列的合法状态
bool st[M]; // 表示所有状态中的合法状态
int main()
{
while (scanf("%d%d", &n, &m), n || m)
{
// 1、首先找出所有单列的合法状态,需要满足没有偶数个0的条件
for (int i = 0; i < (1 << n); i ++ )
{
int cnt = 0;
bool is_valid = true;
for (int j = 0; j < n; j ++ )
{
if (i >> j & 1)
{
if (cnt & 1)
{
is_valid = false;
break;
}
else cnt = 0;
}
else
{
cnt ++ ;
}
}
// 处理最后剩下的几个0
if (cnt & 1) is_valid = false;
st[i] = is_valid;
}
// 2、然后找到i-1列的合法状态k
for (int j = 0; j < (1 << n); j ++ )
{
state[j].clear(); // 清空上一次状态
for (int k = 0; k < (1 << n); k ++ )
{
// 当i列状态j和i-1列状态k之间没有冲突,并且相或(两列的1合并),此时i列也合理的i-1列状态k
if ((j & k) == 0 && st[j | k]) state[j].push_back(k);
}
}
memset(f, 0, sizeof f);
f[0][0] = 1; // 表示第-1列伸出到第0列状态为0,只有全是竖着摆一种情况
for (int i = 1; i <= m; i ++ ) // m列
for (int j = 0; j < (1 << n); j ++ ) // 1 << n种状态
for (auto k : state[j]) // 合法的i-1列状态
f[i][j] += f[i - 1][k]; // i列状态j的方案数等于i-1列状态k的方案数
printf("%lld\n", f[m][0]); // 最终输出m列状态为0的结果
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla