POJ 1222 EXTENDED LIGHTS OUT

题目大意:

灯有亮(1),熄灭(0)两种状态，按一个位置的按钮，那么当前位置以及上下左右的灯都会改变一次状态，给定一个灯的

初始状态，求一个按钮按的状态是这些灯都熄灭

因为最后灯均为0，按钮的状态为 x[m] m=i*6+j(i行j列)

这道题目中灯固定 5行6列30个，那么每一个的位置都最多只跟 5 个按钮有关，按一次相当于 1*x[m]

除了这五个位置，其他位置的系数均为0，那么就可以列出一个30个方程的线性方程组，用高斯消元法解决问题，当然问题处理

过程中始终要mod 2

  1 #include <cstdio>
  2 #include <cstring>
  3 
  4 using namespace std;
  5 int x[35] , b[5][6] , a[35][35];
  6 
  7 int gcd(int a , int b)
  8 {
  9     if(b == 0) return a;
 10     else return gcd(b , a%b);
 11 }
 12 
 13 int lcm(int a , int b)
 14 {
 15     return a/gcd(a , b)*b;//先除后乘防止溢出
 16 }
 17 
 18 inline int my_abs(int x)
 19 {
 20     return x>=0?x:-x;
 21 }
 22 
 23 inline void my_swap(int &a , int &b)
 24 {
 25     int tmp = a;
 26     a = b , b = tmp;
 27 }
 28 
 29 int gauss(int equ , int var , int mod)
 30 {
 31     int max_r; // 当前这列绝对值最大的行
 32     int col; // 当前处理的列
 33     int ta , tb;
 34     int Lcm , tmp;
 35 
 36     for(int i=0 ; i<var ; i++)
 37         x[i] = 0;
 38 
 39     //转化为阶梯形矩阵
 40     col = 0;//一开始处理到第0列
 41     for(int k=0 ; k<equ ; k++,col++){
 42         max_r = k;
 43         for(int i = k+1 ; i<equ ; i++)
 44             if(my_abs(a[i][col]) > my_abs(a[max_r][col]))
 45                 max_r = i;
 46         if(max_r != k){
 47             //交换两行的数据
 48             for(int i=k ; i<var+1 ; i++)
 49                 my_swap(a[max_r][i] , a[k][i]);
 50         }
 51 
 52         if(a[k][col] == 0){
 53             k--;
 54             continue;
 55         }
 56 
 57         for(int i=k+1 ; i<equ ; i++){
 58             //枚举要删去的行
 59             if(a[i][col] != 0 ){
 60                 Lcm = lcm(my_abs(a[i][col]) , my_abs(a[k][col]));
 61                 ta = Lcm / my_abs(a[i][col]);
 62                 tb = Lcm / my_abs(a[k][col]);
 63                 if(a[i][col] * a[k][col] < 0) tb = -tb;//异号相加
 64                 for(int j = col ; j<var+1 ; j++)
 65                     a[i][j] = ((a[i][j]*ta)%mod - (a[k][j]*tb)%mod + mod) % mod;
 66             }
 67         }
 68     }
 69 
 70     for(int i=var-1 ; i>=0 ; i--){
 71         tmp = a[i][var];
 72         for(int j=i+1 ; j<var ; j++){
 73             if(a[i][j] != 0 ) tmp -= a[i][j]*x[j];
 74             tmp = (tmp%mod+mod)%mod;
 75         }
 76         while(tmp%a[i][i])
 77             tmp+=mod;
 78         x[i] = (tmp / a[i][i])%mod;
 79     }
 80     return 0;
 81 }
 82 
 83 int main()
 84 {
 85    // freopen("a.in" , "r" , stdin);
 86     int T , cas=0;
 87     scanf("%d" , &T);
 88     while(T--)
 89     {
 90         for(int i=0 ; i<5 ; i++)
 91             for(int j=0 ; j<6 ; j++)
 92                 scanf("%d" , &b[i][j]);
 93         //构建线性方程
 94         memset(a , 0 , sizeof(a));
 95         for(int i=0 ; i<5 ; i++){
 96             for(int j=0 ; j<6 ; j++){
 97                 a[i*6+j][30] = b[i][j];
 98                 for(int p=0 ; p<5 ; p++){
 99                     for(int q=0 ; q<6 ; q++){
100                         if(my_abs(i-p) + my_abs(j-q) <= 1){
101                             a[i*6+j][p*6+q] = 1;
102                         }
103                     }
104                 }
105             }
106         }
107 
108         gauss(30 , 30 , 2);
109         printf("PUZZLE #%d
" , ++cas);
110         for(int i=0;i<5 ; i++){
111             for(int j=0 ; j<6 ; j++){
112                 if(j) printf(" %d" , x[i*6+j]);
113                 else printf("%d" , x[i*6+j]);
114             }
115             printf("
");
116         }
117     }
118     return 0;
119 }