POJ 1222 熄灯问题【高斯消元】

时间：2023-12-09 23:30:19

<题目链接>

题目大意：

有一个5*6的矩阵，每一位是0或者1。 没翻转一位，它的上下左右的数字也为改变。（0变成1,1变成0）。要把矩阵中所有的数都变成0。求最少翻转次数的方案，输出矩阵（需要翻转的地方用1表示，反则用0表示）。

解题分析：

利用高斯消元，把这30个开关想象成是30个方程，第i个开关状态对应于第i个方程的右边的值。左边的是所有能够影响到的开关的值。

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

using namespace std;

const int N = ;

int a[N][N], ans[N];

int dx[] = { ,,,-, };

int dy[] = { ,,,,- };

int idx(int x, int y) { return (x - ) *  + y; }

void Gauss()

{

    int i, j, k, l;

    memset(ans, , sizeof(ans));

    for (i = , j = ; i <=  && j <= ; j++)

    {

        for (k = i; k <= ; k++)

            if (a[k][j]) break;

        if (a[k][j])

        {

            for (l = ; l <= ; l++) swap(a[i][l], a[k][l]);

            for (l = ; l <= ; l++)     //debug从1开始（回代）

            {

                if (l != i && a[l][j])

                    for (k = ; k <= ; k++)

                        a[l][k] ^= a[i][k];           //高斯消元的^异或运算；

            }

            i++;

        }

    }

    for (int j = ; j<i; j++) ans[j] = a[j][];

}

int main()

{

    int x, y, T, cas = ;

    scanf("%d", &T);

    while (T--)

    {

        memset(a, , sizeof(a));

        for (int i = ; i <= ; i++)

            for (int j = ; j <= ; j++)

            {

                scanf("%d", &a[idx(i, j)][]);      //这里是将该矩阵按列线性存储

                for (int k = ; k <= ; k++)

                {

                    x = i + dx[k]; y = j + dy[k];

                    if (x> || y> || x< || y<) continue;

                    a[idx(i, j)][idx(x, y)] = ;       //将这个点周围四个点全部置为1

                }

            }

        for (int i = ; i <= ; i++) a[i][i] = ;

        Gauss();

        printf("PUZZLE #%d\n", ++cas);

        for (int i = ; i <= ; i++)

        {

            printf("%d ", ans[i]);

            if (i %  == ) printf("\n");

        }

    }

    return ;

}

2018-08-08

相关文章