POJ1222高斯消元

EXTENDED LIGHTS OUT

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 4731		Accepted: 3117

In an extended version of the game Lights Out, is a puzzle with 5 rows of 6 buttons each (the actual puzzle has 5 rows of 5 buttons each). Each button has a light. When a button is pressed, that button and each of its (up to four) neighbors above, below, right and left, has the state of its light reversed. (If on, the light is turned off; if off, the light is turned on.) Buttons in the corners change the state of 3 buttons; buttons on an edge change the state of 4 buttons and other buttons change the state of 5. For example, if the buttons marked X on the left below were to be pressed,the display would change to the image on the right. 

The aim of the game is, starting from any initial set of lights on in the display, to press buttons to get the display to a state where all lights are off. When adjacent buttons are pressed, the action of one button can undo the effect of another. For instance, in the display below, pressing buttons marked X in the left display results in the right display.Note that the buttons in row 2 column 3 and row 2 column 5 both change the state of the button in row 2 column 4,so that, in the end, its state is unchanged. 

Note: 
1. It does not matter what order the buttons are pressed. 
2. If a button is pressed a second time, it exactly cancels the effect of the first press, so no button ever need be pressed more than once. 
3. As illustrated in the second diagram, all the lights in the first row may be turned off, by pressing the corresponding buttons in the second row. By repeating this process in each row, all the lights in the first 
four rows may be turned out. Similarly, by pressing buttons in columns 2, 3 ?, all lights in the first 5 columns may be turned off. 
Write a program to solve the puzzle.

The first line of the input is a positive integer n which is the number of puzzles that follow. Each puzzle will be five lines, each of which has six 0 or 1 separated by one or more spaces. A 0 indicates that the light is off, while a 1 indicates that the light is on initially.

For each puzzle, the output consists of a line with the string: "PUZZLE #m", where m is the index of the puzzle in the input file. Following that line, is a puzzle-like display (in the same format as the input) . In this case, 1's indicate buttons that must be pressed to solve the puzzle, while 0 indicate buttons, which are not pressed. There should be exactly one space between each 0 or 1 in the output puzzle-like display.

2
0 1 1 0 1 0
1 0 0 1 1 1
0 0 1 0 0 1
1 0 0 1 0 1
0 1 1 1 0 0
0 0 1 0 1 0
1 0 1 0 1 1
0 0 1 0 1 1
1 0 1 1 0 0
0 1 0 1 0 0

PUZZLE #1
1 0 1 0 0 1
1 1 0 1 0 1
0 0 1 0 1 1
1 0 0 1 0 0
0 1 0 0 0 0
PUZZLE #2
1 0 0 1 1 1
1 1 0 0 0 0
0 0 0 1 0 0
1 1 0 1 0 1
1 0 1 1 0 1

Greater New York 2002

題目大意：
5*6的一個由燈組成的方陣 操作一個燈 周圍的上下左右四個燈會發生相應變化 即由滅變亮 由亮變滅 問如何操作使燈全亮

解題：
5*6 有30盞燈 那麼每盞燈的亮滅取決上下左右的四盞 由此可列出30元一次方程組 每一盞燈都有一個方程 由線性代數知識可以得出一個30*30的係數陣 如不考慮燈陣的邊 第N個方程都有5個開關影響最後第N個燈的結果 即未知數x(n-1) x(n+1) x(n-6) x(n+6) x(第N盞燈自己的開關也影響自己) 前麵的係數為1 其餘對此燈不起作用所以為0
由此可以列出係數矩陣   參照樣例1 
該係數矩陣確定為 第1盞燈 為方程組[1] 代表係數矩陣第1行
  參照樣例1 得出係數陣 
  
既然方程組等式左邊已經確定 剩餘的就是等式右邊
如果第[N]盞燈已經是亮的 那麼證明開關不用改變 那麼證明經過等式左麵操作的變換開關最終沒用影響該燈的結果 
則為0 如果先前狀態為滅 那麼就需要變亮 則此時第N個方程右邊為1 代表經過 這幾個開關的變換 最終第N盞燈的最
終狀態變亮
由此 則可以確定增廣矩陣
參見樣例1


 
通過矩陣變換的模板  把矩陣做行變換 變換成上三角行矩陣 
1.如果係數矩陣的秩等於增廣矩陣的秩等於行數 則該方程組有唯一解 那麼對應的變亮的方法隻有一種 
2.如果係數矩陣的秩等於增廣矩陣的秩小於行數 則該方程組有無窮多解 但是未知數X隻能取0或1 即亮或滅
那麼 枚舉所有可能情況 求出最小值 但是該題都是唯一解的情況
3.如果係數矩陣的秩不等於增廣矩陣的秩 那麼顯然該方程組無解 對應的沒有方法使燈全亮

行變換後的結果

從最後一個未知數 X30=0 回帶 向上帶 便可以得出所有未知數的解

#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;

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;    //交換 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(void)
{
// freopen("Input.txt", "r", stdin);
    int i, j,t,t1;
    cin>>t;
    t1=t;
    equ=30;
    var=30;
    while (t--)
    {
        memset(a, 0, sizeof(a));
        memset(x, 0, sizeof(x));
//memset(free_x, 1, sizeof(free_x)); // 一開始全是不確定的變元.
//下麵要根據位置計算a[i][j];
        for (i = 0; i < 5; i++)
        {
            for (j = 0; j < 6; j++)
            {
                /* for(int k=0;k<4;k++)
                {
                int ni=i+di[k];
                int nj=j+dj[k];
                if(inlim(ni,nj))
                {
                a[i*6+j][ni*6+nj]=1;
                }
                }
                */
                if (i-1>=0) a[i*6+j][(i-1)*6+j]=1; //計算上麵的位置
                if (i+1<=4) a[i*6+j][(i+1)*6+j]=1;//計算下麵的位置
                if (j-1>=0) a[i*6+j][i*6+j-1]=1;//計算左麵的位置
                if (j+1<=5) a[i*6+j][i*6+j+1]=1; //計算右麵的位置
                a[i*6+j][i*6+j]=1;//別忘了計算自己
                cin>>a[i*6+j][30];
//scanf("%d", &a[i][j]);
            }
        }
//Debug();
//free_num = Gauss();
        free_num=Gauss();
        if (free_num == -1) printf("無解!\n");
        else if (free_num >= 0)
        {
            int na_num=0;
            printf("PUZZLE #%d\n",t1-t);
            for (i = 0; i < var; i++)
            {
                na_num++;
                if (na_num%6==0)
                {
                    printf("%d\n",x[i]);
                }
                else
                    printf("%d ",x[i]);
            }
        }
// printf("\n");
    }
    return 0;
}