poj1222 EXTENDED LIGHTS OUT<高斯消元>

View Code
 1 #include <stdio.h>
 2 #include <string.h>
 3  int d[35][35], x[35], map[7][7];
 4  const int N=30;
 5  void Gauss(  )
 6  {
 7     int i=1, j, p, k, t;
 8     for( j=1; j<=N; ++ j ){
 9         for( p=i;p<=N; ++ p ){
10             if(d[p][j])break ;
11         }
12         if( p>N )continue;
13         if( p!=i ){
14             for( k=j; k<=N+1; ++k ){
15                 t=d[p][k],d[p][k]=d[i][k],d[i][k]=t;
16             }
17         }
18         for( p=i+1; p<=N; ++p ){
19             if( d[p][j] ){
20                 for(k=j;k<=N+1; ++k ){
21                     d[p][k]^=d[i][k];
22                 }
23             }
24         }
25         ++i;
26     }
27     memset( x, 0, sizeof x );        
28     for( p=N; p>=1; --p){
29         for( k=p+1; k<=N; ++ k ){
30                 x[p]^=( x[k]&&d[p][k] );
31         }
32         x[p]^=d[p][N+1];
33     }
34     for( int i=1; i<=30; ++i ){
35         printf( "%d ", x[i]);
36         if( i%6==0 )
37             puts("");    
38     }
39     //puts( "" );
40 }
41 int main( )
42 {
43     int T,Case=1;
44     scanf( "%d", &T );
45     while(T--) {
46         memset(d, 0, sizeof d);
47         for( int i=1; i<=30; ++i )
48             d[i][i]=1;
49         for( int i=0; i<5; ++ i ){
50             for(int j=0; j<6;++j ){
51                 scanf( "%d", &map[i][j] );
52                 if( map[i][j] )    d[i*6+j+1][31]=1;
53                     
54                 if( i>0 )d[(i-1)*6+j+1][i*6+j+1]=1;    
55                 if( j>0 )d[i*6+j][i*6+j+1]=1;    
56                 if( i<4 )d[(i+1)*6+j+1][i*6+j+1]=1;    
57                 if( j<5 )d[i*6+j+2][i*6+j+1]=1;    
58             }    
59         } 
60         printf( "PUZZLE #%d\n", Case++ );
61         Gauss( );
62     } 
63     return 0;    
64 }