UVA 1560 - Extended Lights Out(高斯消元)

UVA 1560 - Extended Lights Out

題目鏈接

題意：給定一個矩陣，1代表開著燈，0代表關燈，沒按一個開關，周圍4個位置都會變化，問一個按的方法使得所有燈都變暗

思路：兩種做法：
1、枚舉遞推
這個比較簡單，就枚舉第一行，然後遞推過去，每次如果上一行是亮燈，則下一行開關必須按下去

2、高斯消元，
這個做法比較屌一些，每個位置對應上下左右中5個位置可以列出一個異或表達式，然後30個位置對應30個異或表達式，利用高斯消元法就能求出每個位置的解了

代碼：

高斯消元法：

#include 
#include 
#include 
using namespace std;

const int d[5][2] = {{0, 0}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int t, a[31][31], out[6][6];

void back() {
    for (int i = 29; i >= 0; i--)
	out[i / 6][i % 6] = a[i][30];
}

void guess() {
    for (int i = 0; i < 30; i++) {
	int k = i;
	for (; k < 30; k++)
	    if (a[k][i]) break;
	for (int j = 0; j <= 30; j++)
	    swap(a[i][j], a[k][j]);
	for (int j = 0; j < 30; j++) {
	    if (i == j) continue;
	    if (a[j][i]) {
		for (int k = i; k <= 30; k++)
		    a[j][k] ^= a[i][k];
	    }
	}
    }
    back();
}

int main() {
    int cas = 0;
    scanf("%d", &t);
    while (t--) {
	memset(a, 0, sizeof(a));
	for (int i = 0; i < 30; i++)
	    scanf("%d", &a[i][30]);
	for (int i = 0; i < 30; i++) {
	    int x = i / 6, y = i % 6;
	    for (int j = 0; j < 5; j++) {
		int xx = x + d[j][0];
		int yy = y + d[j][1];
		if (xx < 0 || xx >= 5 || yy < 0 || yy >= 6) continue;
		a[i][xx * 6 + yy] = 1;
	    }
	}
	guess();
	printf("PUZZLE #%d\n", ++cas);
	for (int i = 0; i < 5; i++) {
	    for (int j = 0; j < 5; j++)
		printf("%d ", out[i][j]);
	    printf("%d\n", out[i][5]);
	}
    }
    return 0;
}

#include 
#include 
#include 
using namespace std;

const int d[5][2] = {{0, 0}, {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
const int N = 6;
int t, g[N][N], tmp[N][N], out[N][N];

bool judge(int s) {
    memset(out, 0, sizeof(out));
    for (int i = 0; i < 5; i++)
	for (int j = 0; j < 6; j++)
	    tmp[i][j] = g[i][j];
    for (int i = 0; i < 6; i++) {
	if (s&(1<= 5 || yy >= 6) continue;
		tmp[xx][yy] = (!tmp[xx][yy]);
	    }
	}
    }
    for (int i = 1; i < 5; i++) {
	for (int j = 0; j < 6; j++) {
	    if (tmp[i - 1][j]) {
		out[i][j] = 1;
		for (int k = 0; k < 5; k++) {
		    int xx = i + d[k][0];
		    int yy = j + d[k][1];
		    if (xx < 0 || yy < 0 || xx >= 5 || yy >= 6) continue;
		    tmp[xx][yy] = (!tmp[xx][yy]);
		}
	    }
	}
    }
    for (int i = 0; i < 6; i++)
	if (tmp[4][i]) return false;
    return true;
}

void solve() {
    for (int i = 0; i < (1<<6); i++)
	if (judge(i)) return;
}

int main() {
    int cas = 0;
    scanf("%d", &t);
    while (t--) {
	for (int i = 0; i < 5; i++)
	    for (int j = 0; j < 6; j++)
		scanf("%d", &g[i][j]);
	solve();
	printf("PUZZLE #%d\n", ++cas);
	for (int i = 0; i < 5; i++) {
	    for (int j = 0; j < 5; j++)
		printf("%d ", out[i][j]);
	    printf("%d\n", out[i][5]);
	}
    }
    return 0;
}