首先对于每一个格子的状态，可能会对它造成影响的是其自身和周围4个格子，这五个格子被按下的总次数也就等于该格子所改变的总次数。
对于任意一个格子，如果这个格子改变了偶数次状态，则等价于没有发生改变。
我们可以将1看作格子亮着，0看作格子暗着，每改变1次就加1，最后格子的状态等于其总数值 MOD 2。
则其运算结果刚好满足异或运算，即每改变一次等于状态值 xor 1。
同样的对于一个格子和它周围的4个格子来说，若格子被按下偶数次，它自身和周围4个格子的状态也等于没有发生改变。所以我们可以知道：任意一个格子至多被按下一次。
假设有数组x[1..30]，分别表示这30个格子是否按下1次，若按下则x[i]=1，否则x[i]=0。
则对于1个格子，他最后的状态为：
当前状态 = 初始状态 xor (a[1] * x[1]) xor (a[2] * x[2]) xor ... xor (a[30] * x[30])其中a[i]表示格子i是否会对当前格子产生影响，若能够则a[i] = 1，否则a[i] = 0
对方程进行变换有：
(a[1] * x[1]) xor (a[2] * x[2]) xor ... xor (a[30] * x[30]) = 当前状态 xor 初始状态因为我们的目标是要让所有等格子都为亮的状态，故我们需要让 当前状态 = 1，则：
(a[1] * x[1]) xor (a[2] * x[2]) xor ... xor (a[30] * x[30]) = 1 xor 初始状态不妨设y = 1 xor 初始状态：
(a[1] * x[1]) xor (a[2] * x[2]) xor ... xor (a[30] * x[30]) = y对于所有的格子，我们可以连立出方程组：
(a[ 1][1] * x[1]) xor (a[ 1][2] * x[2]) xor ... xor (a[ 1][30] * x[30]) = y[ 1] (a[ 2][1] * x[1]) xor (a[ 2][2] * x[2]) xor ... xor (a[ 2][30] * x[30]) = y[ 2] ... (a[30][1] * x[1]) xor (a[30][2] * x[2]) xor ... xor (a[30][30] * x[30]) = y[30]到此，我们的目标就是求出一个x[1..30]，使得上面的方程组成立。
小Ho：这个看上去和高斯消元很像啊。
小Hi：没错，这个方程组叫异或方程组，它可以用和高斯消元同样的方法来解决。
其解答过程几乎和高斯消元无异，判定无解和多解的方式也相同。唯一需要注意的是消元过程不再是高斯消元的加减，而是通过xor运算来进行消元。比如消除第j行第i列的1：
a[j][k] = a[j][k] xor a[i][k], y[j] = y[j] xor y[i]其原理是：
(a[j][1] * x[1]) xor (a[j][2] * x[2]) xor ... xor (a[j][30] * x[30]) xor (a[i][1] * x[1]) xor (a[i][2] * x[2]) xor ... xor (a[ i][30] * x[30]) = y[j] xor y[i] <=> ((a[j][1] * x[1]) xor (a[i][1] * x[1])) xor (((a[j][2] * x[2]) xor (a[i][2] * x[2]))) xor ... xor ((a[j][30] * x[30]) xor (a[i][30] * x[30])) = y[j] xor y[i] <=> ((a[j][1] xor a[i][1]) * x[1]) xor ((a[j][2] xor a[i][2]) * x[2]) xor ... ((a[j][30] xor a[i][30]) * x[30]) = y[j] xor y[i]而且由于给定游戏板是固定的，我们可以知道a[i][j]矩阵一定是固定的，而且通过计算可以知道我们消元得到的上三角矩阵也是固定的，并且在这一次的问题中该上三角矩阵是满秩的，所以其一定存在唯一解。
所以我们一定有办法完成这个游戏。
#include <set> #include <stack> #include <queue> #include <cmath> #include <cstdio> #include <string> #include <cstring> #include <iostream> #include <algorithm> using namespace std; //#pragma comment(linker, "/STACK:1024000000,1024000000") #define FIN freopen("input.txt","r",stdin) #define FOUT freopen("output.txt","w",stdout) #define fst first #define snd second //typedef __int64 LL; typedef long long LL; typedef pair<int, int> PII; const double eps = 1e-6; const int MAXN = 50 + 5; int T, N, M, K; const int row = 5; const int col = 6; char buf[15]; struct Gauss { // 等式的个数和变元的个数 int equ, var; // 系数矩阵 int a[MAXN][MAXN]; // 常数列 int b[MAXN]; // 答案 int x[MAXN]; void init() { equ = row * col, var = row * col; for (int i = 1; i <= var; i++) { int x1, y1, x2, y2; x1 = (i - 1) / col + 1; y1 = (i - 1) % col + 1; for (int j = 1; j <= var; j++) { x2 = (j - 1) / col + 1; y2 = (j - 1) % col + 1; if (x1 == x2 && abs(y1 - y2) <= 1 || y1 == y2 && abs(x1 - x2) <= 1) a[i][j] = 1; else a[i][j] = 0; } } } void read() { for (int i = 1, k = 1; i <= row; i++) { scanf("%s", buf); for (int j = 0; buf[j]; j++, k++) { b[k] = (buf[j] - '0') ^ 1; } } } void chg_row(int r1, int r2) { for (int i = 1; i <= var; i++) { swap(a[r1][i], a[r2][i]); } swap(b[r1], b[r2]); } int run() { int ret = 0; // 处理出上三角矩阵 for (int i = 1; i <= var; i++) { // 从第i行开始，找到第i列不等于0的行j for (int j = i; j <= equ; j++) { if (a[j][i] != 0) { chg_row(i, j); break; } } // 消除第i+1行到第M行的第i列 for (int j = i + 1; j <= equ; j++) { // 这个条件不能少啊! if (a[j][i] == 0) continue; for (int k = 1; k <= var; k++) { a[j][k] ^= a[i][k]; } b[j] ^= b[i]; } } // 必定存在唯一解 // 由于每一行都比前一行少一个系数，所以在M行中只有前N行有系数 // 解析来从第N行开始处理每一行的解 for (int i = var; i >= 1; i--) { // 利用已经计算出的结果，将第i行中第i+1列至第N列的系数消除 for (int j = i + 1; j <= var; j++) { b[i] ^= a[i][j] * x[j]; a[i][j] = 0; } x[i] = b[i]; if (x[i]) ret ++; } return ret; } } gauss; int main() { #ifndef ONLINE_JUDGE FIN; #endif // ONLINE_JUDGE gauss.init(); gauss.read(); int a, b, ret; ret = gauss.run(); printf("%d\n", ret); for (int i = 1; i <= gauss.var; i++) { if (!gauss.x[i]) continue; a = (i - 1) / col + 1; b = (i - 1) % col + 1; printf("%d %d\n", a, b); } return 0; }