題意：一個(gè)01矩陣，表示燈的亮滅狀態(tài)，每次操作可以改變一個(gè)十字形狀內(nèi)的五個(gè)燈的狀態(tài)。問(wèn)能否將所有燈熄滅。

分析：高斯消元法

對(duì)于每個(gè)燈的兩滅有影響的開關(guān)就是它附近十字形內(nèi)的五個(gè)開關(guān)。所以對(duì)于每個(gè)燈可以列一個(gè)方程，即周圍五個(gè)開關(guān)異或起來(lái)的結(jié)果應(yīng)該可以使該燈熄滅。

就是利用線性代數(shù)知識(shí)，寫出增廣矩陣，化為階梯形矩陣，有下到上依次解出各未知量。

View Code #include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
usingnamespace std;

#define maxn 35

int f[maxn][maxn];
int g[maxn][maxn];
int x[maxn];
int dir[5][2] =
{
{ 0, 0 },
{ 0, 1 },
{ 1, 0 },
{ -1, 0 },
{ 0, -1 } };

void debug()
{
for (int i =0; i <30; i++)
{
for (int j =0; j <31; j++)
cout <<""<< g[i][j];
cout << endl;
}
cout << endl;
}

void input()
{
for (int i =0; i <5; i++)
for (int j =0; j <6; j++)
scanf("%d", &g[i *6+ j][30]);
}

void work()
{
int k;
int row, col;
for (row =0, col =0; row <30&& col <30; row++, col++)
{
for (k = row; k <30; k++)
if (g[k][col] !=0)
break;
if (k ==30)
{
row--;
continue;
}
if (k != row)
for (int i = col; i <=30; i++)
swap(g[row][i], g[k][i]);
for (int i = row +1; i <30; i++)
if (g[i][col])
for (int j = col; j <=30; j++)
g[i][j] ^= g[row][j];
}
for (int i = row; i >=0; i--)
{
x[i] = g[i][30];
for (int j =29; j > i; j--)
x[i] ^= (g[i][j] && x[j]);
}
}

void print()
{
for (int i =0; i <5; i++)
{
printf("%d", x[i *6]);
for (int j =1; j <6; j++)
printf(" %d", x[i *6+ j]);
putchar('\n');
}
}

int main()
{
//freopen("t.txt", "r", stdin);
for (int i =0; i <5; i++)
for (int j =0; j <6; j++)
for (int k =0; k <5; k++)
{
int a = i + dir[k][0];
int b = j + dir[k][1];
if (a >=0&& b >=0&& a <5&& b <6)
f[i *6+ j][a *6+ b] =1;
}
int t;
scanf("%d", &t);
for (int i =0; i < t; i++)
{
printf("PUZZLE #%d\n", i +1);
memcpy(g, f, sizeof(g));
input();
work();
print();
}
return0;
}

　　

轉(zhuǎn)載于:https://www.cnblogs.com/rainydays/archive/2011/08/31/2160748.html

總結(jié)

以上是生活随笔為你收集整理的poj1222的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。