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

Poj 1222 EXTENDED LIGHTS OUT (數學_高斯消元)

編輯:C++入門知識

題目大意:給一個5*6的01矩陣,0表示燈暗的,1表示燈亮著。矩陣中每個位置表示一個按鈕,當按鈕按動時它周圍(上下左右)的燈變成相反的狀態。問怎麼按可以將所有的燈都變成暗的。

解題思路:這類開關問題算比較經典的高斯消元題了,做這題時我能想到怎麼建立那個矩陣,但後面的那個解不知道如何求,線代老師死得早啊。
    每個燈最後的狀態都只由自己和旁邊的按鈕決定。有30盞燈,每種燈最後的狀態是0,那麼最初始的狀態若是0,則中間動它的則必須為偶數次,否則為奇數次。我們設30個方程,每個方程等號右邊的值模2就等於矩陣裡對應的值。這樣初始時矩陣裡的值都是0,如果某些點能影響這個點,那麼那幾個點就標記為1。這樣每個點都對應一個未知量,最後的值為0或1。
    矩陣構造出來之後,稍微修改下高斯消元的模板就可以過了。因為這題很特殊解中只有0和1,所以只要用用幾個位操作就好。

測試數據:
1
0 1 1 0 1 0
1 0 0 1 1 1
0 0 1 0 0 1
1 0 0 1 0 1
0 1 1 1 0 0
Out:
PUZZLE #1
1 0 1 0 0 1
1 1 0 1 0 1
0 0 1 0 1 1
1 0 0 1 0 0
0 1 0 0 0 0

C艹代碼:
[cpp] 
<span style="color:#ff0000;">#include <stdio.h> 
#include <string.h> 
#include <algorithm> 
using namespace std; 
#define MOD 2 
#define MAX 35 
 
 
int n,m,x[MAX]; 
int arr[MAX][MAX]; 
int mat[MAX][MAX]; 
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; 
 
 
void Initial() { 
 
    int i,j,k,row,col; 
 
 
    n = m = 5 * 6; 
    memset(mat,0,sizeof(mat)); 
    for (i = 0; i < 5; ++i) 
        for (j = 0; j < 6; ++j) { 
 
            row = i * 6 + j; 
            mat[row][row] = 1; 
            mat[row][m] = arr[i][j]; 
            for (k = 0; k < 4; ++k) { 
 
                int ii = dir[k][0] + i; 
                int jj = dir[k][1] + j; 
                if (ii >= 0 && ii < 5 
                        && jj >=0 && jj < 6) 
                    mat[row][ii*6+jj] = 1; 
            } 
        } 

int Gcd(int x,int y) { 
 
    int r = x % y; 
    while (r) { 
 
        x = y,y = r; 
        r = x % y; 
    } 
    return y; 

int Lcm(int x,int y) { 
 
    return x / Gcd(x,y) * y; 

void Gauss_AC() { 
 
    int i,j,row,max_r,col; 
    int ta,tb,temp,LCM; 
 
 
    row = col = 0; 
    for (; row < n && col < m; ++row,++col) { 
 
        max_r = row; 
        for (j = row + 1; j < n; ++j) 
            if (mat[j][col]) { 
 
                max_r = j; 
                break; 
            } 
        if (mat[max_r][col] == 0) { 
 
            row--; 
            continue; 
        } 
 
 
        if (row != max_r) 
            for (j = col; j <= m; ++j) 
                swap(mat[row][j],mat[max_r][j]); 
        for (i = row + 1; i < n; ++i)   //將每一行的首元素消成0,故要用row行去異或i行 
            if (mat[i][col]) for (j = col; j <= m; ++j) 
                mat[i][j] ^= mat[row][j]; 
    } 
 
 
    for (i = m - 1; i >= 0; --i) { 
 
        x[i] = mat[i][m];               //mat[i][i]為1,那麼mat[i][m]和其他列的和就必須為0故用異或,如果異或為1則x[i]為1 
        for (j = i + 1; j < m; ++j) 
            x[i] ^= (mat[i][j] && x[j]); 
    } 

 
 
int main() 

    int i,j,k,t,cas = 0; 
 
 
    scanf("%d",&t); 
    while (t--) { 
 
        for (i = 0; i < 5; ++i) 
            for (j = 0; j < 6; ++j) 
                scanf("%d",&arr[i][j]); 
 
 
        Initial(); 
        Gauss_AC(); 
        printf("PUZZLE #%d\n",++cas); 
        for (i = 0; i < m; ++i) 
            printf("%d%c",x[i],(i%6)==5?'\n':' '); 
    } 

 
</span> 


作者:woshi250hua

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