POJ 1222 EXTENDED LIGHTS OUT(高斯消元)

题目链接～～～

　这道题做的真纠结，这是学习高斯消元的第一题，没想到就……，开始想了很久没想到怎么做，然后看一些题解吧，结果题解也没看懂。主要是不明白为什么那样列方程，为什么有唯一解，搜了很多博客加上考研线代残留的知识终于完全明白了。

　题意就不说了（此题需要一些线性代数的知识），我们先解决第一个问题怎样列方程（或者为什么列方程）? 我们可以把 5*6 的初始矩阵看成一个30 * 1的列向量（为了后面更好的列方程，所以看成列向量）Y(y1 ,y2 ,y3 ……y30) 。然后把每一个开关也看成一个列向量C(k)（向量里总共30个值），那向量里的值是什么呢？如果第 k 个开关被按下影响了哪个灯就把相应位置为１，否则置为０(例如：按第一个开关，１，２，７号灯会有影响，那么C(1) = {1 ,1 ,0 ,0 ,0 ,0 ,1 ,0,后面全为0}，其它的开关也这样，那么要是全部的开关关掉，就必须 Y(y1 ,y2……y30) + x1 * C(k1)  + x2 * C(k2) + x3 * C(k3) ……＋x30 * C(k30) = (0 ,0 ,0……0) （再次强调等式里的向量都是列向量）,这里等式左边需要mod 2，其中等式中的 x1 ,x2 ……x30 为未知数，为0 或 1 ，1 代表操作了此按钮，０代表没操作，然后我们把所有未知数看成一个列向量X(x1 ,x2 ,x3……x30)，C(k1) ,C(k2) ……C(k30)，也组成一个30*30 的矩阵 A(C(k1) ,C(k2) ,C(k3)……C(k30))（这里Y其实是一个对称向量，Y的转置等于Y）,这样等式就变成了 A*X = Y (mod 2) ,这样方程就列出来了。

　然后为什么有唯一解呢？我们可以发现 r(A) = 30，也就是说 A 可逆，因为r(A) = r(A ,Y) = 30 = n (注意 : 如果矩阵不是30 * 30 的这种形式的矩阵，则可能不是唯一解) ，所以方程一定有唯一解。好了下面就可以用高斯消元解方程了。（因为此矩阵 A 为对称矩阵那么代码中完全可以将向量C(k) 组成 A矩阵的时候看成行向量）。

代码：

  

   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     

      #include <cstdio>
     
    
   

    

     

    
    

     

      #include <cstring>
     
    
   

    

     

    
    

     

      #include <cmath>
     
    
   

    

     

    
    

     

      #include <algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const int MX = 30 + 10 ;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int a[MX][MX] ,ans[MX] ;//a数组存增广矩阵，ans存最终答案
     
    
   

    

     

    
    

     

      int x[] = {-1 ,1 ,0 ,0 ,0} ,y[] = {0 ,0 ,-1 ,1 ,0} ;
     
    
   

    

     

    
    

     

      void Gauss(int n ,int m){
     
    
   

    

     

    
    

     
 int max_r ;
     
    
   

    

     

    
    

     
 int k = 0 ,col = 0 ;
     
    
   

    

     

    
    

     
 for( ;k < n && col < m ; ++k ,++col){
     
    
   

    

     

    
    

     

       max_r = k ;
     
    
   

    

     

    
    

     
 for(int i = k + 1 ;i < n ; ++i)
     
    
   

    

     

    
    

     
 if(abs(a[max_r][col]) < abs(a[i][col]))
     
    
   

    

     

    
    

     

       max_r = i ;
     
    
   

    

     

    
    

     
 if(!a[max_r][col]){
     
    
   

    

     

    
    

     

       k-- ;
     
    
   

    

     

    
    

     
 continue ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(max_r != k){
     
    
   

    

     

    
    

     
 for(int i = col ;i <= m ; ++i)
     
    
   

    

     

    
    

     

       swap(a[k][i] ,a[max_r][i]) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for(int i = k+1 ;i < n ; ++i){
     
    
   

    

     

    
    

     
 if(a[i][col]){
     
    
   

    

     

    
    

     
 for(int j = col ; j <= m ; ++j)
     
    
   

    

     

    
    

     

       a[i][j] = a[i][j]^a[k][j] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for(int i = n-1 ; i >= 0 ; --i){
     
    
   

    

     

    
    

     

       ans[i] = a[i][m] ;
     
    
   

    

     

    
    

     
 for(int j = i+1 ;j < m ; ++j)
     
    
   

    

     

    
    

     

       ans[i] = ans[i]^(a[i][j]&&ans[j]) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void Input(int n ,int m){
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < n ; ++i){
     
    
   

    

     

    
    

     
 for(int j = 0 ;j < m ; ++j){
     
    
   

    

     

    
    

     
 int t = i*m + j ;
     
    
   

    

     

    
    

     
 scanf("%d" ,&a[t][n*m]) ;
     
    
   

    

     

    
    

     
 for(int k = 0 ;k < 5 ; ++k){
     
    
   

    

     

    
    

     
 int sx = x[k] + i ;
     
    
   

    

     

    
    

     
 int sy = y[k] + j ;
     
    
   

    

     

    
    

     
 int st = sx*m + sy ;
     
    
   

    

     

    
    

     
 if(sx >= 0 && sx < n && sy >= 0 && sy < m){
     
    
   

    

     

    
    

     

       a[t][st] = 1 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main(){
     
    
   

    

     

    
    

     
 //freopen("input.txt" ,"r" ,stdin) ;
     
    
   

    

     

    
    

     
 int T ,cse = 1 ;
     
    
   

    

     

    
    

     
 cin>>T ;
     
    
   

    

     

    
    

     
 while(T--){
     
    
   

    

     

    
    

     
 int n = 5 ,m = 6 ;
     
    
   

    

     

    
    

     
 memset(a ,0 ,sizeof(a)) ;
     
    
   

    

     

    
    

     
 memset(ans ,0 ,sizeof(ans)) ;
     
    
   

    

     

    
    

     

       Input(n ,m) ;
     
    
   

    

     

    
    

     

       Gauss(n*m ,n*m) ;
     
    
   

    

     

    
    

     
 cout<<"PUZZLE #"<<cse++<<endl ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < n*m ; ++i){
     
    
   

    

     

    
    

     
 if((i+1)%6 == 0){
     
    
   

    

     

    
    

     
 printf("%d\n" ,ans[i]) ;
     
    
   

    

     

    
    

     

       }else printf("%d " ,ans[i]) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/51952330