首页 > 代码库 > POJ 1222 EXTENDED LIGHTS OUT (高斯消元)
POJ 1222 EXTENDED LIGHTS OUT (高斯消元)
题目链接
题意：5*6矩阵中有30个灯，操作一个灯，周围的上下左右四个灯会发生相应变化 即由灭变亮，由亮变灭，如何操作使灯全灭？
题解：这个问题是很经典的高斯消元问题。同一个按钮最多只能被按一次，因为按两次跟没有按是一样的效果。那么 对于每一个灯，用1表示按，0表示没有按，那么每个灯的状态的取值只能是0或1。列出30个方程，30个变元，高斯消元解出即可，因为解只能是0或者1，所以方程组是一定有解。
代码：
#include <iostream>#include <cstdlib>#include <cstring>#include <cstdio>using namespace std;#define maxn 35int f[maxn][maxn];int g[maxn][maxn];int dir[5][2] ={ { 0, 0 }, { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 }};void debug(){ for (int i =0; i <30; i++) { for (int j =0; j <31; j++) cout <<""<< g[i][j]; cout << endl; } cout << endl;}void input(){ for(int i=0; i<30; i++) scanf("%d",&g[i][30]);}void work(){ int i,j,k,r,n=30; for(i=0; i<n; i++) //i代表(i,i) { r=i; for(j=i; j<n; j++) if(g[j][i]==1) { r=j; break; } //找到一个为1的 if(r!=i) for(j=i; j<=n; j++) //j从i开始就可以 前面都是0 swap(g[r][j],g[i][j]); //现在一定为1 可以用了 for(j=i+1; j<n; j++) if(g[j][i]) //如果是1 异或整行 for(k=i; k<=n; k++) //k从i开始就可以 前面都是0 g[j][k]^=g[i][k]; } //构建上三角完毕 下面开始回代过程 for (int i = n-1; i >=0; i--) { for (int j =29; j > i; j--) g[i][30] ^= (g[i][j] && g[j][30]);//这一行可以参考传统的求解过程来理解 }}void print(){ for(int i=0; i<30; i++) { if((i+1)%6!=0) printf("%d ",g[i][30]); else printf("%d\n",g[i][30]); }}int main(){ //构造初始方阵 这个方法很好理解 for (int i =0; i <5; i++) for (int j =0; j <6; j++) for (int k =0; k <5; k++) { int a = i + dir[k][0]; int b = j + dir[k][1]; if (a >=0&& b >=0&& a <5&& b <6) f[i *6+ j][a *6+ b] =1; } int t; scanf("%d", &t); for (int i =0; i < t; i++) { printf("PUZZLE #%d\n", i +1); memcpy(g, f, sizeof(g)); input(); work(); print(); } return 0;}
POJ 1222 EXTENDED LIGHTS OUT (高斯消元)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。