POJ 2965 The Pilots Brothers' refrigerator 高斯消元

野性酷女 2022-09-25 15:20 23阅读 0赞

POJ 2965 The Pilots Brothers' refrigerator 高斯消元 题目链接：[http://poj.org/problem?id=2965][http_poj.org_problem_id_2965]

题面描述：

The Pilots Brothers' refrigerator

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td colspan="3"><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;24288</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;9379</td> 
   <td>&nbsp;</td> 
   <td style="font-weight:bold; color:red">Special Judge</td> 
  </tr> 
 </tbody> 
</table>

Description

The game “The Pilots Brothers: following the stripy elephant” has a quest where a player needs to open a refrigerator.

There are 16 handles on the refrigerator door. Every handle can be in one of two states: open or closed. The refrigerator is open only when all handles are open. The handles are represented as a matrix 4х4. You can change the state of a handle in any location **\[i, j\]** (1 ≤ i, j ≤ 4). However, this also changes states of all handles in row **i** and all handles in column **j**.

The task is to determine the minimum number of handle switching necessary to open the refrigerator.

Input

The input contains four lines. Each of the four lines contains four characters describing the initial state of appropriate handles. A symbol “+” means that the handle is in closed state, whereas the symbol “−” means “open”. At least one of the handles is initially closed.

Output

The first line of the input contains N – the minimum number of switching. The rest N lines describe switching sequence. Each of the lines contains a row number and a column number of the matrix separated by one or more spaces. If there are several solutions, you may give any one of them.

Sample Input

-+--
    ----
    ----
    -+--

Sample Output

6
    1 1
    1 3
    1 4
    4 1
    4 3
    4 4

Source

[Northeastern Europe 2004][], Western Subregion

题目大意：

为了打开冰箱门，当且仅当冰箱门上的16个开关都为开时，才能打开；且每次按动一个开关，该开关的所在行和所在列的所有的开关都要进行翻转，即为由开变关或者由关变开，给定初始状态，求最小按动开关的次数使得冰箱门打开，并输出所按的开关分别是哪些。

题目分析：

利用高斯消元，由于冰箱门一定能被打开，所以初始状态A矩阵的逆矩阵一定能求出来，所以利用如下公式：

![Image 1][]

求得A的逆矩阵后，直接用A矩阵的逆矩阵和b矩阵做矩阵相乘即可。这样只需要进行一次高斯消元，可以提高一下效率，当然也可以直接把A的逆矩阵算出来打印在代码中，这样会更快一点。

注意：I矩阵为只有对角线元素为1的单位阵。

代码实现：异或版

#include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    int a[16][33],c[16][16];
    int ans[16];
    
    void Gauss()
    {
        for(int i=0; i<16; i++)//i代表行，也是主元的位置
        {
            int k=i;//k代表列，从对角线的行开始就好
            for(;k<16;k++)//找到这一列第一个不为0的行，作为主元
            {
                if(a[k][i]!=0)
                    break;
            }
            for(int j=0;j<=31;j++)//交换整行
            {
                swap(a[i][j],a[k][j]);
            }
            //开始消元
            for(int j=0;j<16;j++)//j代表行
            {
                if(i!=j&&a[j][i])//不是主元行，要消元的行已经是1了才消
                    for(int k=0;k<=31;k++)//k代表列
                    a[j][k]=a[i][k]^a[j][k];
            }
        }
        //把逆矩阵放在数组C中
        for(int i=0;i<16;i++)
        {
            for( int j=0;j<16;j++)
            {
                c[i][j]=a[i][j+16];
            }
        }
    }
    
    void Debug()
    {
        for(int i=0;i<16;i++)
        {
            for(int j=0;j<31;j++)
            {
                cout<<a[i][j]<<" ";
            }
            cout<<endl;
        }
    }
    
    int main()
    {
        int b[16];
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i=0; i<4; i++)
        {
            for(int j=0; j<4; j++)
            {
                for(int k=0; k<4; k++)
                {
                    a[4*k+j][4*i+j]=1;
                    a[4*i+k][4*i+j]=1;
                }
            }
        }
        for( int i=0; i<16; i++)
        {
            a[i][16+i]=1;
        }
        //Debug();
        Gauss();
       // Debug();
        char str[10];
        memset(str,0,sizeof(str));
        for(int i=0; i<4; i++)
        {
            scanf("%s",str);
            for(int j=0; j<4;j++)
            {
                if(str[j]=='+')
                {
                    b[4*i+j]=1;
                }
            }
        }
        //执行x=A^(-1)*b
        memset(ans,0,sizeof(ans));
        for(int i=0;i<16;i++)
            for(int j=0;j<16;j++)
            ans[i]=ans[i]^(c[i][j]*b[j]);
    
        int sum=0;
        for(int i=0;i<16;i++)
        {
            sum+=ans[i];
        }
        cout<<sum<<endl;
        for(int i=0;i<16;i++)
        {//cout<<b[i]<<endl;
            if(ans[i]==1)
            {
                printf("%d %d\n",i/4+1,i%4+1);
            }
        }
        return 0;
    }

代码实现：直接打印出矩阵的逆。

#include <iostream>
    #include <cstring>
    #include <cstdio>
    
    using namespace std;
    
    int c[16][16]={1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
    1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0,
    1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0,
    1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1,
    1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0,
    0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0,
    0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0,
    0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1,
    1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0,
    0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0,
    0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0,
    0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1,
    1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1,
    0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1,
    0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1,
    0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1,
    };
    
    
    int main()
    {
        int b[16];
        int ans[16];
        char str[10];
        memset(b,0,sizeof(b));
        memset(str,0,sizeof(str));
        for(int i=0; i<4; i++)
        {
            scanf("%s",str);
            for(int j=0; j<4;j++)
            {
                if(str[j]=='+')
                {
                    b[4*i+j]=1;
                }
            }
        }
        //执行x=A^(-1)*b
        memset(ans,0,sizeof(ans));
        for(int i=0;i<16;i++)
            for(int j=0;j<16;j++)
            ans[i]=ans[i]^(c[i][j]*b[j]);
    
        int sum=0;
        for(int i=0;i<16;i++)
        {
            sum+=ans[i];
        }
        cout<<sum<<endl;
        for(int i=0;i<16;i++)
        {//cout<<b[i]<<endl;
            if(ans[i]==1)
            {
                printf("%d %d\n",i/4+1,i%4+1);
            }
        }
        return 0;
    }

[http_poj.org_problem_id_2965]: http://poj.org/problem?id=2965
[Northeastern Europe 2004]: http://poj.org/searchproblem?field=source&key=Northeastern+Europe+2004
[Image 1]: