首页 > 代码库 > POJ 1222 EXTENDED LIGHTS OUT(高斯消元)

POJ 1222 EXTENDED LIGHTS OUT(高斯消元)

2024-07-13 17:26:31   220人阅读

题目链接：http://poj.org/problem?id=1222

题意： 给你一个5 * 6的矩阵，由0和1组成。对于其中一个位置(i, j)进行操作的话，四周4个位置都会操作一次。(注：所谓的操作就是把状态0->1或者1->0)

这个游戏一般人小时候都玩过吧。 最后问你是从一个当前状态转移到目标状态(全是0)需要选择哪几个。

我的做法是高斯消元(刚在学)。

很容易写出第i个方程 : a[i] ^ a[k1] ^ a[k2] ^ a[k3] ^ a[k4] = cur[i]^aim[i] (k1~4 表示的是第i个上下左右四边的标号) a[x] 表示第x个是1还是0

普通的高斯消元方程都是加减乘除的，这里却是异或关系。

但是还是可以消元的，只要把高斯消元过程稍微修改下就行了。

两点:

1) 用 i 行消j(j > i)行时，如果A[j][i]是0的话，那么这一行就不用消了。另外如果A[i][i]是0的话说明无法用这一行消了，直接continue就行。

这是因为这里消的方法是第i行和第j行方程叠加A[i][i] ^ A[j][i] ^ A[i][i+1] ^ A[j][i+1] ... = A[i][n]^A[j][n]

2)在回代的过程中只需要A[i][n] ^= (A[j][n]&&A[i][j]); 这边使用与关系，可以自己体会下。

 

代码：

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cstdlib> 5  6 using namespace std; 7 const int N = 6*6; 8 typedef bool Mat[N][N+1]; 9 const int dir[4][2] = {1, 0, 0, 1, 0, -1, -1, 0};10 int cur[N][N], aim[N][N];11 12 void Guss(Mat &A, int n) {13     for (int i = 0; i < n; i++) {14         int r = i;15         for (int j = i + 1; j < n; j++) {16             if (abs(A[j][i]) > abs(A[r][i])) r = j;17         }18         if (r != i) for (int j = 0; j <= n; j++) swap(A[r][j], A[i][j]);19         for (int j = i + 1; j < n; j++) {20             if (!A[j][i]) continue;21             for (int k = i + 1; k <= n; k++) {22                 A[j][k] ^= A[i][k];23             }24         }25     }26     for (int i = n-1; i >= 0; i--) {27         for (int j = i + 1; j < n; j++) {28             A[i][n] ^= (A[j][n]&&A[i][j]);29         }30     }31 }32 int n = 5, m = 6;33 int change(int x, int y) {34     return m * (x-1) + y - 1;35 }36 void solve() {37     Mat A;38     for (int i = 0; i < n*m; i++) for (int j = 0; j <= n*m; j++) A[i][j] = 0;39 40     for (int i = 1; i <= n; i++) {41         for (int j = 1; j <= m; j++) {42             int c = change(i, j);43             for (int k = 0; k < 4; k++) {44                 int x = i + dir[k][0];45                 int y = j + dir[k][1];46                 if (x <= 0 || x > n || y <= 0 || y > m) continue;47                 A[c][change(x, y)] = 1;48             }49             A[c][c] = 1;50             A[c][n*m] = cur[i][j] ^ aim[i][j];51         }52     }53     Guss(A, n*m);54     for (int i = 0; i < n*m; i++) {55         printf("%d", A[i][n*m]);56         if (i%6 == 5) puts("");57         else printf(" ");58     }59 }60 61 int main() {62     for (int i = 1; i <= n; i++) {63         for (int j = 1; j <= m; j++) {64             aim[i][j] = 0;65         }66     }67     int T; scanf("%d", &T);68     for (int cas = 1; cas <= T; cas++) {69         for (int i = 1; i <= n; i++) {70             for (int j = 1; j <= m; j++) {71                 scanf("%d", &cur[i][j]);72             }73         }74         printf("PUZZLE #%d\n", cas);75         solve();76     }77     return 0;78 }
View Code


联系
我们