欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVA - 11464 Even Parity 【暴力枚举】

程序员文章站 2022-06-02 21:24:46
...

UVA - 11464 Even Parity 【暴力枚举】

题意
给出一个 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;
    }
}

相关标签: 枚举