POJ1753高斯消元+枚舉

Flip Game

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 20337		Accepted: 8821

Flip game is played on a rectangular 4x4 field with two-sided pieces placed on each of its 16 squares. One side of each piece is white and the other one is black and each piece is lying either it's black or white side up. Each round you flip 3 to 5 pieces, thus changing the color of their upper side from black to white and vice versa. The pieces to be flipped are chosen every round according to the following rules: 

1. Choose any one of the 16 pieces. 
   
2. Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any).

Consider the following position as an example: 

bwbw 
wwww 
bbwb 
bwwb 
Here "b" denotes pieces lying their black side up and "w" denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become: 

bwbw 
bwww 
wwwb 
wwwb 
The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal. 

The input consists of 4 lines with 4 characters "w" or "b" each that denote game field position.

Write to the output file a single integer number - the minimum number of rounds needed to achieve the goal of the game from the given position. If the goal is initially achieved, then write 0. If it's impossible to achieve the goal, then write the word "Impossible" (without quotes).

bwwb
bbwb
bwwb
bwww

4

 

解題：

基本和POJ1222差不多(參見博客POJ1222中內容)點擊打開鏈接

但是出現行變換後最後四行值均為0 即方程組有無窮解狀態 通過最後一行回帶一個未知數x (0或1)

那麼通過枚舉或者搜索找出最小的變換

 

#include <iostream>
#include <cstring>
#include <stdio.h>
using namespace std;
const int maxn=16;
int a[maxn][maxn+1],x[maxn],b[maxn][maxn+1];
int equ,var;
bool free_x[maxn+1]; // 判斷是否是不確定的變元.
int free_num,ans=100000000;
int abs1(int num)
{
    if (num>=0) return num;
    else
        return -1*num;
}
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;
    a=b;
    b=temp;
}
int Gauss_1()
{
    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; //a[i][j]隻有0 和
//1 兩種狀態
            }
        }
    }
    for(int i = k; i < equ; ++i)
        if(a[i][col] != 0) return -1; // 無解返回 -1
//上述代碼是消元的過程，消元完成
//Debug();
//唯一解或者無窮解,k<=var
//var-k==0 唯一解；var-k>0 無窮多解，自由解的個數=var-k
//下麵這幾行很重要，保證秩內每行主元非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;
    }
    if (var-k==0)//唯一解時，poj1753 本題沒唯一解，當題目具體操作給出後，係數矩陣已
//經固定了！
    {
//下麵是回帶求解，當無窮多解時，最後幾行為0
        for(int i = k-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;
//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 k,free_num;
    char c1[20];
    memset(a,0,sizeof(a));
    memset(x,0,sizeof(x));
    ans=1000000000;
    for (int i=0; i<4; i++)
    {
        cin>>c1;
//構造係數矩陣A
        for (int j=0; j<4; j++)
        {
            k = 4*i+j;
            a[k][k]=1;
            if (i>0) a[k][k-4]=1; //上
            if (i<3) a[k][k+4]=1; //下
            if (j>0) a[k][k-1]=1; //左
            if (j<3) a[k][k+1]=1; //右
            if (c1[j]=='b')
                a[k][maxn] = 1;
        }
    }
    for(int i=0; i<16; i++)
        for(int j=0; j<=16; j++)
            b[i][j]=a[i][j];
    for(int k=0; k<16; k++)
        b[k][16]^=1;
    equ=var=16;
    int j1=Gauss_1();
    int min1=ans;
    for(int i=0; i<16; i++)
        for(int j=0; j<=16; j++)
            a[i][j]=b[i][j];
    ans=100000000;
    int j2=Gauss_1();
    int min2=ans;
    if (j1==-1&&j2==-1) cout<<"Impossible"<<endl;
    else
        cout<<min(ans,min1)<<endl;
// cout << "Hello world!" << endl;
    return 0;
}