題目大意:給一個5*6的01矩陣,0表示燈暗的,1表示燈亮著。矩陣中每個位置表示一個按鈕,當按鈕按動時它周圍(上下左右)的燈變成相反的狀態。問怎麼按可以將所有的燈都變成暗的。
解題思路:這類開關問題算比較經典的高斯消元題了,做這題時我能想到怎麼建立那個矩陣,但後面的那個解不知道如何求,線代老師死得早啊。
每個燈最後的狀態都只由自己和旁邊的按鈕決定。有30盞燈,每種燈最後的狀態是0,那麼最初始的狀態若是0,則中間動它的則必須為偶數次,否則為奇數次。我們設30個方程,每個方程等號右邊的值模2就等於矩陣裡對應的值。這樣初始時矩陣裡的值都是0,如果某些點能影響這個點,那麼那幾個點就標記為1。這樣每個點都對應一個未知量,最後的值為0或1。
矩陣構造出來之後,稍微修改下高斯消元的模板就可以過了。因為這題很特殊解中只有0和1,所以只要用用幾個位操作就好。
測試數據:
1
0 1 1 0 1 0
1 0 0 1 1 1
0 0 1 0 0 1
1 0 0 1 0 1
0 1 1 1 0 0
Out:
PUZZLE #1
1 0 1 0 0 1
1 1 0 1 0 1
0 0 1 0 1 1
1 0 0 1 0 0
0 1 0 0 0 0
C艹代碼:
[cpp]
<span style="color:#ff0000;">#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MOD 2
#define MAX 35
int n,m,x[MAX];
int arr[MAX][MAX];
int mat[MAX][MAX];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
void Initial() {
int i,j,k,row,col;
n = m = 5 * 6;
memset(mat,0,sizeof(mat));
for (i = 0; i < 5; ++i)
for (j = 0; j < 6; ++j) {
row = i * 6 + j;
mat[row][row] = 1;
mat[row][m] = arr[i][j];
for (k = 0; k < 4; ++k) {
int ii = dir[k][0] + i;
int jj = dir[k][1] + j;
if (ii >= 0 && ii < 5
&& jj >=0 && jj < 6)
mat[row][ii*6+jj] = 1;
}
}
}
int Gcd(int x,int y) {
int r = x % y;
while (r) {
x = y,y = r;
r = x % y;
}
return y;
}
int Lcm(int x,int y) {
return x / Gcd(x,y) * y;
}
void Gauss_AC() {
int i,j,row,max_r,col;
int ta,tb,temp,LCM;
row = col = 0;
for (; row < n && col < m; ++row,++col) {
max_r = row;
for (j = row + 1; j < n; ++j)
if (mat[j][col]) {
max_r = j;
break;
}
if (mat[max_r][col] == 0) {
row--;
continue;
}
if (row != max_r)
for (j = col; j <= m; ++j)
swap(mat[row][j],mat[max_r][j]);
for (i = row + 1; i < n; ++i) //將每一行的首元素消成0,故要用row行去異或i行
if (mat[i][col]) for (j = col; j <= m; ++j)
mat[i][j] ^= mat[row][j];
}
for (i = m - 1; i >= 0; --i) {
x[i] = mat[i][m]; //mat[i][i]為1,那麼mat[i][m]和其他列的和就必須為0故用異或,如果異或為1則x[i]為1
for (j = i + 1; j < m; ++j)
x[i] ^= (mat[i][j] && x[j]);
}
}
int main()
{
int i,j,k,t,cas = 0;
scanf("%d",&t);
while (t--) {
for (i = 0; i < 5; ++i)
for (j = 0; j < 6; ++j)
scanf("%d",&arr[i][j]);
Initial();
Gauss_AC();
printf("PUZZLE #%d\n",++cas);
for (i = 0; i < m; ++i)
printf("%d%c",x[i],(i%6)==5?'\n':' ');
}
}
</span>