本文主要是介绍POJ 1222 EXTENDED LIGHTS OUT 枚举 || 高斯消元，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意就不说了，就是把棋盘上的1全变0即可
如果枚举的话，看似有2的30次方中可能，其实不是。
实际上只需要枚举第一行的状态即可，再往后，如果想要解决问题，必须根据第一行的状态推下去。
对于每个位置，如果上一行的这一列有1，必然这个按键要按下去，不然不可能达到要求的结果。
枚举代码如下，直接使用二进制枚举
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <map>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 100007
#define INF 1000000000
#define eps 1e-7
using namespace std;
int a[5][6], mx, flag, mi, ta[5][6];
int tmp[5][6];
void press(int i, int j)
{ta[i][j] = !ta[i][j];if(i > 0) ta[i - 1][j] = !ta[i - 1][j];if(j > 0) ta[i][j - 1] = !ta[i][j - 1];if(i < 4) ta[i + 1][j] = !ta[i + 1][j];if(j < 5) ta[i][j + 1] = !ta[i][j + 1];
}
bool ok()
{for(int i = 0; i < 6; i++)if(ta[4][i]) return false;return true;
}
void output()
{for(int i = 0; i < 5; i++){for(int j = 0; j < 6; j++){if(j) printf(" ");printf("%d", tmp[i][j]);}printf("\n");}
}
void solve()
{for(int k = 0; k < 64; k++){for(int i = 0; i < 5; i++)for(int j = 0; j < 6; j++)ta[i][j] = a[i][j];memset(tmp, 0, sizeof(tmp));for(int j = 0; j < 6; j++)if(k & (1 << j)) {press(0, j); tmp[0][j] = 1;}for(int i = 1; i < 5; i++)for(int j = 0; j < 6; j++)if(ta[i - 1][j]){tmp[i][j] = 1;press(i, j);}if(ok()){output(); return;}}
}
int main()
{int T, cas = 0;scanf("%d", &T);while(T--){for(int i = 0; i < 5; i++)for(int j = 0; j < 6; j++)scanf("%d", &a[i][j]);printf("PUZZLE #%d\n", ++cas);solve();}return 0;
}再然后就是高斯消元了。
建立方程组的过程参考了http://hi.baidu.com/ofeitian/blog/item/9385662a30c2ebf7e7cd4016.html
不得不说这是一种逆向思想，题目要求是怎样能全灭掉，建立方程则是求解怎样能从全灭转变到当前状态，实际上，由于一个灯摁两次的效果是一样的，所以这样求出来的解就是最终解。
然后求解的时候，最好还是用异或操作。这样就避免出现了负数和特别巨大的数字。经试验，这是很有可能的。
这就是用高斯消元法求异或方程组了
异或方程组就是形如这个样子的方程组：
M[0][0]x[0]^M[0][1]x[1]^…^M[0][N-1]x[N-1]=B[0]
M[1][0]x[0]^M[1][1]x[1]^…^M[1][N-1]x[N-1]=B[1]
…
M[N-1][0]x[0]^M[N-1][1]x[1]^…^M[N-1][N-1]x[N-1]=B[N-1]
其中“^”表示异或(XOR, exclusive or)，M[i][j]表示第i个式子中x[j]的系数，是1或者0。B[i]是第i个方程右端的常数，是1或者0。
解这种方程可以套用高斯消元法，只须将原来的加减操作替换成异或操作就可以了，两个方程的左边异或之后，它们的公共项就没有了。
具体的操作方法是这样的：对于k=0..N-1，找到一个M[i][k]不为0的行i，把它与第k行交换，用第k行去异或下面所有M[i][j]不为0的行i，消去它们的第k个系数，这样就将原矩阵化成了上三角矩阵；最后一行只有一个未知数，这个未知数就已经求出来了，用它跟上面所有含有这个未知数的方程异或，就小觑了所有的着个未知数，此时倒数第二行也只有一个未知数，它就被求出来了，用这样的方法可以自下而上求出所有未知数。
我就是根据这个来求的
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <map>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 100007
#define INF 1000000000
#define eps 1e-7
using namespace std;
int a[10][10];
int d[33][33], ans[33];
int n;
int gauss()
{int pos;for(int k = 0; k < n; k++){pos = -1;for(int i = k; i < n; i++) //找到这一列中第一个非0元素的行if(d[i][k] != 0){pos = i; break; }for(int i = k; i <= n; i++)swap(d[k][i], d[pos][i]); //交换位置，我们在学线性代数的时候也经常这么做for(int i = k + 1; i < n; i++){if(d[i][k] == 0) continue; for(int j = k; j <= n; j++) //对于下面出现的这一列中有1的行，需要把1消掉d[i][j] ^= d[k][j];}}for(int i = n - 1; i >= 0; i--){for(int j = 0; j < i; j++){if(d[j][i] == 0) continue;for(int k = 0; k <= n; k++)d[j][k] ^= d[i][k];}int flag = 0;for(int j = 0; j < n; j++)if(d[i][j]) flag = 1; if(!flag) return 0; //如果某一行的系数全是0，说明就不对了ans[i] = d[i][n];}for(int i = 0; i < 5; i++)for(int j = 0; j < 6; j++){printf("%d",ans[i * 6 + j]);if(j == 5) printf("\n");else printf(" ");}return 1;
}int main()
{int T, cas = 0;scanf("%d", &T);n = 30;while(T--){memset(d,0,sizeof(d));for(int i = 0; i < 5; i++)for(int j = 0; j < 6; j++){scanf("%d",&a[i][j]);if(a[i][j]) d[6 * i + j][n] = 1;}for(int i = 0; i < 5; i++)for(int j = 0; j < 6; j++){d[6 * i + j][6 * i + j] = 1;if(i > 0) d[6 * i + j][6 * (i - 1) + j] = 1;if(j > 0) d[6 * i + j][6 * i + j - 1] = 1;if(i < 4) d[6 * i + j][6 * (i + 1) + j] = 1;if(j < 5) d[6 * i + j][6 * i + j + 1] = 1;}printf("PUZZLE #%d\n", ++cas);gauss();}return 0;
}
这篇关于POJ 1222 EXTENDED LIGHTS OUT 枚举 || 高斯消元的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
