POJ 1222 高斯消元更稳

大致题意：

　　有5*6个灯，每个灯只有亮和灭两种状态，分别用1和0表示。按下一盏灯的按钮，这盏灯包括它周围的四盏灯都会改变状态，0变成1,1变成0。现在给出5*6的矩阵代表当前状态，求一个能全部使灯灭的解。

分析：

　　题目已经提示我们，按两次和按零次是一样的效果，所以每个灯的解为0或者1。这样我们可以构造一个30*30的方程组，右边的常数列为灯的初始状态。

　　影响当前灯的状态的按钮有5个

　　a[i][j]+x[i][j]+x[i][j-1]+x[i-1][j]+x[i][j+1]+x[i][j+1]=0 (mod 2)

　　x[i][j]+x[i][j-1]+x[i-1][j]+x[i][j+1]+x[i][j+1]=a[i][j] (mod 2)

　　不难发现，灯的初始状态只影响常数列，与系数矩阵无关，系数矩阵是不变的。

　　消元的过程中系数也可以对2取模，按n次与按n+2次的效果是一样的。对2取模更方便的运算就是异或了。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

int n=30;

int a[35][35],x[35];

int mat[35][35];

void init()//初始化系数矩阵

{

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

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

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

    {

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

        {

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

            {

                int x=i+dx[k];

                int y=j+dy[k];

                if(x>0 && x<=5 && y>0 && y<=6)

                    mat[(i-1)*6+j][(x-1)*6+y]=1;

            }

        }

    }

}

void Gauss(int equ,int var)

{

    int row,col;

    row=col=1;

    while(row<=equ && col<=var)

    {

        //列非零主

        int r=row;

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

            if(a[i][col]!=0)

            {

                r=i;

                break;

            }

        if(r!=row)

        {

            for(int i=col; i<=var+1; i++)

                swap(a[row][i],a[r][i]);

        }

        if(a[row][col]==0)//说明有自由变元

        {

            col++;

            continue;

        }

        //消元

        for(int i=row+1; i<=equ; i++)

        {

            if(a[i][col]==0) continue;

            for(int j=col; j<=var+1; j++)

                a[i][j]^=a[row][j];

        }

        row++;

        col++;

    }

    for(int i=equ; i>=1; i--)

    {

        x[i]=a[i][var+1];

        for(int j=i+1; j<=var; j++)

            x[i]^=a[i][j]*x[j];

    }

}

int main()

{

    int t,kase=1;

    scanf("%d",&t);

    init();

    while(t--)

    {

        memset(a,0,sizeof(a));

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

            scanf("%d",&a[i][31]);

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

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

                a[i][j]=mat[i][j];

        Gauss(n,n);

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

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

        {

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

                printf("%d ",x[(i-1)*6+j]);

            printf("%d\n",x[i*6]);

        }

    }

    return 0;

}

巴特西

POJ 1222 高斯消元更稳

最新文章

热门文章