程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj1222--EXTENDED LIGHTS OUT(高斯消元)

poj1222--EXTENDED LIGHTS OUT(高斯消元)

編輯:C++入門知識

poj1222--EXTENDED LIGHTS OUT(高斯消元)


 

題目大意:給出5*6的矩陣,每個格子都是一個開關(開是1,關是0),每改變一個格子,格子自身和上下左右都會改變,問最終都要變成關,需要怎麼操作。

每個格子只能被操作0次,或1次,多了是沒有意義的,所以按照每一個格子可以影響的位置列出方程組。高斯消元

 

 

#include 
#include 
#include 
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
, 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
, ++step) ;
        solve() ;
    }
    return 0 ;
}


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved