Luogu1879 [USACO06NOV]Corn Fields G

tony102

2020 年 12 月 12 日

1937 次浏览

暂无评论

496字数

题解

[Link](https://www.luogu.com.cn/problem/P1879)

## Sol

很经典的题目还是要写个题解（主要是觉得自己最近越来越懒决定强迫自己更更博

这个题目的要求就是你选的格子如果是$1$，那么它四周的各自不能为$1$。也就是说四个方向上相邻的格子不能有相邻的$1$

注意到$n,m \leq 12$的数据范围很小，考虑状压。

可以设$f[i][j]$表示第$i$行的选$1$的格子状态为$j$时，满足要求的方案数。那么我们可以预处理出所有合法的方案，记作$s[i]$，那么```s[i] = (!(i & (i << 1))) && (!(i & (i >> 1)))```

那么我们直接枚举第$i$行的状态为$j$时，第$i-1$行的状态为$k$，满足此时$j\&k$且$j$状态选取的$1$格子在给定的网格图上有$1$且保证$j$状态为合法态。

最后直接按照加法原理统计第$n$行所有合法答案即可

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

const int SIZE = (1 << 12) + 5;
const int mod = 1e8;

int n, m;
int s[SIZE], g[SIZE], f[SIZE][SIZE], a[SIZE][SIZE];

namespace ae86 {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (!isdigit(c))b ^= c == '-', c = fetch();
		while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
}
using ae86::read;

signed main() {
	// freopen("code.in", "r", stdin);
	// freopen("code.out", "w", stdout);
	n = read(), m = read();
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= m; ++ j) {
			a[i][j] = read();
			g[i] = (g[i] << 1) + a[i][j];
		}
	}
	int r = (1 << m); f[0][0] = 1;
	for (int i = 0; i < r; ++ i) {
		s[i] = (!(i & (i << 1))) && (!(i & (i >> 1)));
	}
	for (int i = 1; i <= n; ++ i) {
		for (int j = 0; j < r; ++ j) {
			if (s[j] && (j & g[i]) == j) {
				for (int k = 0; k < r; ++ k) {
					if (!(k & j)) f[i][j] = (f[i][j] + f[i - 1][k]) % mod;
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < r; ++ i) {
		ans = (ans + f[n][i]) % mod;
	}
	printf("%lld\n", ans % mod);
	return 0;
}
```

最后修改：2021 年 09 月 04 日