网站模板如何修改域名,工程合同承包协议书完整版,淘宝上可以做网站吗,企业管理咨询是做什么农夫约翰的土地由 MN 个小方格组成#xff0c;现在他要在土地里种植玉米。 非常遗憾#xff0c;部分土地是不育的#xff0c;无法种植。 而且#xff0c;相邻的土地不能同时种植玉米#xff0c;也就是说种植玉米的所有方格之间都不会有公共边缘。 现在给定土地的大小…农夫约翰的土地由 M×N 个小方格组成现在他要在土地里种植玉米。 非常遗憾部分土地是不育的无法种植。 而且相邻的土地不能同时种植玉米也就是说种植玉米的所有方格之间都不会有公共边缘。 现在给定土地的大小请你求出共有多少种种植方法。 土地上什么都不种也算一种方法。
输入 第 1 行包含两个整数 M 和 N (1 ≤ M,N ≤ 12)。 第 2..M1 行每行包含 N 个整数 0 或 1用来描述整个土地的状况1 表示该块土地肥沃0 表示该块土地不育。
输出 输出总种植方法对 1e8 取模后的值。
Input 2 3 1 1 1 0 1 0
Output 9
解析 板子题不过对于每一行有不能种植的地方在枚举合法状态的时候需要特判一下将不能种植的地方种植的状态要跳过这样的状态是不合法的。
#include bits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pairint,int PII;
const double PIacos(-1.0);
const int N14,M112,mod1e8;
int n,m;
int g[N];
vector int state;
vector int head[M];
int f[N][M];
bool check (int x) //一行中相邻两项不能同时为1也就是不能同时种植
{for (int i0;im;i){if ((xi1)(xi11)) return 0;}return 1;
}
void solve()
{cinnm;for (int i1;in;i)for (int j0;jm;j){int x;cinx;g[i] !x*(1j); //1代表该位置不能被种植0代表该位置能被种植}for (int i0;i1m;i) //预处理一行中所有合法的状态一行的相邻两项不能同时为1就是合法状态{if (check(i)) state.push_back(i);}for (int i0;istate.size();i) //预处理两行中所有合法的状态两行的同一列不能同时为1就是合法状态for (int j0;jstate.size();j){int astate[i],bstate[j];if ((ab)0) head[a].push_back(b);}f[0][0]1;for (int i1;in1;i)for (auto a:state)for (auto b:head[a]){if (g[i]a) continue; //此处运算同1则1说明此时合法状态 a 和g[i]不能种植的位置 都存在1,与题意不符跳过f[i][a](f[i][a]f[i-1][b])%mod;}coutf[n1][0]endl;
}
signed main()
{ios;int T1;//cinT;while (T--) solve();return 0;
}
