首页 > 代码库 > uva 1560 - Extended Lights Out(枚举 | 高斯消元)
uva 1560 - Extended Lights Out(枚举 | 高斯消元)
题目链接:uva 1560 - Extended Lights Out
题目大意:给定一个5?6的矩阵,每个位置上有一个灯和开关,初始矩阵表示灯的亮暗情况,如果按了这个位置的开关,将会导致周围包括自己位置的灯状态变换,求一个按开关位置,保证所有灯都灭掉。
解题思路:
- 枚举,枚举第一行的状态,然后递推出后面四行的状态。
- 高斯消元,对于每个位置对定变量,这样列出30个方程求解。
C++ 枚举#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 10;
const int R = 5;
const int C = 6;
int arr[maxn][maxn], v[maxn][maxn], p[maxn][maxn];
bool judge (int s) {
memset(p, 0, sizeof(p));
memset(v, 0, sizeof(v));
for (int i = 0; i < C; i++) {
if (s&(1<<i)) {
p[1][i+1] = 1;
for (int j = 0; j <= 2; j++)
v[1][i+j] ^= 1;
v[2][i+1] ^= 1;
}
}
for (int i = 2; i <= R; i++) {
for (int j = 1; j <= C; j++)
if (v[i-1][j]^arr[i-1][j]) {
p[i][j] = 1;
for (int k = -1; k <= 1; k++)
v[i][j+k] ^= 1;
v[i+1][j] ^= 1;
}
}
for (int i = 1; i <= C; i++)
if (v[R][i]^arr[R][i])
return false;
for (int i = 1; i <= R; i++) {
for (int j = 1; j < C; j++)
printf("%d ", p[i][j]);
printf("%d\n", p[i][C]);
}
return true;
}
int main () {
int cas;
scanf("%d", &cas);
for (int kcas = 1; kcas <= cas; kcas++) {
for (int i = 1; i <= R; i++)
for (int j = 1; j <= C; j++)
scanf("%d", &arr[i][j]);
printf("PUZZLE #%d\n", kcas);
for (int s = 0; s < (1<<C); s++)
if (judge(s))
break;
}
return 0;
}
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int dir[5][2] = {{0, 0}, {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
const int maxn = 30;
const int R = 5;
const int C = 6;
typedef int Mat[maxn+5][maxn+5];
Mat A;
int v[R+5][C+5];
void init () {
memset(A, 0, sizeof(A));
memset(v, 0, sizeof(v));
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
int x = i * C + j;
scanf("%d", &A[x][maxn]);
for (int k = 0; k < 5; k++) {
int p = i + dir[k][0];
int q = j + dir[k][1];
if (p < 0 || p >= R || q < 0 || q >= C)
continue;
A[x][p*C+q] = 1;
}
}
}
}
void gauss_elimination (Mat a, int n) {
for (int i = 0; i < n; i++) {
int r = i;
while (A[r][i] == 0)
r++;
if (r != i) {
for (int j = 0; j <= n; j++)
swap(A[i][j], A[r][j]);
}
for (int j = i + 1; j < n; j++) {
if (A[j][i]) {
for (int k = 0; k <= n; k++)
A[j][k] ^= A[i][k];
}
}
}
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j < n; j++)
A[i][n] ^= (A[j][n] * A[i][j]);
if (A[i][n])
v[i/C][i%C] = 1;
}
}
int main () {
int cas;
scanf("%d", &cas);
for (int kcas = 1; kcas <= cas; kcas++) {
init();
gauss_elimination(A, maxn);
printf("PUZZLE #%d\n", kcas);
for (int i = 0; i < R; i++) {
printf("%d", v[i][0]);
for (int j = 1; j < C; j++)
printf(" %d", v[i][j]);
printf("\n");
}
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。