首页 > 代码库 > [Gauss]POJ1222 EXTENDED LIGHTS OUT
[Gauss]POJ1222 EXTENDED LIGHTS OUT
题意：给一个5*6的矩阵
1代表该位置的灯亮着， 0代表该位置的等没亮
按某个位置的开关，可以同时改变 该位置 以及 该位置上方、下方、左方、右方， 共五个位置的灯的开、关（1->0, 0->1）
问能否将所有的灯关闭 若能 输出需要按哪些地方； 不能输出-1
高斯消元的入门题。
每个位置可以列出一个方程， 列出增广矩阵：
每个位置可以形成增广矩阵的一行， 每行都有30个系数 分别代表（0到29号灯）， 将该位置可以影响到的位置（自己、上、下、左、右）对应的置1， 其余置0
这样就形成了29*29的系数矩阵。
将初始状态置入最后一列 就形成了增广矩阵
接下来只要解方程组即可。
化成约化阶梯后最后一列即为该方程组的解。
P.s. 需要注意的是：因为是矩阵表示的是灯的开关状态，所以解的过程中不应出现0、1以外的其余数字
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <climits> 5 #include <cctype> 6 #include <cmath> 7 #include <string> 8 #include <sstream> 9 #include <iostream> 10 #include <algorithm> 11 #include <iomanip> 12 using namespace std; 13 #include <queue> 14 #include <stack> 15 #include <vector> 16 #include <deque> 17 #include <set> 18 #include <map> 19 typedef long long LL; 20 typedef long double LD; 21 const double pi=acos(-1.0); 22 const double eps=1e-9; 23 #define INF 0x3f3f3f 24 #define lson l, m, rt<<1 25 #define rson m+1, r, rt<<1|1 26 typedef pair<int, int> PI; 27 typedef pair<int, PI > PP; 28 #ifdef _WIN32 29 #define LLD "%I64d" 30 #else 31 #define LLD "%lld" 32 #endif 33 //#pragma comment(linker, "/STACK:1024000000,1024000000") 34 //LL quick(LL a, LL b){LL ans=1;while(b){if(b & 1)ans*=a;a=a*a;b>>=1;}return ans;} 35 //inline int read(){char ch=‘ ‘;int ans=0;while(ch<‘0‘ || ch>‘9‘)ch=getchar();while(ch<=‘9‘ && ch>=‘0‘){ans=ans*10+ch-‘0‘;ch=getchar();}return ans;} 36 //inline void print(LL x){printf(LLD, x);puts("");} 37 //inline void read(LL &ret){char c;int sgn;LL bit=0.1;if(c=getchar(),c==EOF) return ;while(c!=‘-‘&&c!=‘.‘&&(c<‘0‘||c>‘9‘)) c=getchar();sgn=(c==‘-‘)?-1:1;ret=(c==‘-‘)?0:(c-‘0‘);while(c=getchar(),c>=‘0‘&&c<=‘9‘) ret=ret*10+(c-‘0‘);if(c==‘ ‘||c==‘\n‘){ ret*=sgn; return ; }while(c=getchar(),c>=‘0‘&&c<=‘9‘) ret+=(c-‘0‘)*bit,bit/=10;ret*=sgn;} 38 39 int a[35][35]; 40 int x[35]; 41 42 void debug() 43 { 44 for(int i=0;i<30;i++) 45 { 46 for(int j=0;j<=30;j++) 47 printf("%d ", a[i][j]); 48 printf("\n"); 49 } 50 printf("\n"); 51 } 52 53 void Gauss() 54 { 55 for(int k=0, col=0;k<30 && col<30;k++, col++) 56 { 57 int maxr=k; 58 for(int i=k+1;i<30;i++) 59 if(abs(a[i][col])>abs(a[maxr][col])) 60 maxr=i; 61 if(k!=maxr) 62 { 63 for(int j=col;j<=30;j++) 64 swap(a[k][j], a[maxr][j]); 65 // swap(x[k], x[maxr]); 66 } 67 // x[k]/=a[k][col]; 68 // for(int j=col+1;j<30;j++) 69 // a[k][j]/=a[k][col]; 70 // a[k][col]=1; 71 // for(int i=0;i<30;i++) 72 // if(i!=k) 73 // { 74 // x[i]-=x[k]*a[i][col]; 75 // for(int j=col+1;j<30;j++) 76 // a[i][j]-=a[k][j]*a[i][col]; 77 // a[i][col]=0; 78 // } 79 if(a[k][col]==0) 80 { 81 k--; 82 continue; 83 } 84 for(int i=k+1;i<30;i++) 85 if(a[i][col]) 86 for(int j=col;j<=30;j++) 87 a[i][j]^=a[k][j]; 88 // debug(); 89 } 90 for(int i=29;i>=0;i--) 91 { 92 x[i]=a[i][30]; 93 for(int j=i+1;j<30;j++) 94 x[i]^=(a[i][j] && x[j]); 95 } 96 } 97 int main() 98 { 99 // freopen("out.txt", "w", stdout);100 int t, ca=1;101 scanf("%d", &t);102 while(t--)103 {104 memset(a, 0, sizeof(a));105 for(int i=0;i<30;i++)106 scanf("%d", &a[i][30]);107 printf("PUZZLE #%d\n", ca++);108 for(int i=0;i<5;i++)109 for(int j=0;j<6;j++)110 {111 int t=i*6+j;112 a[t][t]=1;113 if(i>0)114 a[(i-1)*6+j][t]=1;115 if(i<4)116 a[(i+1)*6+j][t]=1;117 if(j>0)118 a[i*6+j-1][t]=1;119 if(j<5)120 a[i*6+j+1][t]=1;121 }122 // debug();123 Gauss();124 for(int i=0;i<5;i++)125 for(int j=0;j<6;j++)126 {127 printf("%d", x[i*6+j]);128 if(j==5)129 printf("\n");130 else131 printf(" ");132 }133 }134 return 0;135 }
[Gauss]POJ1222 EXTENDED LIGHTS OUT
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。