两个异或方程组的题目，都比较经典，贴上代码当模板，代码来自他人博客
POJ 1222
题目大意：给你一个5*6的格子，每个格子中有灯（亮着1，暗着0），每次你可以把一个暗的点亮（或者亮的熄灭）然后它上下左右的灯也会跟着变化。最后让你把所有的灯熄灭，问你应该改变哪些灯。
/*Poj 1222Author: Robert_YuanMemory: 364KTime: 0MS
*/
#include<cstdio>
#include<cstring>using namespace std;#define maxn 32int n,m;
int x[maxn];
int a[maxn][maxn];
int w[maxn][maxn]; //w[i][j] 表示 i,j是否能互相影响 void swap(int i,int j){ //交换两行int t;for(int k=i;k<=m*n+1;k++)t=w[i][k],w[i][k]=w[j][k],w[j][k]=t;
}void Xor(int i,int j){ //计算for(int k=i;k<=m*n+1;k++)w[j][k]=w[j][k]^w[i][k];
}void print(){ //Debugfor(int i=1;i<=n*m;i++){for(int j=1;j<=m*n+1;j++)printf("%d ",w[i][j]);printf("\n");} printf("\n\n");
}void gauss(){ //高斯消元 解 异或方程 //print();for(int i=1;i<=m*n;i++){bool find=false;for(int j=i;j<=m*n;j++) //列选主元消元if(w[j][i]){ swap(i,j);find=true;break;}if(!find) continue;for(int j=i+1;j<=m*n;j++)if(w[j][i])Xor(i,j);}//print();for(int i=m*n;i>=1;i--){ //求解xix[i]=w[i][m*n+1];if(!x[i]) continue;for(int j=i-1;j>=1;j--) //直接将x[i]带入其余方程if(w[j][i])w[j][m*n+1]^=x[i];}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)printf("%d ",x[(i-1)*m+j]);printf("\n");}
}void prework(){ //初始化增广矩阵n=5,m=6;memset(w,0,sizeof(w));for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)scanf("%d",&a[i][j]),w[(i-1)*m+j][m*n+1]=a[i][j];for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){w[(i-1)*m+j][(i-1)*m+j]=1; //自己和上下左右是对自己有影响的点 if(j!=1) w[(i-1)*m+j][(i-1)*m+j-1]=1;if(j!=m) w[(i-1)*m+j][(i-1)*m+j+1]=1;if(i!=n) w[(i-1)*m+j][i*m+j]=1;if(i!=1) w[(i-1)*m+j][(i-2)*m+j]=1;}
}int main(){int T,cnt=0;scanf("%d",&T);while(T--){prework();printf("PUZZLE #%d\n",++cnt);gauss();}
}代码2：
/*
POJ 1681
*/#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<iostream>
using namespace std;const int MAXN=300;//有equ个方程，var个变元。增广矩阵行数为equ,分别为0到equ-1,列数为var+1,分别为0到var.
int equ,var;
int a[MAXN][MAXN];//增广矩阵
int x[MAXN];//解集bool free_x[MAXN];//标记是否是不确定的变元
int free_num;//不确定变元个数void Debug(void)
{int i, j;for (i = 0; i < equ; i++){for (j = 0; j < var + 1; j++){cout << a[i][j] << " ";}cout << endl;}cout << endl;
}int Gauss()
{int i,j,k;int max_r;int col;int temp;int free_x_num;int free_index;col=0;for(k=0;k<equ&&col<var;k++,col++){max_r=k;for(i=k+1;i<equ;i++) //选主元{if(abs(a[i][col])>abs(a[max_r][col]))max_r=i;}if(max_r!=k) //选定主元后交换{for(j=col;j<var+1;j++)swap(a[k][j],a[max_r][j]);}if(a[k][col]==0) //x[col]为自由变量{k--;continue;}for(i=k+1;i<equ;i++) //消元{if(a[i][col]!=0){for(j=col;j<var+1;j++)a[i][j]^=a[k][j];}}}for(i=k;i<equ;i++){if(a[i][col]!=0)return -1;//无解}for(i=var-1;i>=0;i--) //解xi{x[i]=a[i][var];for(j=i+1;j<var;j++) //带入第i个方程的其他项x[i]^=(a[i][j]&&x[j]);}return 0;
}int n;void init()
{memset(a,0,sizeof(a));memset(x,0,sizeof(x));memset(free_x, 1, sizeof(free_x)); // 一开始全是不确定的变元.equ=n*n;var=n*n;for(int i=0;i<n;i++)for(int j=0;j<n;j++){int t=i*n+j;a[t][t]=1;if(i>0)a[(i-1)*n+j][t]=1;if(i<n-1)a[(i+1)*n+j][t]=1;if(j>0)a[i*n+j-1][t]=1;if(j<n-1)a[i*n+j+1][t]=1;}
}
char str[20];int main()
{int T;scanf("%d",&T);while(T--){scanf("%d",&n);init();for(int i=0;i<n;i++){scanf("%s",&str);for(int j=0;j<n;j++){if(str[j]=='y')a[i*n+j][n*n]=0;else a[i*n+j][n*n]=1;}}int t=Gauss();if(t==-1){printf("inf\n");continue;}int ans=0;for(int i=0;i<n*n;i++)if(x[i]==1)ans++;printf("%d\n",ans);}return 0;
}
POJ 1681
题意：
一个n*n 的木板 ，每个格子 都 可以 染成 白色和黄色，（ 一旦我们对也个格子染色 ，他的上下左右 都将改变颜色）；
给定一个初始状态 ， 求将 所有的 格子 染成黄色 最少需要染几次？ 若 不能 染成 输出 inf。
/*
POJ 1681
*/#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<iostream>
using namespace std;
const int INF=0x3fffffff;
const int MAXN=300;int a[MAXN][MAXN];//增广矩阵
int x[MAXN]; //解集int free_x[MAXN];//标记是否是不确定的变元
int free_num; //不确定变元个数//高斯消元法解方程组(Gauss-Jordan elimination).
//(-1表示无解，大于0表示结果)
//有equ个方程，var个变元。增广矩阵行数为equ,分别为0到equ-1,列数为var+1,分别为0到var.
int Gauss(int equ,int var)
{int i,j,k;int max_r;//当前这列绝对值最大的行.int col; //当前处理的列int free_index;free_num=0;for(int i=0;i<=var;i++){x[i]=0;free_x[i]=0;}//转换为阶梯阵.col=0; // 当前处理的列for(k = 0;k < equ && col < var;k++,col++){ //枚举当前处理的行.//找到该col列元素绝对值最大的那行与第k行交换.(为了在除法时减小误差)max_r=k;for(i=k+1;i<equ;i++){if(abs(a[i][col])>abs(a[max_r][col])) max_r=i;}if(max_r!=k){// 与第k行交换.for(j=k;j<var+1;j++) swap(a[k][j],a[max_r][j]);}if(a[k][col]==0){// 说明该col列第k行以下全是0了，则处理当前行的下一列.k--;free_x[free_num++]=col;continue;}for(i=k+1;i<equ;i++){// 枚举要删去的行.if(a[i][col]!=0){for(j=col;j<var+1;j++){a[i][j] ^= a[k][j];}}}}// 1. 无解的情况: 化简的增广阵中存在(0, 0, ..., a)这样的行(a != 0).for (i = k; i < equ; i++){ // 对于无穷解来说，如果要判断哪些是自由变元，那么初等行变换中的交换就会影响，则要记录交换.if (a[i][col] != 0) return -1;}int stat=1<<(var-k);//自由变元有 var-k 个int res=INF;for(i=0;i<stat;i++)//枚举所有变元的赋值方案{int cnt=0;free_index=i;for(j=0;j<var-k;j++) //枚举为每一个变元赋值，其值与一个二进制串index对应，而index是对二进制串的枚举{x[free_x[j]]=(free_index&1);if(x[free_x[j]]) cnt++;free_index>>=1;}for(j=k-1;j>=0;j--) //将枚举的值带入其它方程求解{int tmp=a[j][var];for(int l=j+1;l<var;l++)if(a[j][l]) tmp^=x[l];x[j]=tmp;if(x[j])cnt++;}if(cnt<res)res=cnt;}return res;
}int n;void init()
{memset(a,0,sizeof(a));memset(x,0,sizeof(x));memset(free_x, 1, sizeof(free_x)); // 一开始全是不确定的变元.for(int i=0;i<n;i++)for(int j=0;j<n;j++){int t=i*n+j;a[t][t]=1;if(i>0)a[(i-1)*n+j][t]=1;if(i<n-1)a[(i+1)*n+j][t]=1;if(j>0)a[i*n+j-1][t]=1;if(j<n-1)a[i*n+j+1][t]=1;}
}
char str[20];int main()
{int T;scanf("%d",&T);while(T--){scanf("%d",&n);init();for(int i=0;i<n;i++){scanf("%s",str);for(int j=0;j<n;j++){if(str[j]=='y')a[i*n+j][n*n]=0;else a[i*n+j][n*n]=1;}}int t=Gauss(n*n,n*n);if(t==-1){printf("inf\n");continue;}printf("%d\n",t);}return 0;
}补充：注意第85至92行
for(j=k-1;j>=0;j--) //将枚举的值带入其它方程求解
{ int tmp=a[j][var]; for(int l=j+1;l<var;l++)if(a[j][l]) tmp^=x[l]; x[j]=tmp; if(x[j])cnt++;
} for(j=k-1;j>=0;j--) //将枚举的值带入其它方程求解
{int col;for(int l=j;l<var;l++) if(a[j][l]){col=l;break;}//求出的col即是代表当前第j行该解的非自由元变量X[col]int tmp=a[j][var];for(int l=col+1;l<var;l++)if(a[j][l]) tmp^=x[l];x[col]=tmp;if(x[col])cnt++;
}参考：
POJ 1681 Painter's Problem(高斯消元法）
Poj 1222 EXTENDED LIGHTS OUT
http://blog.csdn.net/sdau20163942/article/details/79182813
最后再贴上一个高斯消元模板：高斯消元法（模板）
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;const int MAXN=50;int a[MAXN][MAXN];//增广矩阵
int x[MAXN];//解集
bool free_x[MAXN];//标记是否是不确定的变元/*
void Debug(void)
{int i, j;for (i = 0; i < equ; i++){for (j = 0; j < var + 1; j++){cout << a[i][j] << " ";}cout << endl;}cout << endl;
}
*/inline int gcd(int a,int b)
{int t;while(b!=0){t=b;b=a%b;a=t;}return a;
}
inline int lcm(int a,int b)
{return a/gcd(a,b)*b;//先除后乘防溢出
}// 高斯消元法解方程组(Gauss-Jordan elimination).(-2表示有浮点数解，但无整数解，
//-1表示无解，0表示唯一解，大于0表示无穷解，并返回自由变元的个数)
//有equ个方程，var个变元。增广矩阵行数为equ,分别为0到equ-1,列数为var+1,分别为0到var.
int Gauss(int equ,int var)
{int i,j,k;int max_r;// 当前这列绝对值最大的行.int col;//当前处理的列int ta,tb;int LCM;int temp;int free_x_num;int free_index;for(int i=0;i<=var;i++){x[i]=0;free_x[i]=true;}//转换为阶梯阵.col=0; // 当前处理的列for(k = 0;k < equ && col < var;k++,col++){// 枚举当前处理的行.
// 找到该col列元素绝对值最大的那行与第k行交换.(为了在除法时减小误差)max_r=k;for(i=k+1;i<equ;i++){if(abs(a[i][col])>abs(a[max_r][col])) max_r=i;}if(max_r!=k){// 与第k行交换.for(j=k;j<var+1;j++) swap(a[k][j],a[max_r][j]);}if(a[k][col]==0){// 说明该col列第k行以下全是0了，则处理当前行的下一列.k--;continue;}for(i=k+1;i<equ;i++){// 枚举要删去的行.if(a[i][col]!=0){LCM = lcm(abs(a[i][col]),abs(a[k][col]));ta = LCM/abs(a[i][col]);tb = LCM/abs(a[k][col]);if(a[i][col]*a[k][col]<0)tb=-tb;//异号的情况是相加for(j=col;j<var+1;j++){a[i][j] = a[i][j]*ta-a[k][j]*tb;}}}}// Debug();// 1. 无解的情况: 化简的增广阵中存在(0, 0, ..., a)这样的行(a != 0).for (i = k; i < equ; i++){ // 对于无穷解来说，如果要判断哪些是自由变元，那么初等行变换中的交换就会影响，则要记录交换.if (a[i][col] != 0) return -1;}// 2. 无穷解的情况: 在var * (var + 1)的增广阵中出现(0, 0, ..., 0)这样的行，即说明没有形成严格的上三角阵.// 且出现的行数即为自由变元的个数.if (k < var){// 首先，自由变元有var - k个，即不确定的变元至少有var - k个.for (i = k - 1; i >= 0; i--){// 第i行一定不会是(0, 0, ..., 0)的情况，因为这样的行是在第k行到第equ行.// 同样，第i行一定不会是(0, 0, ..., a), a != 0的情况，这样的无解的.free_x_num = 0; // 用于判断该行中的不确定的变元的个数，如果超过1个，则无法求解，它们仍然为不确定的变元.for (j = 0; j < var; j++){if (a[i][j] != 0 && free_x[j]) free_x_num++, free_index = j;}if (free_x_num > 1) continue; // 无法求解出确定的变元.// 说明就只有一个不确定的变元free_index，那么可以求解出该变元，且该变元是确定的.temp = a[i][var];for (j = 0; j < var; j++){if (a[i][j] != 0 && j != free_index) temp -= a[i][j] * x[j];}x[free_index] = temp / a[i][free_index]; // 求出该变元.free_x[free_index] = 0; // 该变元是确定的.}return var - k; // 自由变元有var - k个.}// 3. 唯一解的情况: 在var * (var + 1)的增广阵中形成严格的上三角阵.// 计算出Xn-1, Xn-2 ... X0.for (i = var - 1; i >= 0; i--){temp = a[i][var];for (j = i + 1; j < var; j++){if (a[i][j] != 0) temp -= a[i][j] * x[j];}if (temp % a[i][i] != 0) return -2; // 说明有浮点数解，但无整数解.x[i] = temp / a[i][i];}return 0;
}
int main(void)
{freopen("in.txt", "r", stdin);freopen("out.txt","w",stdout);int i, j;int equ,var;while (scanf("%d %d", &equ, &var) != EOF){memset(a, 0, sizeof(a));for (i = 0; i < equ; i++){for (j = 0; j < var + 1; j++){scanf("%d", &a[i][j]);}}
// Debug();int free_num = Gauss(equ,var);if (free_num == -1) printf("无解!\n");else if (free_num == -2) printf("有浮点数解，无整数解!\n");else if (free_num > 0){printf("无穷多解! 自由变元个数为%d\n", free_num);for (i = 0; i < var; i++){if (free_x[i]) printf("x%d 是不确定的\n", i + 1);else printf("x%d: %d\n", i + 1, x[i]);}}else{for (i = 0; i < var; i++){printf("x%d: %d\n", i + 1, x[i]);}}printf("\n");}return 0;
}