【高斯消元&&01矩阵】POJ-3185TheWaterBowls

Step1 Problem:

每次让三个数翻转，结果全为0，最少需要翻转几次？

Step2 Ideas:

构造异或方程组，求出自由元，枚举自由元所有情况，找出最小解。

Step3 Code:

#include
#include
#include
using namespace std;
const int N = 25;
const int inf = 0x3f3f3f3f;
int data[N][N], lib[N];
int x[5] = {1, -1, 0};
bool ok(int x, int y)
{
    if(x >= 0 && x <20 && y >= 0 && y <20) return 1;
    else return 0;
}
int Gauss(int n)
{
    memset(lib, 0, sizeof(lib));
    int r = 0, rst = 0;
    for(int i = 0; i for(int j = r; j //找第i列，从第r行开始，第一个非0行，和r行交换
        {
            if(!data[j][i]) continue;
            for(int k = 0; k <= n; k++)
                swap(data[r][k], data[j][k]);
            break;
        }
        if(!data[r][i]) continue;//没找到，自由元数量++
        for(int j = 0; j //利用r行，消去其他行。
        {
            if(j == r || !data[j][i]) continue;
            for(int k = 0; k <= n; k++)
                data[j][k] ^= data[r][k];
        }
        lib[i] = 1; r++; rst++;
    }
    int ans = 0;
    for(int i = 0; i if(data[i][n]) {//如果第i行，data[i][n]不是0，其他全为0则无解。
            int flag = 0;
            for(int j = 0; j if(data[i][j]) flag = 1;
            }
            if(!flag) return -1;//无解
        }
        if(!lib[i]) continue;
        for(int j = 0; j //求唯一解的答案
        {
            if(data[j][i]) {
                ans += data[j][n];
                break;
            }
        }
    }
    if(rst == n) return ans;//唯一解，直接返回
    else ans = inf;
    int unk = n - rst;//自由变元
    for(int k = 0; k <(1<//枚举自由变元可能解的所有情况
    {
        int num = 0, cnt = 0;
        for(int i = 0; i >i)&1;//自由变元 为 1的数量
        for(int i = 0; i //代回到前rst行
        {
            int t = 0;
            for(int j = 0; j if(data[i][n-j-1]) t ^= (k>>j)&1;
            }
            if(t != data[i][n]) cnt++;
        }
        ans = min(cnt+num, ans);//更新最小解
    }
    return ans;
}
int main()
{
    int n = 20;
    memset(data, 0, sizeof(data));
    for(int i = 0; i scanf("%d", &data[i][n]);
        for(int k = 0; k <3; k++)//data[i][n]只由 周围的三个决定
        {
            int tx = i, ty = i+x[k];
            if(ok(tx, ty)) {
                data[i][ty] = 1;
            }
        }
    }
    int t = Gauss(n);
    if(t == -1) printf("...\n");//无解
    else
    printf("%d\n", t);
    return 0;
}