本文主要是介绍POJ 1222 EXTENDED LIGHTS OUT，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
高斯消元
题意：
给你一个5*6的矩阵，每个点上都有一个灯，按下f[i][j]的按钮，f[i][j]位置的灯的状态会改变，它上下左右的灯的状态也会改变（开变关，关变开）。
现在给出这个矩阵的初始状态，输出按下哪些按钮，使所有的灯都关闭。
分析：
每个位置可以形成增广矩阵的一行，每行有30个系数分别代表0 -29号灯，将可以影响该位置变换的位置（自己，上，下，左，右）置1，其余的置0；这样就形成了30*30的系数矩阵，将初始状态置入最后一列，就形成了增广矩阵。
高斯消元解矩阵的秩，本题认为有唯一解。
代码：
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std; const int MAXN = 50; //未知数数目
int equ, var; //equ个方程,var个变元
int a[MAXN][MAXN]; //行数为equ，0~var列为系数，var列为得数
int x[MAXN]; //解集
int free_num; //自由变元数量
int free_x[MAXN]; //自由变元，多解枚举时会用到 /*******************************************************
* mod2高斯消元过程
* 返回-1无解，0惟一解，>0自由变元数目
*******************************************************/
int Gauss()
{ int maxr, col, i, j, k; free_num = 0; for (k = 0, col = 0; k<equ && col<var; k++, col++) { maxr = k; for (i = k + 1; i<equ; i++) { if (abs(a[i][col])>abs(a[maxr][col])) maxr = i; } if (a[maxr][col] == 0) { k--; free_x[free_num++] = col; //出现一个自由变元 continue; } if (maxr != k) { for (j = col; j<var + 1; j++) swap(a[k][j], a[maxr][j]); } 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; //无解情况 if (k<var) return var - k; //多个自由变元 for (i = var - 1; i >= 0; i--) //惟一解，进行回代 { x[i] = a[i][var]; for (j = i + 1; j<var; j++) x[i] ^= (a[i][j] && x[j]); } return 0;
} void work()
{ int i, j, k, t; memset(a, 0, sizeof(a)); memset(x, 0, sizeof(x)); equ = 30; var = 30; for (i = 0; i<5; i++) for (j = 0; j<6; j++) { t = i * 6 + j; a[t][t] = 1; //itself if (i > 0) a[(i - 1) * 6 + j][t] = 1; //top if (i < 4) a[(i + 1) * 6 + j][t] = 1; //bottom if (j > 0) a[i * 6 + j - 1] [t] = 1; //left if (j < 5) a[i * 6 + j + 1] [t] = 1; //right } for (i = 0; i < 30; i++) scanf("%d",&a[i][30]); Gauss(); for (i = 0; i < 5; i++) { for (j = 0; j < 5; j++) printf("%d ", x[6 * i + j]); printf("%d\n",x[6*i+5]); }
} int main()
{ int i, T; scanf("%d", &T); for (i = 1; i <= T; i++) { printf("PUZZLE #%d\n", i); work(); } return 0;
} 这篇关于POJ 1222 EXTENDED LIGHTS OUT的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
