补题链接:Here
经典状压DP问题
坑点,注意多组输入。。。
const int N = 16, mod = 100000000;
int f[N][1 << N];
int a[N];
void solve() {
int n, m;
while (cin >> n >> m) {
memset(f, 0, sizeof(f)), memset(a, 0, sizeof(a));
for (int i = 1; i <= n; ++i) {
int t = 0;
for (int j = 0, x; j < m; ++j) {
cin >> x;
if (x)t += (1 << j);
}
a[i] = t;//记录每行的状态
}
f[0][0] = 1;
for (int i = 1; i <= n; i++) { ///枚举每一行
for (int j = 0; j < (1 << m); j++) { ///枚举当前行所有情况
if ((j & a[i]) != j) ///有些位置不能站
continue;
if (j & (j << 1)) ///相邻不能有1
continue;
for (int k = 0; k < (1 << m); k++) { ///枚举上一行所有情况
if (!(j & k)) { ///当前行和上一行没有相邻的英雄
f[i][j] = (f[i][j] + f[i - 1][k]) % mod;
}
}
}
}
int ans = 0;
for (int i = 0; i < (1 << m); ++i) ans += f[n][i], ans %= mod;
cout << ans << "\n";
}
}