POJ1681高消+搜索

Painter's Problem

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 3484		Accepted: 1718

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. 

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.

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'.

2
3
yyy
yyy
yyy
5
wwwww
wwwww
wwwww
wwwww
wwwww

0
15

 

題解：

典型的高斯消元 詳細參見POJ1222 點擊打開鏈接POJ1222

這題也是出現多解的情況 所以用搜索來搜出一個最小變化數

 

#include <iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=230;
int a[maxn][maxn+1],x[maxn];//a 是係數矩陣和增廣矩陣，x 是最後存放的解
// a[][maxn]中存放的是方程右麵的值（bi）
int equ,var;//equ 是係數陣的行數，var 是係數矩陣的列數（變量的個數）
int free_num,ans=100000000;
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;
}
//調試輸出，看消元後的矩陣值，提交時，就不用了
inline int gcd(int a, int b) //最大公約數
{
    int t;
    while (b != 0)
    {
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}

inline int lcm(int a, int b) //最小公倍數
{
    return a * b / gcd(a, b);
}

int dfs(int p) //枚舉自由解，隻能取0-1，枚舉完就回帶，找到最小的
{
    if (p<=free_num-1) //深入到了主對角線元素非0 的行了
    {
        //下麵就是回帶的代碼啊
        for(int i = free_num-1; i >= 0; --i)
        {
            int tmp = a[i][var] % 2;
            for(int j = i+1; j < var; ++j) //x[i]取決於x[i+1]--x[var]啊，所以後麵的解對前麵的解有影
//響。
                if(a[i][j] != 0)
                    tmp = ( tmp - (a[i][j]*x[j])%2 + 2 ) % 2;
            x[i] = (tmp/a[i][i]) % 2; //上麵的正常解
        } //回帶完成了
//計算解元素為1 的個數；
        int sum=0;
        for(int i=0; i<var; i++) sum+=x[i];
        if (ans>sum) ans=sum;
        return 0;
    }
    x[p]=0;
    dfs(p-1);
    x[p]=1;
    dfs(p-1);
}
void swap(int &a,int &b)
{
    int temp=a;    //交換 2 個數
    a=b;
    b=temp;
}
int Gauss()
{
    int k,col = 0;
//當前處理的列
    for(k = 0; k < equ && col < var; ++k,++col)
    {
        int max_r = k;
        for(int i = k+1; i < equ; ++i)
            if(a[i][col] > a[max_r][col])
                max_r = i;
        if(max_r != k)
        {
            for(int i = k; i < var + 1; ++i)
                swap(a[k][i],a[max_r][i]);
        }
        if(a[k][col] == 0)
        {
            k--;
            continue;
        }
        for(int i = k+1; i < equ; ++i)
        {
            if(a[i][col] != 0)
            {
                int LCM = lcm(a[i][col],a[k][col]);
                int ta = LCM/a[i][col], tb = LCM/a[k][col];
                if(a[i][col]*a[k][col] < 0)
                    tb = -tb;
                for(int j = col; j < var + 1; ++j)
                    a[i][j] = ( (a[i][j]*ta)%2 - (a[k][j]*tb)%2 + 2 ) % 2;
                // 0 和 1 兩種狀態
            }
        }
    }
//a[i][j]隻有

//上述代碼是消元的過程，行消元完成
//解下來 2 行，判斷是否無解
//注意 K 的值，k 代表係數矩陣值都為 0 的那些行的第 1 行
    for(int i = k; i < equ; ++i)
        if(a[i][col] != 0)
            return -1;
//Debug();

//唯一解或者無窮解,k<=var
//var-k==0 唯一解；var-k>0 無窮多解，自由解的個數=var-k
//能執行到這，說明肯定有解了，無非是 1 個和無窮解的問題。
//下麵這幾行很重要，保證秩內每行主元非 0，且按對角線順序排列，就是檢查列
    for(int i = 0; i <equ; ++i)//每一行主元素化為非零
        if(!a[i][i])
        {
            int j;
            for(j = i+1; j<var; ++j)
                if(a[i][j])
                    break;
            if(j == var)
                break;
            for(int k = 0; k < equ; ++k)
                swap(a[k][i],a[k][j]);
        }
// ----處理保證對角線主元非 0 且順序，檢查列完成

    free_num=k;
    if (var-k>0)
    {
        dfs(var-1);
        return ans;
        //無窮多解，先枚舉解，然後用下麵的回帶代碼進行回帶；
//這裏省略了下麵的回帶的代碼；不管唯一解和無窮解都可以回帶，隻不過無窮解
//回帶時，默認為最後幾個自由變元=0 而已。
    }
    if(var-k<0)
        return -1;
// 無解返回 -1
    if (var-k==0)//唯一解時
    {
//下麵是回帶求解代碼，當無窮多解時，最後幾行為 0 的解默認為 0；
        for(int i = k-1; i >= 0; --i) //從消完元矩陣的主對角線非 0 的最後 1 行，開始往
//回帶
        {
            int tmp = a[i][var] % 2;

            for(int j = i+1; j < var; ++j) //x[i]取決於 x[i+1]--x[var]啊，所以後麵的解對前麵的解有影響。
                if(a[i][j] != 0)
                    tmp = ( tmp - (a[i][j]*x[j])%2 + 2 ) % 2;
            //if (a[i][i]==0) x[i]=tmp;//最後的空行時，即無窮解得
            //else
            x[i] = (tmp/a[i][i]) % 2; //上麵的正常解
        }
        int sum=0;
        for(int i=0; i<var; i++)
            sum+=x[i];
        return sum;

        //回帶結束了
    }
}


int main()
{
    int t,n;
    char map[17][17];
    cin>>t;
    getchar();
    while(t--)
    {
        memset(a,0,sizeof(a));
        memset(x,0,sizeof(x));
        ans=100000000;
        cin>>n;
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
            {
                int k=i*n+j;
                a[k][k]=1;
                if(i>0) a[k][k-n]=1;
                if(i<n-1) a[k][k+n]=1;
                if(j>0)  a[k][k-1]=1;
                if(j<n-1) a[k][k+1]=1;
                cin>>map[i][j];
                if(map[i][j]=='w')
                    a[k][n*n]=1;

            }
        equ=var=n*n;
        int j1=Gauss();
        // Debug();
        if(j1==-1)
            cout<<"inf"<<endl;
        else
            cout<<j1<<endl;

    }
    return 0;
}