poj1222 高斯消元

时间：2024-06-24 14:35:32

给了一个01矩阵然后选在一个点1变0或者0变1 然后 与他相邻的 数也相应的变成相反的数，问最后求出一种方案把他们变成全0 将每一个位置上的状态看做一个变元，30个变元，列出30个异或方程

#include <iostream>

#include <algorithm>

#include <string.h>

#include <cstdio>

#include <vector>

using namespace std;

#define eps 1e-9

const int MAXN=;

int a[MAXN][MAXN],x[MAXN];//方程的左边的矩阵和等式右边的值，求解之后x存的就是结果

int equ,var;//方程数和未知数个数

int Gauss()

{

    int i,j,row,col,max_r;

    equ=var=;

    for(row=,col=;row<equ&&col<var;row++,col++)

    {

        max_r=row;

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

          if(a[i][col])

            { max_r=i; break; }

        if(row!=max_r)

        {

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

              swap(a[row][j],a[max_r][j]);

            swap(x[row],x[max_r]);

        }

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

          if(i!=row&&a[i][col])

          {

              x[i]^=x[row];

              for(j=col+;j<var;j++)a[i][j]=a[i][j]^a[row][j];

              a[i][col]=;

          }

    }

    return ;

}

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

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

int idmark[][];

int main()

{

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

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

           idmark[i][j]=i*+j;

    int cas;

    scanf("%d",&cas);

    for(int cc=; cc<=cas ; cc++)

    {

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

        {

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

        }

       memset(a,,sizeof(a));

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

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

              a[ idmark[i][j] ][ idmark[i][j] ] = ;

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

              int tx= i+dx[k];

              int ty= j+dy[k];

              if(tx>=&&ty>=&&tx<&&ty<)

              a[ idmark[i][j] ][ idmark[tx][ty] ]=;

          }

       }

       Gauss();

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

       int cur=;

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

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

        printf("%d%c",x[cur++],j==?'\n':' ');

    }

    return ;

}

相关文章