关灯游戏源代码（更新）

/*The code to turn off all bulbs in a matrix of bulbs */ #include <stdio.h> #include <stdlib.h> #include <string.h> typedef char ** MATRIX; typedef char * VECTOR; typedef char *const* CONST_MATRIX; typedef const char * CONST_VECTOR; MATRIX matrix_alloc2(int n, int m){ MATRIX x= (MATRIX)malloc(sizeof(char *)*n+sizeof(char)*n*m); int i; x[0]=(char *)(x+n); for(i=1;i<n;i++)x[i]=x[i-1]+m; return x; } int maxtrix_count_one(MATRIX x,int n, int m){ int r=0; int i,j; for(i=0;i<n;i++)for(j=0;j<n;j++)if(x[i][j]!=0)r++; return r; } MATRIX matrix_alloc(int n){ MATRIX x = (MATRIX)malloc(sizeof(char *)*n+sizeof(char)*n*n); int i; x[0]=(char *)(x+n); for(i=1;i<n;i++)x[i]=x[i-1]+n; return x; } void matrix_free(MATRIX x){ free(x); } VECTOR vector_alloc(int n){ VECTOR x = (VECTOR)malloc(sizeof(char)*n); return x; } void vector_free(VECTOR x){ free(x); } void matrix_sum(MATRIX A, CONST_MATRIX B, int n){ int i,j; for(i=0;i<n;i++){ for(j=0;j<n;j++){ A[i][j] ^= B[i][j]; } } } void vector_sum(VECTOR a, CONST_VECTOR b, int n){ int i; for(i=0;i<n;i++)a[i]^=b[i]; } void matrix_mul(MATRIX out, CONST_MATRIX in1, CONST_MATRIX in2, int n){ int i,j,k; for(i=0;i<n;i++)for(j=0;j<n;j++){ int sum=0; for(k=0;k<n;k++){ if(in1[i][k]) sum^=in2[k][j]; } out[i][j]=sum; } } void matrix_mul_H(MATRIX out, CONST_MATRIX in, int n){ int i,j; for(i=0;i<n;i++)for(j=0;j<n;j++){ int sum=in[i][j]; if(i>0)sum^=in[i-1][j]; if(i<n-1)sum^=in[i+1][j]; out[i][j]=sum; } } void matrix_mul_vector(VECTOR out, CONST_MATRIX m, CONST_VECTOR in, int n){ int i,j; for(i=0;i<n;i++){ int sum=0; for(j=0;j<n;j++){ sum^=m[i][j]&in[j]; } out[i]=sum; } } void H_mul_vector(VECTOR out, CONST_VECTOR in, int n){ int i; for(i=0;i<n;i++){ int sum=in[i]; if(i>0)sum^=in[i-1]; if(i<n-1)sum^=in[i+1]; out[i]=sum; } } void vector_init_const(VECTOR v, char c, int n){ int i; for(i=0;i<n;i++)v[i]=c; } void matrix_init_O(MATRIX o, int n){ int i,j; for(i=0;i<n;i++)for(j=0;j<n;j++)o[i][j]=0; } void matrix_init_const(MATRIX m, char c, int n1, int n2){ int i,j; for(i=0;i<n1;i++)for(j=0;j<n2;j++)m[i][j]=c; } void matrix_init_E(MATRIX e, int n){ int j; matrix_init_O(e,n); for(j=0;j<n;j++)e[j][j]=1; } void matrix_init_H(MATRIX h, int n){ int i; matrix_init_O(h,n); for(i=0;i<n;i++){ if(i>=1)h[i][i-1]=1; h[i][i]=1; if(i<n-1)h[i][i+1]=1; } } void matrix_copy(MATRIX m, CONST_MATRIX k, int n){ int i,j; for(i=0;i<n;i++)for(j=0;j<n;j++)m[i][j]=k[i][j]; } void matrix_copy2(MATRIX m, CONST_MATRIX k, int n1, int n2){ int i,j; for(i=0;i<n1;i++)for(j=0;j<n2;j++)m[i][j]=k[i][j]; } void vector_copy(VECTOR v, CONST_VECTOR w, int n){ int i; for(i=0;i<n;i++)v[i]=w[i]; } void matrix_output2(CONST_MATRIX m, int n1, int n2){ int i,j; for(i=0;i<n1;i++){ for(j=0;j<n2;j++){ printf("%d",m[i][j]); } printf("\n"); } } void matrix_output(CONST_MATRIX m, int n){ int i,j; for(i=0;i<n;i++){ for(j=0;j<n;j++){ printf("%d",m[i][j]); } printf("\n"); } } void vector_output(VECTOR v, int n){ int i; for(i=0;i<n;i++)printf("%d",v[i]); printf("\n"); } void Usage(const char *program_name){ printf("Usage:\n"); printf("\t$%s n\n",program_name); printf("\t\twhere n is a positive integer no more than 1000\n"); printf("Or\n"); printf("\t$%s [0|1]* [0|1]* ... [0|1]*\n", program_name); printf("\t\tIn this format, there're n strings of 0 and 1 and length of each string is n too\n"); printf("The program assumes there're an n*n array. Each cell in the array has a switch " "and a light. On touches of the switch in a cell will changes the state of the " "light in the cell as well as the lights in the neighbors of the cell, so that " "one switch could change states of 5 lights at most\n"); printf("The program will try to find a solution to turn all lights off\n"); printf("The first format of input gives an initial n*n array with all lights on\n"); printf("The second format requires n strings of 0 and 1, and the length of each string" " is n too. Each string is correspondent to state of lights in one line of the " "array. A digit 0 means the correspondent light is off and 1 means the light is " "on.\n"); printf("The program will output an n*n matrix of 0 and 1 when there's a solution which " "tells whether we need to touch a switch to turn off all the lights\nOr the " "program will output \"NO SOLUTION\" when there's no solution\n"); exit(-1); } MATRIX P0,P1,H; VECTOR ME; MATRIX init; //First we need to solve equation P*X(n) = ME; //There could be multiple solutions //For each solution X(n), try //X(n-1) = INIT+ H*X(n); //X(K) = INIT + H*X(k+1)+X(k+2);//for k<n-1 void Solve(MATRIX P, VECTOR ME, int n, int m) { int *freedom_index; int freedom_count=0; int i,j,k,t; int failed=0; freedom_index = (int *)malloc(sizeof(int)*m); //First solve equition P*X(n) = ME for(i=0,t=0;i<m;i++){ for(j=t;j<m;j++)if(P[j][i]==1)break; if(j==m){ //find a freedom factor freedom_index[freedom_count++]=i; }else{ if(j!=t){ //Swap line j and t int temp; for(k=i;k<m;k++){ temp=P[t][k]; P[t][k]=P[j][k]; P[j][k]=temp; } temp = ME[t]; ME[t] = ME[j]; ME[j] = temp; } for(j=0;j<m;j++){ if(j!=t&&P[j][i]){ //If P[j][i] is 1, add Line i into Line j for(k=i;k<m;k++){ P[j][k]^=P[t][k]; } ME[j]^=ME[t]; } } t++; } } for(;t<m;t++){ if(ME[t]!=0){ failed=1; break; } } fprintf(stderr,"Freedom factor = %d\n", freedom_count); if(failed){ printf("NO SOLUTION\n"); free(freedom_index); return; } if(freedom_count>0){ int delta=freedom_count; for(k=m-1,t=freedom_count-1;k>=0&&delta>0;k--){ if(k==freedom_index[t]){ int i; for(i=0;i<m;i++)P[k][i]=0; ME[k]=0; delta--;t--; }else if(delta>0){ for(i=0;i<m;i++)P[k][i]=P[k-delta][i]; ME[k]=ME[k-delta]; } } } //Now ME hold's one solution for X[n], //And random reset index inside freedom_index of ME to 0, 1 // will result in another solution for X[n]; //Output one solution #ifdef _DEBUG printf("ME:");vector_output(ME, m);printf("\n"); printf("H:\n");matrix_output(H,m); printf("init:\n"); matrix_output(init,m); #endif if(freedom_count>=20)freedom_count=20;//do not search too much int u; int best_one_count=n*m+1; MATRIX bm=matrix_alloc2(n,m); for(u=0;u<1<<freedom_count;u++) { MATRIX x=matrix_alloc2(n,m); vector_copy(x[n-1],ME,m); for(k=0;k<freedom_count;k++){ if(u&(1<<k)){ x[n-1][freedom_index[k]]=1; for(i=0;i<m;i++){ if(P[i][freedom_index[k]]!=0){ x[n-1][i]^=1; } } }else{ x[n-1][freedom_index[k]]=0; } } matrix_mul_vector(x[n-2],H,x[n-1],m); vector_sum(x[n-2],init[n-1],m); for(k=n-3;k>=0;k--){ H_mul_vector(x[k],x[k+1],m); #ifdef _DEBUG printf("x[%d] 1:",k);vector_output(x[k],m);printf("\n"); #endif vector_sum(x[k],init[k+1],m); #ifdef _DEBUG printf("x[%d] 2:",k);vector_output(x[k],m);printf("\n"); #endif vector_sum(x[k],x[k+2],m); #ifdef _DEBUG