UVA - 11464 Even Parity 【暴力枚举】
程序员文章站
2022-06-02 21:24:46
...
题意
给出一个 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;
}
}