高斯消元系列

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stdlib.h>
  6 #include<vector>
  7 #include<cmath>
  8 #include<queue>
  9 #include<set>
 10 using namespace std;
 11 #define N 100000
 12 #define LL long long
 13 #define INF 0xfffffff
 14 const double eps = 1e-8;
 15 const double pi = acos(-1.0);
 16 const double inf = ~0u>>2;
 17 int f[10][1<<6],a[8],b[8][8],o[10][1<<6];
 18 char s[8][8];
 19 int main()
 20 {
 21     int i,j,g,t,kk=0;
 22     cin>>t;
 23     while(t--)
 24     {
 25         for(i = 1 ; i <= 5 ; i++)
 26         {
 27             for(j = 0 ; j < 6 ; j++)
 28             {
 29                 cin>>s[i][j];
 30                 b[i][j] = s[i][j]-‘0‘;
 31             }
 32         }
 33 
 34         for(i = 0 ; i < (1<<6) ; i++)
 35         {
 36             for(j = 0 ; j < 6 ; j++)
 37             a[j] = b[1][j];
 38             for(g = 0 ; g < 6 ; g++)
 39             if((1<<g)&i)
 40             {
 41                 if(g==0)
 42                 {
 43                     a[g] = (a[g]+1)%2;
 44                     a[g+1] = (a[g+1]+1)%2;
 45                 }
 46                 else
 47                 {
 48                     a[g] = (a[g]+1)%2;
 49                     a[g-1] = (a[g-1]+1)%2;
 50                     a[g+1] = (a[g+1]+1)%2;
 51                 }
 52             }
 53 
 54             int tt = 0;
 55             for(j = 0 ; j < 6 ; j++)
 56             tt+=(1<<j)*a[j];
 57             f[1][tt] = 1;
 58             o[1][tt] = i;
 59         }
 60         for(i = 2; i <= 5 ; i++)
 61         {
 62             for(j = 0 ; j < (1<<6) ; j++)
 63             {
 64                 if(!f[i-1][j]) continue;
 65                 for(g = 0  ;g < 6 ; g++)
 66                 a[g] = b[i][g];
 67                 for(g = 0 ; g < 6 ; g++)
 68                 {
 69                     if((1<<g)&j)
 70                     {
 71                         if(g==0)
 72                         {
 73                             a[g] = (a[g]+1)%2;
 74                             a[g+1] = (a[g+1]+1)%2;
 75                         }
 76                         else
 77                         {
 78                             a[g] = (a[g]+1)%2;
 79                             a[g-1] = (a[g-1]+1)%2;
 80                             a[g+1] = (a[g+1]+1)%2;
 81                         }
 82                     }
 83                     if(o[i-1][j]&(1<<g))
 84                     a[g]= (a[g]+1)%2;
 85                 }
 86                 int sum=0;
 87                 for(g = 0 ; g < 6 ; g++)
 88                 sum+=(1<<g)*a[g];
 89                 f[i][sum] = f[i-1][j];
 90                 o[i][sum] = j;
 91             }
 92         }
 93         int t = 0;
 94         printf("PUZZLE #%d\n",++kk);
 95         for(i = 5 ; i >= 1; i--)
 96         {
 97             t = o[i][t];
 98             for(j = 0 ; j < 6 ; j++)
 99             {
100                 if(t&(1<<j))
101                 b[i][j] = 1;
102                 else
103                 b[i][j] = 0;
104             }
105         }
106         for(i = 1 ; i <= 5 ; i++)
107         {
108             for(j = 0 ; j < 5 ; j++)
109             cout<<b[i][j]<<" ";
110             cout<<b[i][5];
111             cout<<endl;
112         }
113         //puts("");
114     }
115     return 0;
116 }

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<vector>
 7 #include<cmath>
 8 #include<queue>
 9 #include<set>
10 using namespace std;
11 #define N 100000
12 #define LL long long
13 #define INF 0xfffffff
14 const double eps = 1e-8;
15 const double pi = acos(-1.0);
16 const double inf = ~0u>>2;
17 int x[42][42],ans[32];
18 int gauss()
19 {
20     int i,j,k;
21     for(k = 0 ;k < 30 ; k++)//依次将第k列变换为0
22     {
23         i = k;
24         while(i<30&&x[i][k]==0) i++;
25         if(i!=k)//找出第一个k列不为0的行 与之交换  因为是01 一般的会找出最大的
26         {
27             for(j = 0 ; j <= 30 ; j++)
28             swap(x[k][j],x[i][j]);
29         }
30         //i++;
31         for(i = 0 ;i <30 ; i++)//所有行与第k行进行运算 
32         {
33             if(i==k||x[i][k]==0)
34             {
35                 continue;
36             }
37             for(j = 0 ;j <= 30 ; j++)
38             {
39                 x[i][j]^=x[k][j];//因为01矩阵的特殊性 直接异或就可以了
40             }
41         }
42     }
43     for(i = 0 ;i < 30 ;i++)
44     {
45         if(x[i][30])
46         {
47             for(j = 0 ; j < 30&&x[i][j]==0 ; j++);
48             if(j==30) return 0;
49             else ans[j] = x[i][30];//也是因为01矩阵的特殊性 免去了解一元方程的麻烦
50         }
51     }
52     return 1;
53 }
54 int main()
55 {
56     int i,j,n,kk=0;
57     cin>>n;
58     while(n--)
59     {
60         memset(ans,0,sizeof(ans));
61         memset(x,0,sizeof(x));
62         for(i =0 ;i < 30 ;i++)
63         {
64             scanf("%d",&x[i][30]);
65         }
66         for(i =0 ; i < 30 ;i++)//构造矩阵 行为开关 列为灯  一个开关可以控制5个灯
67         {
68             x[i][i] = 1;
69            if(i>5) x[i][i-6] = 1;
70            if(i%6>0) x[i][i-1] = 1;
71            if(i%6<5) x[i][i+1] = 1;
72            if(i+6<30) x[i][i+6] = 1;
73         }
74         /*for(i = 0 ;i < 30 ;i++)
75         {
76             int tx = i/6;
77             int ty = i%6;
78             x[i][i] = 1;
79             for(j = 0 ; j < 30 ; j++)
80             {
81                 int kx = j/6;
82                 int ky = j%6;
83                 if(abs(tx-kx)+abs(ty-ky)<=1)
84                 x[i][j] = 1;
85             }
86         }*/
87         gauss();
88         printf("PUZZLE #%d\n",++kk);
89         for(i = 0 ; i < 30 ;i++)
90         {
91             cout<<ans[i];
92             if((i+1)%6==0) puts("");
93             else cout<<" ";
94         }
95     }
96     return 0;
97 }