zoj 2977 Strange Billboard

zoj 2977 Strange Billboard

#include <iostream>#include <string>#include <cstdio>#include <cstring>#include <cmath>#define ABS( x ) ((x)<0? (-(x)) :(x))#define ty 2using namespace std;const int maxn = 505;int equ, var; int a[maxn][maxn];int x[maxn]; bool free_x[maxn]; int free_num,_b[maxn],step=0,its,ans=100000;void Debug(void){ int i, j; for (i = 0; i < equ; i++) { for (j = 0; j < var + 1; j++) { cout << a[i][j] << " "; } cout << endl; } cout << endl;}inline int gcd(int a, int b){ int t; while (b != 0) { t = b; b = a % b; a = t; } return a;}inline int lcm(int a, int b){ return a * b / gcd(a, b);}int Gauss(void){ int i, j, k; int max_r; int col;  int ta, tb; int LCM; int temp; int free_x_num; int free_index; col = 0;  for (k = 0; k < equ && col < var; k++, col++) {  max_r = k; for (i = k + 1; i < equ; i++) { if (ABS(a[i][col]) > ABS(a[max_r][col])) max_r = i; } if (max_r != k) {  for (j = k; j < var + 1; j++) swap(a[k][j], a[max_r][j]); } if (a[k][col] == 0) {  k--; continue; } for (i = k + 1; i < equ; i++) {  if (a[i][col] != 0) { LCM = lcm(ABS(a[i][col]), ABS(a[k][col])); ta = LCM / ABS(a[i][col]), tb = LCM / ABS(a[k][col]); if (a[i][col] * a[k][col] < 0) tb = -tb; for (j = col; j < var + 1; j++) { if (ty) a[i][j] = (a[i][j] * ta - a[k][j] * tb + ty ) % ty;else a[i][j] = a[i][j] * ta - a[k][j] * tb; } } } } for (i = k; i < equ; i++) {  if (a[i][col] != 0) return -1; } if (k<var) { its=k; return 1; } for (i = var - 1; i >= 0; i--) { temp = a[i][var]; for (j = i + 1; j < var; j++) { if (a[i][j] != 0) temp -= a[i][j] * x[j]; } if (temp % a[i][i] != 0) return -2;  x[i] = temp / a[i][i]; } return 0;}int main(void){ int i, j; int m,n; while (scanf("%d%d",&m,&n)!=EOF,n&&m) { memset(a, 0, sizeof(a)); memset(x, 0, sizeof(x)); memset(free_x, 1, sizeof(free_x)); char _str[25][25]; for (int i=0;i<m;i++) scanf("%s",_str[i]); for (int i=0;i<m;i++) for (int j=0;j<n;j++) _b[n*i+j]=(_str[i][j]=='X'); equ=m*n; for (int i=0;i<m;i++) for (int j=0;j<n;j++) { int tmp=n*i+j; if (i>0) a[tmp][(i-1)*n+j]=1; if (j>0) a[tmp][i*n+j-1]=1; if (i+1<m) a[tmp][(i+1)*n+j]=1; if (j+1<n) a[tmp][i*n+j+1]=1; a[tmp][tmp]=1; } var=equ; for (int i=0;i<equ;i++) a[i][equ]=_b[i]; free_num = Gauss(); if (free_num==-1) { cout<<"Damaged billboard."<<endl; continue; } if (free_num==0) { int _ans=0; for (int i=0;i<equ;i++) _ans+=x[i]&1; printf("You have to tap %d tiles.n",_ans); continue; } ans=1000000; if (free_num>0) { int k=its; int _tmp=(1<<(var-k)) ; for (int state=0;state<_tmp;state++) { for (int i=k;i<equ;i++) { if ((state>>((var-i-1))) & 1) { a[i][i]=1; a[i][equ]=1; }else { a[i][i]=1; a[i][equ]=0; } } if (!Gauss()) { int _ans=0; for (int i=0;i<equ;i++) _ans+=x[i]&1; if (_ans<ans) ans=_ans; } } } printf("You have to tap %d tiles.n",ans); } return 0;}