AOJ 2140 - Tile Puzzle

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2140

概要

N * N のタイルがあり，最初すべてのタイルの色は 0 である．

あるタイルに触れると，そのタイルと隣接する8マスのタイルの色が1つ進む． タイルの色は 7 種類で，色 6 の次は色 0 になる． また，一番上のマスと一番下のマスは隣接しているとし，同様に一番左のマスと一番右のマスも隣接しているとする．

最終的な色の配置が与えられるので，どのマスを何回触れればよいかを答える． ただし，そのような配置にすることができない場合は -1 のみを出力する．

制約

解法

いわゆる Lights Out とか Flip It と呼ばれるゲーム．

マス (i, j) に触れる回数を x[i,j]，最終的な色を a[i,j] とすると，N*N 個の一次方程式が立つので，連立方程式とみて有限体 F_7 の上でガウスの消去法で解くことで求めることができる．

なぜか AOJ でジャッジができないので，2008/Practice/夏合宿 - ACM-ICPC Japanese Alumni Group からインプットを取ってきて手元で確認した．

 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(7);
13 int inv_tbl[7] = {-1, 1, 4, 5, 2, 3, 6};
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 N;
62   while (scanf("%d", &N) != EOF && N != 0) {
63     const mod K(N);
64     vector<vector<int> > a(N*N, vector<int>(N*N, 0));
65     for (int i = 0; i < N; i++) {
66       for (int j = 0; j < N; j++) {
67         for (int k = -1; k <= 1; k++) {
68           for (int l = -1; l <= 1; l++) {
69             a[N*i+j][N*K(i+k)+K(j+l)] = 1;
70           }
71         }
72       }
73     }
74     vector<int> b(N*N);
75     for (int i = 0; i < N*N; i++) {
76       scanf("%d", &b[i]);
77     }
78 
79     const vector<int> x = gaussian_elimination(a, b);
80     if (x.empty()) {
81       puts("-1");
82     } else {
83       for (int i = 0; i < N; i++) {
84         for (int j = 0; j < N; j++) {
85           if (j != 0) {
86             putchar(' ');
87           }
88           printf("%d", x[N*i+j]);
89         }
90         putchar('\n');
91       }
92     }
93     putchar('\n');
94   }
95   return 0;
96 }
aoj/2140.cc