题意 给出一个 01 二维方阵 可以将里面的 0 改成1 但是 不能够 将 1 改成 0 然后这个方阵 会对应另外一个 方阵 另外一个方阵当中的元素 为 上 下 左 右 四个元素（如果存在）的和 要求另外一个方阵当中的元素 全都是偶数
求 最少的 改变次数 使得 满足这种状态
思路
刚开始 想要暴力枚举 所有状态
但是 2^225 太大了。。。
后来想想 如果 第一行确定了 那么 接下来的每一行 都是能够确定的
比如说
3 0 0 0 1 0 0 0 0 0
这组 样例 来说
假如 我第一行为
0 1 0
那么 第二行的状态
如果 原始元素 为 1 我们就要判断 是否满足 不满足 就return
如果 原始元素 为 0 我们就判断 其 左上 右上 和 上上 的元素 相加 是否为 奇数 如果是 ans++ 并且 将该元素 改为 1
然后 最后 其实是要多判断一行的
因为我们每一次判断的 其实是上一行的状态 比如说
当前的状态是 g[5][5] 那么 我们就要求
sum = g[4][4] + g[4][6] + g[3][5] 易知 这三个点 都是已经 判断并且更新过的
如果 sum 为 奇数
并且 g[5][5] = 0 的话 我们就将 g[5][5] 改为1 ans++
因为只有这样 g[4][5] 这个点 的sum 才是偶数
如果 g[5][5] = 1 那么 这种状态就是不行的 直接 return 一个不行的标记的就可
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-30; const int INF = 0x3f3f3f3f; const int maxn = 4e5 + 5; const int MOD = 1e9 + 7; int G[15][15]; int n; int Move[4][2] { 0, 0, -1, -1, -1, 1, -2, 0, }; bool ok(int x, int y) { if (x < 0 || x >= n || y < 0 || y >= n) return false; return true; } int check(int cur) { int g[16][16]; CLR(g, 0); int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { g[i][j] = G[i][j]; } } for (int i = n - 1; i >= 0; i--) { if (g[0][i] == 0) { if (cur & 1) { ans++; g[0][i] = 1; } cur >>= 1; } } for (int i = 1; i <= n; i++) { for (int j = 0; j < n; j++) { int sum = 0; for (int k = 0; k < 4; k++) { int x = i + Move[k][0]; int y = j + Move[k][1]; if (ok(x, y)) sum += g[x][y]; } if (sum & 1) { if (g[i][j] == 0) { g[i][j] = 1; ans++; } else { return INF; } } } } return ans; } int main() { int t; cin >> t; int count = 1; while (t--) { scanf("%d", &n); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &G[i][j]); int ans = INF; int len = 0; for (int i = 0; i < n; i++) { if (G[0][i] == 0) len++; } len = 1 << len; for (int i = 0; i <= len; i++) ans = min(check(i),ans); printf("Case %d: ", count++); if (ans == INF) printf("-1\n"); else cout << ans << endl; } }转载于:https://www.cnblogs.com/Dup4/p/9433123.html
相关资源：JAVA上百实例源码以及开源项目