您的位置:手机购彩平台 > 手机购彩平台-编程 > 问最后要使得所有的灯关掉的操作矩阵(1表示该位

问最后要使得所有的灯关掉的操作矩阵(1表示该位

2019-09-24 15:47

EXTENDED LIGHTS OUT

题意:给一个5*6的01矩阵,对一个位置操作(0->1开灯或者1->0关灯)会影响到周边灯状态反转。问最后要使得所有的灯关掉的操作矩阵(1表示该位置的灯操作了)

提示:01矩阵,题目给了说是操作两次就相当于没操作,但是还有隐含的意思就是这就是一个异或操作;对于01矩阵加上操作矩阵得到0矩阵,可知所作用的矩阵和原矩阵相同;(操作矩阵:如对操作就相当于加上只有左上角有3个1的矩阵,但是把这个矩阵转化为了一个维度为30的向量形式,有30栈灯所以下面是一个30*30的矩阵)这是高斯消元列方程的基础;

高斯消元法:最重要的是要想到构造出一个30*30的作用矩阵,第i列数字中(列号0~29表示灯的标号)1表示第i盏灯操作会影响到1所对应的行号的灯,存储在增广矩阵a[][]中;

所谓增广矩阵就是抽象出只含方程组的系数和结果的矩阵。这样第i盏灯最终的状态a[i][30] = Σ(a[i][j]*x[j])(0 <= j < 30)。这就是为什么在最后化成了上三角之后怎么是对行向量操作的原因;(a[i][j] && x[j]表示第j盏灯操作会影响到第i盏灯,并且第j盏灯是开的。还有一个前提就是a[i][i] = 1,所以x[i] = a[i][var])

注:在高斯消元列方程转移到矩阵时,最好直接看每一个系数与变量之间的对应关系,而不是用行向量与列向量来看。

图片 1图片 2

#include<iostream>#include<cstdio>#include<cstring>#include<string.h>#include<algorithm>#include<map>#include<queue>#include<vector>#include<cmath>#include<stdlib.h>#include<time.h>using namespace std;#define rep0 for(int i = ;i < #define rep1 for(int i = ;i <= #define rep_0 for(int i = ;i > #define rep_1 for(int i = ;i >= #define MS0 memset(a,0,sizeof#define MS1 memset(a,-1,sizeofint dir[2][4] = {{0,1,0,-1},{1,0,-1,0}};int a[35][35];int equ,var;int x[35];int Guass(){    int i,j,k,free_var = 0;    rep0(i,0,equ){        int mx = i;        rep0(j,i+1,equ)            if(abs > abs)  mx = j;        if(a[mx][i] == 0){            free_var++;            continue;        }        if(mx != i)            rep1(k,i,var)                swap(a[i][k],a[mx][k]);        rep0(j,i+1,equ){            if{    //第j盏灯也会对第i盏灯产生影响;                rep1(k,i,var)                    a[j][k] ^= a[i][k];            }        }    }    if(free_var != 0) return free_var;    rep_1(i,var-1,0){        x[i] = a[i][var];        rep0(j,i+1,equ)            x[i] ^= (a[i][j] && x[j]);  //第j个灯会影响到第i盏灯,同时第j盏灯也会亮。    }}void init(){    int i,j,k;    rep0(i,0,5)        rep0(j,0,6){            int x = i*6+j;            a[x][x] = 1;            rep0(k,0,4){                int nx = i + dir[0][k] ,ny = j + dir[1][k];                int pos = nx*6+ny;                if(nx < 0 || nx >= 5 || ny < 0 || ny >= 6) continue;                a[pos][x] = 1;  //本来是对称的矩阵,因为影响是相互的,但是写成[x][pos]思想就不一样了            }        }}int main(){    int T,kase = 1,i;    cin>>T;    while(T--){        MS0;        rep0(i,0,30) scanf("%d",&a[i][30]);        init();        equ = var = 30;        Guass();        printf("PUZZLE #%dn",kase++);        rep0(i,0,30)            printf("%d%c",x[i],(i+1)%6?' ':'n');    }    return 0;}

View Code

本文由手机购彩平台发布于手机购彩平台-编程,转载请注明出处:问最后要使得所有的灯关掉的操作矩阵(1表示该位

关键词: