题目链接:【http://poj.org/problem?id=1222】
题意:Light Out,给出一个5 * 6的0,1矩阵,0表示灯熄灭,反之为灯亮。输出一种方案,使得所有的等都被熄灭。
题解:首先可以用高斯消元来做,对于每个点,我们列出一个方程,左边是某个点和它相邻的点,他们的异或值等于右边的值(灯亮为1 ,灯灭为0),然后求一个异或高斯消元就可以了。可以用bitset优化,或者__int128优化(其实unsigned就可以了)。
还可以枚举第一行的按开关的状态共有1<<6中状态,从上到下检查,如果某一行的某一个灯是亮的,那只有用按下下一行的这个位置的开关使得这个位置的灯熄灭,最后判断最后一行是否熄灭就可以了。
高斯消元:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 35;
int T;
int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
int a[maxn][maxn], ans[maxn];
int idx(int x, int y)
{
return (x - 1) * 6 + y;
}
void Guess()
{
int i, j, k, l;
for(i = 1, j = 1; i <= 30 && j <= 30; j++)
{
for(k = i; k <= 30; k++)
if(a[k][j]) break;
if(a[k][j])
{
for(l = 1; l <= 31; l++) swap(a[i][l], a[k][l]);
for(l = 1; l <= 30; l++) //debug从1开始(回代)
{
if(l != i && a[l][j])
for(k = 1; k <= 31; k++)
a[l][k] ^= a[i][k];
}
i++;
}
}
for(int j = 1; j < i; j++) ans[j] = a[j][31];
//*元不是必须按的,则标记为0
}
int main ()
{
int ic =0;
scanf("%d", &T);
while(T--)
{
memset(a, 0, sizeof(a));
for(int i = 1; i <= 5; i++)
for(int j = 1; j <= 6; j++)
{
scanf("%d", &a[idx(i, j)][31]);
}
for(int i = 1; i <= 30; i++)
{
a[i][i] = 1;
int X = (i - 1) / 6 + 1;
int Y = i - idx(X, 0);
for(int j = 0; j < 4; j++)
{
int x = X + dir[j][1];
int y = Y + dir[j][0];
if(x < 1 || y < 1 || x > 5 || y > 6) continue;
a[i][idx(x, y)] = 1;
}
}
Guess();
printf("PUZZLE #%d\n",++ic);
for(int i = 1; i <= 30; i++)
{
printf("%d", ans[i]);
if(!(i % 6)) printf("\n");
else printf(" ");
} }
return 0;
}
Bitset:
#include<bitset>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 35;
int T;
int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
bitset<maxn>a[maxn];
int idx(int x, int y)
{
return (x - 1) * 6 + y;
}
void Guess()
{
int i, j, k, l;
for(i = 1, j = 1; i <= 30 && j <= 30; j++)
{
for(k = i; k <= 30; k++) if(a[k][j]) break;
if(a[k][j])
{
swap(a[i], a[k]);
for(l = 1; l <= 30; l++) //debug从1开始(回代)
if(l != i && a[l][j]) a[l] ^= a[i];
i++;
}
}
}
int main ()
{
int ic = 0;
scanf("%d", &T);
while(T--)
{
for(int i = 1; i <= 31; i++) a[i].reset();
for(int i = 1; i <= 5; i++)
for(int j = 1; j <= 6; j++)
{
int t = 0 ;
scanf("%d", &t);
if(t) a[idx(i, j)].set(31);
}
for(int i = 1; i <= 30; i++)
{
a[i][i] = 1;
int X = (i - 1) / 6 + 1;
int Y = i - idx(X, 0);
for(int j = 0; j < 4; j++)
{
int x = X + dir[j][1];
int y = Y + dir[j][0];
if(x < 1 || y < 1 || x > 5 || y > 6) continue;
a[i].set(idx(x, y));
}
}
Guess();
printf("PUZZLE #%d\n", ++ic);
for(int i = 1; i <= 30; i++)
{
if(a[i][31]) printf("1");
else printf("0");
if(!(i % 6)) printf("\n");
else printf(" ");
}
}
return 0;
}
unsigned:
#include<bitset>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 35;
int T;
int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
unsigned long long a[maxn];
int idx(int x, int y)
{
return (x - 1) * 6 + y;
}
void Guess()
{
int i, j, k, l;
for(i = 1, j = 1; i <= 30 && j <= 30; j++)
{
for(k = i; k <= 30; k++) if(a[k] & ((unsigned long long)1 << (j - 1))) break;
if(a[k] & ((unsigned long long)1 << (j - 1)))
{
swap(a[i], a[k]);
for(l = 1; l <= 30; l++)
if(l != i && a[l] & ((unsigned long long)1 << (j - 1))) a[l] ^= a[i];
i++;
}
}
}
int main ()
{
int ic = 0;
scanf("%d", &T);
while(T--)
{
for(int i = 1; i <= 31; i++) a[i] = 0;
for(int i = 1; i <= 5; i++)
for(int j = 1; j <= 6; j++)
{
int t = 0 ;
scanf("%d", &t);
if(t) a[idx(i, j)] |= ((unsigned long long)1 << 30);
}
for(int i = 1; i <= 30; i++)
{
a[i] |= ((unsigned long long)1 << (i - 1));
int X = (i - 1) / 6 + 1;
int Y = i - idx(X, 0);
for(int j = 0; j < 4; j++)
{
int x = X + dir[j][1];
int y = Y + dir[j][0];
if(x < 1 || y < 1 || x > 5 || y > 6) continue;
a[i] |= ((unsigned long long)1 << idx(x, y) - 1);
}
}
Guess();
printf("PUZZLE #%d\n", ++ic);
for(int i = 1; i <= 30; i++)
{
if(a[i] & ((unsigned long long)1 << 30)) printf("1");
else printf("0");
if(!(i % 6)) printf("\n");
else printf(" ");
}
}
return 0;
}
二进制状态枚举:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 15;
int T;
int a[maxn][maxn], tmp[maxn][maxn], ans[maxn][maxn];
int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
void flip(int x, int y)
{
ans[x][y] = 1;
tmp[x][y] ^= 1;
for(int i = 0; i < 4; i++)
{
int X = x + dir[i][0];
int Y = y + dir[i][1];
if(X < 1 || X > 5 || Y < 1 || Y > 6) continue;
tmp[X][Y] ^= 1;
}
}
int main ()
{
int ic = 0;
scanf("%d", &T);
while(T--)
{
for(int i = 1; i <= 5; i++)
for(int j = 1; j <= 6; j++)
scanf("%d", &a[i][j]);
for(int k = 0; k <= (1 << 6) - 1; k++)
{
for(int i = 1; i <= 5; i++)
for(int j = 1; j <= 6; j++)
tmp[i][j] = a[i][j], ans[i][j] = 0;
int t = k, pos = 1;
while(t)
{
if(t & 1) flip(1, pos);
t >>= 1;
pos++;
}
for(int i = 1; i <= 4; i++)
for(int j = 1; j <= 6; j++)
if(tmp[i][j]) flip(i + 1, j);
int sum = 0;
for(int i = 1; i <= 6; i++)
sum += tmp[5][i];
if(!sum) break;
}
printf("PUZZLE #%d\n",++ic);
for(int i = 1; i <= 5; i++)
{
for(int j = 1; j <= 5; j++)
printf("%d ", ans[i][j]);
printf("%d\n", ans[i][6]);
}
}
return 0;
}