POJ-1681

/**
          题意：根据给出的图，问有多少种方法使得变为全‘y’
          做法：高斯消元 建一个n*n的矩阵
**/
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#define maxn 250
using namespace std;
int mmap[maxn][maxn];
int x[maxn];
int equ,val;
char ch[20][20];
int free_x[maxn];
int gcd(int a,int b)
{
    if(b == 0) return a;
    return gcd(b,a%b);
}
int Lcm(int a,int b)
{
    return a/gcd(a,b)*b;
}
int Guess()
{
    int lcm;
    int ta;
    int tb;
    int max_r;
    int k;
    int col;
    col = 0;
    for(k = 0; k<equ&&col < val; k++,col++)
    {
        max_r = k;
        for(int i=k+1; i<equ; i++)
        {
            if(abs(mmap[i][col]) > abs(mmap[max_r][col]))
            {
                max_r = i;
            }
        }
        if(mmap[max_r][col] == 0)
        {
            k--;
            continue;
        }
        if(max_r != k)
        {
            for(int i=col; i<val+1; i++)
            {
                swap(mmap[max_r][i],mmap[k][i]);
            }
        }
        for(int i=k+1; i<equ; i++)
        {
            if(mmap[i][col] != 0)
            {
                for(int j=col; j<val+1; j++)
                {
                    mmap[i][j] ^= mmap[k][j];
                }
            }
        }
    }
    for(int i=k; i<equ; i++)
    {
        if(mmap[i][col] != 0) return -1;
    }
    for(int i=val-1; i>=0; i--)
    {
        x[i] = mmap[i][val];
        for(int j=i+1; j<val; j++)
        {
            x[i] ^= (mmap[i][j] & x[j]);
        }
    }
    return 0;
}
void init(int n)
{
    memset(x,0,sizeof(x));
    memset(mmap,0,sizeof(mmap));
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            int tt = i * n +j;
            mmap[tt][tt] = 1;
            if(i > 0) mmap[(i-1)*n+j][tt] = 1;
            if(i < n-1) mmap[(i+1)*n+j][tt] = 1;
            if(j > 0) mmap[i*n + j - 1][tt] = 1;
            if(j < n-1) mmap[i*n + j + 1][tt] = 1;
        }
    }
}
void solve(int tt)
{
    int res = Guess();
    if(res == -1) printf("inf\n");
    else if(res == 0)
    {
        int ans = 0;
        for(int i=0; i<=tt; i++)
        {
            ans += x[i];
        }
        printf("%d\n",ans);
        return;
    }
    else
    {
        int ans = 0x3f3f3f3f;
        int tot = (1<<res);
        for(int i=0; i<tot; i++)
        {
            int cnt = 0;
            for(int j=0; j<res; j++)
            {
                if(i &(1<<j))
                {
                    x[free_x[j]] = 1;
                    cnt++;
                }
                else x[free_x[j]] = 0;
            }
            for(int j=val-tt-1; j>=0; j--)
            {
                                        int k;
                for( k=j; k<val; k++)
                    if(mmap[j][k]) break;
                x[k] = mmap[j][val];
                for(int l=k+1; l < val; l++)
                    if(mmap[j][l]) x[k] ^= x[l];
                cnt += x[k];

            }
            ans = min(ans,cnt);
        }
        printf("%d\n",ans);
    }
    return;
}
int main()
{
//#ifndef ONLINE_JUDGE
//    freopen("in.txt","r",stdin);
//#endif // ONLINE_JUDGE
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        char c[28];
        init(n);
        int tt = n*n;
        equ = val = tt;
        for(int i=0; i<n; i++)
        {
            scanf("%s",c);
            for(int j=0; j<n; j++)
            {
                if(c[j] == ‘y‘) mmap[i*n+j][tt] = 0;
                else mmap[i*n+j][tt] = 1;

            }
        }
        solve(tt);
    }
    return 0;
}