poj 1681 Painter's Problem 高斯消元 枚舉自由變元

Painter's Problem

Time Limit: 1000MS	Memory Limit: 10000K
Total Submissions: 5598	Accepted: 2705

Description

There is a square wall which is made of n*n small square bricks. Some bricks are white while some bricks are yellow. Bob is a painter and he wants to paint all the bricks yellow. But there is something wrong with Bob's brush. Once he uses this brush to paint brick (i, j), the bricks at (i, j), (i-1, j), (i+1, j), (i, j-1) and (i, j+1) all change their color. Your task is to find the minimum number of bricks Bob should paint in order to make all the bricks yellow. 

Input

The first line contains a single integer t (1 <= t <= 20) that indicates the number of test cases. Then follow the t cases. Each test case begins with a line contains an integer n (1 <= n <= 15), representing the size of wall. The next n lines represent the original wall. Each line contains n characters. The j-th character of the i-th line figures out the color of brick at position (i, j). We use a 'w' to express a white brick while a 'y' to express a yellow brick.

Output

For each case, output a line contains the minimum number of bricks Bob should paint. If Bob can't paint all the bricks yellow, print 'inf'.

Sample Input

2
3
yyy
yyy
yyy
5
wwwww
wwwww
wwwww
wwwww
wwwww
      

Sample Output

0
15
      

Source

題意：類似于開燈問題

解法：高斯消元 , 需要枚舉自由變元

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define for0(a, n) for (int (a) = 0; (a) < (n); (a)++)
#define for1(a, n) for (int (a) = 1; (a) <= (n); (a)++)
#define sqr(x) ((x)*(x))
#define ysk(x)  (1<<(x))
typedef long long ll;
typedef pair<int, int> pii;
const int INF =0x3f3f3f3f;
const int maxn=225    ;

int n,equ,var;
int x[maxn+10],freex[maxn+10];
int a[maxn+10][maxn+10];
int pos[maxn+10];
void debug(void)
{
    int i, j;
    for (i = 0; i < equ; i++)
    {
        for (j = 0; j < var + 1; j++)
        {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

int guass()
{
    int row,col,free_num=0;//free_num 為自由變元數目
//    debug();
    for(row=0,col=0;row<equ&&col<var;row++,col++)//行指針row，列指針col，一個equ*row大小的矩陣
    //其中equ為矩陣的行數
    {
   //第一步：進行初等行變換(交換行)，使得目前行目前列系數不為零
         if(!a[row][col])
         {
             for(int i=row;i<equ;i++)
             {
                  if(a[i][col])
                  {
                      for(int k=col;k<=var;k++)
                      {
                          swap(a[i][k],a[row][k]);
                      }
                      break;
                  }
             }
         }
        //如果沒有可以交換的行，那麼目前列col對應的元為自由變元。指針繼續又掃，而不會下降。
         if(!a[row][col])  { row--;freex[free_num++]=col;   continue;}

//第二步，為了使之變為階梯形矩陣,将下方處于該列的系數全部消為0 (第i行減去第row行)
         for(int i=row+1;i<equ;i++)  if(a[i][col])
         {
               for(int k=col;k<=var;k++)
               {
                   a[i][k]^=a[row][k];
               }
         }
         pos[row]=col;//pos[row]記錄了第row行第一個非零系數。

    }
    //第三步，判斷無解的情況
    //這個時候row行到下方的方程都是無用的，實際上矩陣的秩=row,就是第0到第row-1個方程。
    for(int i=row;i<equ;i++)
    {
        if(a[i][var]) return -1;
    }
// 一般這裡有個判斷多解的情況。   
// if(row!=col) return var-row;//整個過程是col不斷右移，但是在某一段時間裡，row可能會停住。
    //因為這一行掃過去，a[i][col]持續為0
    //自由變元的個數=變量數var-實際方程數row(矩陣的行秩)


//該題目要求的是最小的步數，也就是∑xi最小，那麼枚舉自由變元，使得所有的xi之後最小。
    int ans=INF;
    for(int s=0;s<ysk(free_num);s++)
    {
        int cnt=0;
        int ts=s;
        for(int i=0;i<free_num;i++)
        {
            x[freex[i]]=ts&1;
            if(x[freex[i]])  cnt++;
            ts>>=1;
        }

        int j= var-1 ;
        for(int i=row-1;i>=0;i--)
        {
            int p=pos[i];
             x[p]=a[i][var];
            for(int j= var-1;j>p;j--)
            {
                x[p]^=a[i][j]*x[j];
            }
            if(x[p])  cnt++;
        }
        ans=min(ans,cnt);
    }




   return ans;

}

void init()
{
    equ=sqr(n);
    var=equ;
    memset(a,0,sizeof a);
    for0(i,equ)
    {
        a[i][i]=1;
        if(i-n>=0)  a[i-n][i]=1;
        if(i+n<equ) a[i+n][i]=1;
        if(i%n !=0) a[i-1][i]=1;
        if(i%n !=n-1) a[i+1][i]=1;
    }
}
int main()
{
    int T;char ch;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        init();

        for0(i,equ)
        {
            scanf(" %c",&ch);
            a[i][var]= (ch=='y')?0:1;//若原來是黃色，那麼不需要變，為0。
        }
        int ans=guass();
        if(ans==-1)  printf("inf\n");
        else  printf("%d\n",ans);
    }

   return 0;
}