题意： 农夫有一块地，被划分为m行n列大小相等的格子，其中一些格子是可以放牧的（用1标记），农夫可以在这些格子里放牛，其他格子则不能放牛（用0标记），并且要求不可以使相邻格子都有牛。求该农夫有多少种放牧方案可以选择 。
题解： 自己也理解了很久，还没办法能够完美表达出来，所以可以参考另一篇优秀的博客。我自己的理解以及需要注意的地方，都注释在代码中了。
#include<iostream> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; inline int read() { int s = 0, w = 1; char ch = getchar(); while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();} while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar(); return s * w; } const int mod = 1e9; const int N = 600; int m, n, cnt; int cur[20]; int state[N]; int dp[20][N]; inline bool check(int x) { //检查是否含有相邻的1 if(x & x<<1) return false; return true; } inline bool fit(int x, int k) { //检查是否在不该出现1的地方出现1 if(x & cur[k]) return false; return true; } void init() { cnt = 0; memset(dp, 0, sizeof dp); memset(cur, 0, sizeof cur); int tot = 1 << n; for(int i = 0; i < tot; i++) { if(check(i)) state[++cnt] = i; } } void run() { init(); for(int i =1; i <= m; i++) { for(int j = 1; j <= n; j++) { int x = read(); if(x == 0) cur[i] += (1 << (n - j)); //存逆图，方便fit的判断 } } for(int i = 1; i <= cnt; i++) { //含等号！ if(fit(state[i], 1)) dp[1][i] = 1; } for(int i = 2; i <= m; i++) { for(int j = 1; j <= cnt; j++){ //在第i行中找出所有合法的state[j] if(!fit(state[j], i)) continue; for(int k = 1; k <= cnt; k++) { if(!fit(state[k], i - 1)) continue; //判断state[k]在第i - 1行是否合法 if(state[j] & state[k]) continue; //相邻两行含相邻1 dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod; } } } int ans = 0; for(int i = 1; i <= cnt; i++){ if(dp[m][i]) ans = (ans + dp[m][i]) % mod; } printf("%d\n", ans); } int main() { scanf("%d%d", &m, &n); run(); return 0; }