poj1222–EXTENDED LIGHTS OUT(高斯消元)
分类：———-数学———-代数
题目链接：点击打开链接
题目大意：给出5*6的矩阵，每个格子都是一个开关(开是1，关是0)，，每改变一个格子，格子自身和上下左右都会改变，问最终都要变成关，需要怎么操作。
每个格子只能被操作0次，或1次，多了是没有意义的，所以按照每一个格子可以影响的位置列出方程组。高斯消元
#include <cstdio>#include <cstring>#include <algorithm>using namespace std ;int s[5][2] = { {0,0},{0,1},{0,-1},{1,0},{-1,0} } ;int Map[30][30] , a[30] , ans[30] ;void solve() {int i , j , k , l ;for(i = 0 , k = 0 ; i < 30 && k < 30 ; i++ , k++) {for(j = i ; j < 30 ; j++)if( Map[j][k] ) break ;if( j >= 30 ) {i– ;continue ;}if( i != j ) {for(l = k ; l < 30 ; l++)swap(Map[i][l],Map[j][l]) ;swap(a[i],a[j]) ;}for(j = i+1 ; j < 30 ; j++) {if( !Map[j][k] ) continue ;for(l = k ; l < 30 ; l++)Map[j][l] = Map[i][l]^Map[j][l] ;a[j] = a[i]^a[j] ;}}for(i = 29 ; i >= 0 ; i–) {for(j = i+1 ; j < 30 ; j++)a[i] = a[i]^(ans[j]*Map[i][j]) ;ans[i] = a[i] ;}memset(Map,0,sizeof(Map)) ;for(i = 0 ; i < 30 ; i++) {if( ans[i] ) {Map[ i/6 ][ i%6 ] = 1 ;}}for(i = 0 ; i < 5 ; i++) {for(j = 0 ; j < 5 ; j++)printf("%d ", Map[i][j]) ;printf("%d\n", Map[i][5]) ;}return ;}int main() {int t , step = 0 ;int i , j , k , x , y ;scanf("%d", &t) ;while( t– ) {memset(Map,0,sizeof(Map)) ;for(i = 0 ; i < 5 ; i++) {for(j = 0 ; j < 6 ; j++) {for(k = 0 ; k < 5 ; k++) {x = i + s[k][0] ;y = j + s[k][1] ;if( x >= 0 && x < 5 && y >= 0 && y < 6 )Map[x*6+y][i*6+j] = 1 ;}}}for(i = 0 ; i < 5 ; i++)for(j = 0 ; j < 6 ; j++)scanf("%d", &a[i*6+j]) ;printf("PUZZLE #%d\n", ++step) ;solve() ;}return 0 ;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇poj1166–The Clocks(高斯消元)
顶1踩0
从此便踏上征途，也许会孤独一程。
