poj 1753 Flip Game 高斯消元 异或方程组 求最值

题目链接：http://poj.org/problem?id=1753

题意：给出一张4*4的图，表示16个方格的初始颜色的情况(白或黑)，相邻方格操作的时候会相互影响，求最少的操作次数，使得每个方格都是白色或者都是黑色，如果不行输出Impossible。

思路：和poj1222差不多，这题要求最值，所以要枚举自由变元的值。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define maxn 5
char mp[maxn][maxn];
int a[maxn*maxn][maxn*maxn];
int x[maxn*maxn];
int free_x[maxn*maxn];
int free_num;
int mj_ans;
#define inf 0x3f3f3f3f
void init()
{
    memset(a, 0, sizeof(a));
    for(int i = 0; i < 4; i++)
    {
        for(int j = 0; j < 4; j++)
        {
            int pos = i*4+j;
            a[pos][pos] = 1;
            if(i > 0) a[pos][(i-1)*4+j] = 1;
            if(i < 3) a[pos][(i+1)*4+j] = 1;
            if(j > 0) a[pos][i*4+j-1] = 1;
            if(j < 3) a[pos][i*4+j+1] = 1;
        }
    }
}
int Gauss(int n, int m)
{
    memset(x, 0, sizeof(x));
    int r, c;
    free_num = 0;
    for(r = 0, c = 0; r < n && c < m; r++, c++)
    {
        int max_r = r;
        for(int i = r+1; i < n; i++)
        {
            if(fabs(a[i][c]) > fabs(a[max_r][c])) max_r = i;
        }
        if(a[max_r][c] == 0) {r--; free_x[free_num++] = c; continue;}
        if(max_r != r)
        {
            for(int i = c; i < m+1; i++) swap(a[r][i], a[max_r][i]);
        }
        
        for(int i = r+1; i < n; i++)
        {
            if(a[i][c] == 0) continue;
            for(int j = c; j < m+1; j++)
            {
                a[i][j] ^= a[r][j];
            }
        }
    }
    for(int i = r; i < n; i++)
    {
        if(a[i][c]) return -1;
    }
    if(r < m)
    {
        mj_ans = inf;
        int cnt = m-r;
        for(int i = 0; i < (1<<cnt); i++)
        {
            int sum = 0;
            for(int j = 0; j < cnt; j++)
            {
                if(i&(1<<j)) {x[free_x[j]] = 1; sum++;}
                else x[free_x[j]] = 0;
            }
            for(int j = m-1-cnt; j >= 0; j--)
            {
                int pos;
                for(pos = j; pos < m; pos++) if(a[j][pos]) break;
                x[pos] = a[j][m];
                for(int k = pos+1; k < m; k++)
                {
                    x[pos] ^= (a[j][k] && x[k]);
                }
                if(x[pos]) sum++;
            }
            if(sum < mj_ans) mj_ans = sum;
        }
        return m-r;
    }
    for(int i = m-1; i >= 0; i--)
    {
        x[i] = a[i][m];
        for(int j = i+1; j < m; j++)
        {
            x[i] ^= (a[i][j] && x[j]);
        }
    }
    return 0;
}
int main() 
{
    
    //freopen("in.txt", "r", stdin);
    while(~scanf("%s", mp[0]))
    {
        for(int i = 1; i < 4; i++) scanf("%s", mp[i]);

        init();
        for(int i = 0; i < 4; i++)
        {
            for(int j = 0; j < 4; j++)
            {
                if(mp[i][j] == 'b') a[i*4+j][16] = 1; 
            }
        }
        int cnt = Gauss(16, 16);
        int sum1 = 0, sum2 = 0;
        if(cnt == -1) sum1 = inf;
        else if(cnt == 0)
        {
            for(int i = 0; i < 16; i++)
            {
                if(x[i]) sum1++;
            }
        }
        else sum1 = mj_ans;


        init();
        for(int i = 0; i < 4; i++)
        {
            for(int j = 0; j < 4; j++)
            {
                if(mp[i][j] == 'w') a[i*4+j][16] = 1;
            }
        }
        cnt = Gauss(16, 16);
        if(cnt == -1) sum2 = inf;
        else if(cnt == 0)
        {
            for(int i = 0; i < 16; i++)
            {
                if(x[i]) sum2++;
            }
        }
        else sum2 = mj_ans;

        if(min(sum1, sum2) == inf) printf("Impossible
");
        else printf("%d
", min(sum1, sum2));

    }
    return 0;
}