POJ 1222 - EXTENDED LIGHTS OUT

http://poj.org/problem?id=1222

概要

6 * 5 のマス目があり，各マスにはライトがある．

あるマスに触れるとそのマスと隣接する4マスのライトのオンオフが入れ替わる．

各マスのライトのオンオフの初期状態が与えられるので，すべてのライトをオフにするために触れるべきマスを答える．

制約

特になし

解法

AOJ 2140 - Tile Puzzle と同様．

  1 #include <cstdio>
  2 #include <vector>
  3 using namespace std;
  4 
  5 struct mod
  6 {
  7   int m;
  8   mod(int a) : m(a) {}
  9   int operator()(int x) const { return ((x%m)+m)%m; }
 10 };
 11 
 12 static mod M(2);
 13 int inv_tbl[2] = {-1, 1};
 14 
 15 vector<int> gaussian_elimination(vector<vector<int> > a, vector<int> b)
 16 {
 17   const int N = a.size();
 18   vector<int> sigma(N);
 19   for (int i = 0; i < N; i++) {
 20     sigma[i] = i;
 21   }
 22 
 23   for (int i = 0; i < N; i++) {
 24     for (int j = i+1; a[i][i] == 0 && j < N; j++) {
 25       swap(a[i], a[j]);
 26       swap(b[i], b[j]);
 27       swap(sigma[i], sigma[j]);
 28     }
 29     if (a[i][i] == 0) {
 30       continue;
 31     }
 32 
 33     const int t = inv_tbl[a[i][i]];
 34     for (int k = i; k < N; k++) {
 35       a[i][k] = M(a[i][k] * t);
 36     }
 37     b[i] = M(b[i] * t);
 38 
 39     for (int j = 0; j < N; j++) {
 40       if (i == j) {
 41         continue;
 42       }
 43       const int u = a[j][i];
 44       for (int k = i; k < N; k++) {
 45         a[j][k] = M(a[j][k] - u*a[i][k]);
 46       }
 47       b[j] = M(b[j] - u*b[i]);
 48     }
 49   }
 50 
 51   for (int i = 0; i < N; i++) {
 52     if (a[sigma[i]][sigma[i]] == 0 && b[sigma[i]] != 0) {
 53       return vector<int>();
 54     }
 55   }
 56   return b;
 57 }
 58 
 59 int main()
 60 {
 61   int T;
 62   scanf("%d", &T);
 63   for (int Ti = 1; Ti <= T; Ti++) {
 64     vector<vector<int> > a(30, vector<int>(30, 0));
 65     for (int i = 0; i < 5; i++) {
 66       for (int j = 0; j < 6; j++) {
 67         for (int d = 0; d < 5; d++) {
 68           static const int di[] = {0, -1, 1, 0, 0};
 69           static const int dj[] = {0, 0, 0, -1, 1};
 70           const int k = i+di[d];
 71           const int l = j+dj[d];
 72           if (0 <= k && k < 5 && 0 <= l && l < 6) {
 73             a[6*i+j][6*k+l] = 1;
 74           }
 75         }
 76       }
 77     }
 78     vector<int> b(30);
 79     for (int i = 0; i < 30; i++) {
 80       scanf("%d", &b[i]);
 81     }
 82 
 83     const vector<int> x = gaussian_elimination(a, b);
 84     printf("PUZZLE #%d\n", Ti);
 85     if (x.empty()) {
 86       throw "fail";
 87     } else {
 88       for (int i = 0; i < 5; i++) {
 89         for (int j = 0; j < 6; j++) {
 90           if (j != 0) {
 91             putchar(' ');
 92           }
 93           printf("%d", x[6*i+j]);
 94         }
 95         putchar('\n');
 96       }
 97     }
 98   }
 99   return 0;
100 }